Чем занимается теория линейного программирования
В самых различных отраслях народного хозяйства постоянно возникает
необходимость в составлении наилучшего плана производства: плана
перевозок нефти между местами ее добычи и городами-потребителями;
плана использования станков или другого оборудования; плана использования
имеющихся ресурсов. Нахождением наилучшего решения такого рода задач
и занимается теория линейного программирования. Название
"линейное" связано с нахождением оптимального (минимального или
максимального) значения линейной функции нескольких переменных,
на которые наложены ограничения в виде линейных уравнений или неравенств.
Слово "программирование" происходит от конечной цели методов этой
теории - составления оптимальной (наилучшей) программы действия.
Линейное программирование - новая область прикладной математики.
Основные идеи линейного программирования были развиты всего лишь
три десятилетия назад. В 1939 г. появилась работа советского академика
Л. В. Канторовича "Математические методы в организации и планировании
производства". В 1949 г. опубликована работа американского математика
Джорджа Б. Данцига, в которой излагались идеи метода последовательного
улучшения плана, называемого теперь симплексным методом. Этот
метод является одним из самых универсальных и эффективных.
Методы линейного программирования очень быстро получили широкое
применение в экономике при решении различных задач планирования.
О характере таких задач дает представление следующий пример.
Сначала рассмотрим экономическую постановку. задачи. Цех
выпускает два вида продукции: А и В (можно предположить,
что продукция А - это столы, продукция В - шкафы).
В данном цехе четыре группы оборудования (т. е. станков разного
типа), которое используется для производства одной штуки продукции
А и В указанным в таблице образом:
Виды продукции |
Группы оборудования
|
I |
II |
III |
IV |
А |
1 |
1 |
2 |
0 |
В |
1 |
2 |
0 |
2 |
Всего станков по группам оборудования |
18 |
24 |
24 |
18 |
Данные в таблице показывают, сколько станков определенной группы
используется одновременно для производства одной штуки продукции
(наличие нуля означает, что станки данной группы в производстве
данного вида продукции не используются). Цех получает прибыль с
одной штуки продукции вида А 40 рублей, вида В - 60
рублей. Необходимо составить такой производственный план цеха, который
позволял бы получать максимальную прибыль при имеющихся в наличии
станках и производственных мощностях.
|