Чем занимается теория линейного программирования

В самых различных отраслях народного хозяйства постоянно возникает необходимость в составлении наилучшего плана производства: плана перевозок нефти между местами ее добычи и городами-потребителями; плана использования станков или другого оборудования; плана использования имеющихся ресурсов. Нахождением наилучшего решения такого рода задач и занимается теория линейного программирования. Название "линейное" связано с нахождением оптимального (минимального или максимального) значения линейной функции нескольких переменных, на которые наложены ограничения в виде линейных уравнений или неравенств. Слово "программирование" происходит от конечной цели методов этой теории - составления оптимальной (наилучшей) программы действия.

Линейное программирование - новая область прикладной математики. Основные идеи линейного программирования были развиты всего лишь три десятилетия назад. В 1939 г. появилась работа советского академика Л. В. Канторовича "Математические методы в организации и планировании производства". В 1949 г. опубликована работа американского математика Джорджа Б. Данцига, в которой излагались идеи метода последовательного улучшения плана, называемого теперь симплексным методом. Этот метод является одним из самых универсальных и эффективных.

Методы линейного программирования очень быстро получили широкое применение в экономике при решении различных задач планирования. О характере таких задач дает представление следующий пример.

Сначала рассмотрим экономическую постановку. задачи. Цех выпускает два вида продукции: А и В (можно предположить, что продукция А - это столы, продукция В - шкафы). В данном цехе четыре группы оборудования (т. е. станков разного типа), которое используется для производства одной штуки продукции А и В указанным в таблице образом:

Виды продукции	Группы оборудования
Виды продукции	I	II	III	IV
А	1	1	2	0
В	1	2	0	2
Всего станков по группам оборудования	18	24	24	18

Данные в таблице показывают, сколько станков определенной группы используется одновременно для производства одной штуки продукции (наличие нуля означает, что станки данной группы в производстве данного вида продукции не используются). Цех получает прибыль с одной штуки продукции вида А 40 рублей, вида В - 60 рублей. Необходимо составить такой производственный план цеха, который позволял бы получать максимальную прибыль при имеющихся в наличии станках и производственных мощностях.

перейти к началу страницы