Элементы линейного программирования
Задача 23. Предприятие имеет возможность приобрести не более 20 трехтонных и не более 18 пятитонных автомашин. Отпускная цена трехтонного грузовика 4000 у.е, пятитонного — 5000 у.е. Сколько нужно приобрести автомашин каждой марки, чтобы их суммарная грузоподъемность была максимальной, если для приобретения автомашин выделено 150 тысяч рублей? Задачу решить графическим и аналитическим методами.
Решение. Пусть приобретено 
трехтонных и 
пятитонных
автомашин. Из условия задачи имеем
≤ ≤ 20
0 ≤ ≤ 18
4+ 5 = 150 . (1)
Суммарная грузоподъемность приобретенных грузовиков равна
L = 3 + 5
. (2)
Задача состоит в нахождении такого решения системы (1) , при котором линейная форма (целевая функция) (2) принимает наибольшее значение.
Графический метод решения
В прямоугольной системе координат 
построим многоугольник
OABCD, образованный прямыми = 0 (OD), =20 (AB), = 0 (AO ), = 18 ( CD), 4 + 5 = 150 ( BC) и прямую 3 + 5 = 0 (l) ( рис. 9 ).
Системе (1) удовлетворяют координаты точек, лежащих на пятиугольнике OABCD и внутри него. Так как прямые (l) и BC не параллельны, то для нахождения оптимального решения системы (1), для которого линейная форма (2) принимает наибольшее значение, достаточно найти значения этой формы в точках A, B, C, D и из полученных чисел выбрать наибольшее. В нашей задаче эти точки имеют следующие координаты: А (20; 0), В (20; 14), С (15, 18), D (0; 18). Подставляя координаты этих точек в (2), получим:
L (A) = L (20; 0 ) = 60; L (B) = L (20; 14) = 130;
L (C) = L (15; 18) = 135; L (D) = L (0; 18) = 90.
Рис. 9
Следовательно, L = L (15; 18) = 135, то есть предприятию следует приобрести 15 трехтонных и 18 пятитонных автомашин, при их общей грузоподъемностью 135 т.
Вопросы для самопроверки
Сформулируйте основную задачу линейного программирования. Приведите примеры.
Дайте геометрическую интерпретацию основной задачи линейного программирования.
В чем суть симплекс-метода решения задач линейного программирования?
