Тема 14. Элементы линейного программирования

[2] гл. XXVI § 3.

Задача 23. Предприятие имеет возможность приобрести не более 20 трехтонных и не более 18 пятитонных автомашин. Отпускная цена трехтонного грузовика 4000 руб., пятитонно­го - 5000 руб. Сколько нужно приобрести автомашин каж­дой марки, чтобы их суммарная грузоподъемность была мак­симальной, если для приобретения автомашин выделено 150 тысяч рублей? Задачу решить графическим и аналитиче­ским методами.

Решение. Пусть приобретено х₁ трехтонных и х₂ пяти­тонных автомашин. Из условия задачи имеем

(1)

Суммарная грузоподъемность приобретенных грузовиков равна

(2)

Задача состоит в нахождении такого решения системы (1), при котором линейная форма (целевая функция) (2) прини­мает наибольшее значение

Графический метод решения

В прямоугольной системе координат построим мно­гоугольник ОАВСD, образованный прямыми (OD), (АВ), (АО), (СD), (ВС) и прямую (L) (рис.9).

Системе (1) удовлетворяют координаты точек, лежащих на пятиугольнике ОАВСD и внутри него. Так как прямые (L) и ВС не параллельны, то для нахождения оптимального реше­ния системы (1), для которого линейная форма (2) прини­мает наибольшее значение, достаточно найти значения этой формы в точках А, В, С, D и из полученных чисел выбрать наибольшее. В нашей задаче эти точки имеют следующие координаты: А(20; 0), В(20; 14), С(15; 18), D(0; 18). Подставляя координаты этих точек в (2), получим:

L(A)=L(20;0)=60; L(В)=L(20;14)=130;

L(С)=L(15;18)=135; L(D)=L(0;18)=90.

Р и с. 9

Следовательно, L_max=L(15;18)=135, то есть предприятию

следует приобрести 15 трехтонных и 18 пятитонных автома­шин.

Аналитический метод решения

В систему (1) введем дополнительные неизвестные х₃ и х₄ , чтобы она приняла следующий вид:

₍₃₎

Система (3) имеет 3 уравнения и 4 неизвестные. Примем, на­пример,х₁, х₂, х₃ за базисные неизвестные, а х₄ — за свобод­ное неизвестное и выразим из системы (3) неизвестные х₁, х₂, х₃ через х₄. Тогда

, , и

L= .

Из последнего выражения следует, что L принимает наиболь­шее значение при х₄ =0 (так как х₄ 0). При х₄ = 0 имеем:

_, и L(15;18)=135.

Следовательно, предприятие должно приобрести 15 трех­тонных и 18 пятитонных автомашин при их общей грузоподъ­емности 135 тонн.

Вопросы для самопроверки

1. Сформулируйте основную задачу линейного програм­мирования. Приведите примеры.

2. Дайте геометрическую интерпретацию основной задачи линейного программирования.

3. В чем суть симплекс-метода решения задач линейного программирования?