Теория и методы принятия решений

3. В трёх пунктах находится однородный груз в количествах, соответственно равных 420, 380 и 400 т. Этот груз необходимо развести в три пункта назначения, в количествах, соответственно равных 260, 520 и 420 т. Тарифы перевозок 1 т груза из каждого пункта отправления в каждый пункт назначения задаются следующей таблицей:

.

Найти план перевозок, обеспечивающий вывоз всего имеющегося груза и завоз его в полном объёме в пункты назначения при минимальных транспортных расходах.

1.3. Геометрическое решение задач линейного программирования

Если система ограничений и целевая функция задачи линейного программирования содержат две переменные, то эту задачу можно решить геометрически.

Геометрическое решение задачи линейного программирования состоит в следующих действиях:

1. заменить в каждом ограничении знак неравенства на знак равно;
2. в прямоугольной системе построить соответствующие прямые,
3. выделить область точек на плоскости, координаты которых удовлетворяют системе ограничений (ограничению со знаком "?" удовлетворяют точки, находящиеся выше прямой, а знаку "?" – ниже прямой);
4. в целевой функции отбросить свободный член и построить соответствующую прямую;
5. при поиске максимума последнюю прямую параллельно перемещаем вверх, а минимума – вниз;
6. координаты точки области, которую прямая пересечёт последней, будут давать максимум (минимум) целевой функции, если эта точка существует.

Пример. Решить задачу линейного программирования:

f = x1 + 2x2 + 3 ? max

Решение.

1. Заменим в ограничениях знаки "?" на знак равно, получим уравнения двух прямых:

Построим эти прямые в прямоугольной системе координат:

2. Выделим область точек на плоскости, координаты которых удовлетворяют системе ограничений (на рисунке эта область 0ABC закрашена):

первому ограничению удовлетворяют точки на плоскости, которые лежат ниже прямой L1, второму ограничению – ниже прямой L2, третьему – точки, находящиеся правее оси Ox2, четвёртому – выше оси Ox1

3. Отбросим свободный член в целевой функции, получим функцию y = x1 + 2x2, построим график этой функции (прямую L3).

4. Перемещая прямую L3 параллельно вверх, находим, что последней точкой области 0ABC, которую она пересечёт, будет точка B.

5. Для нахождения координат точки В решаем систему уравнений: