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

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

Решение.

Пусть приобретено трехтонных и пятитонных автомашин. По условию задачи имеем систему ограничений:

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

.

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

В прямоугольной системе координат построим многоугольник OABCD, образованный прямыми = 0 (OD), = 20 (AB), = 0 (AO), = 18 (CD), 4 +5 =150 (BC) и прямую 3 +5 =0 (l) (рис.7).

X₁

Рис.7.

Системе ограничений удовлетворяют координаты точек, лежащих на пятиугольнике OABCD и внутри него. Т.к. прямые (l) и (ВС) не параллельны, то для определения оптимального решения системы ограничений, для которой линейная форма L принимает наибольшее значение, достаточно определить значения этой формы в точках A, B, C, D и из полученных чисел выбрать наибольшее. Эти точки в нашей задаче имеют следующие координаты: A(20, 0), B(20, 14), C(15, 18), D(0, 18). Подставляя координаты этих точек, определяем значения целевой функции:

L(A)=L(20; 0)=60; L(B)=L(20; 14)=130; L(C)=L(15; 18)=135; L(D)=L(0; 18)=90.

Следовательно, Lmax=L(15; 18)=135, т.е. предприятию следует приобрести 15 трехтонных и 18 пятитонных автомашин.

В систему ограничений введем дополнительные неизвестные , чтобы она приняла следующий вид:

Эта система имеет 3 уравнения и 4 неизвестных. Примем, например, x₁, x₂, x₃ за базисные неизвестные, а x₄ за базисное неизвестное и выразим из системы ограничений неизвестные, x₁, x₂, x₃ через. x₄. Тогда

и

.

Из последнего выражения следует, что L принимает наибольшее значение при x₄. = 0 (т.к. ). При x₄. = 0 имеем: x₁ = 15, x₂ = 18 и L(15; 18)=135.

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

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

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

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

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

Дата добавления: 2017-02-01