Решение оптимизационной задачи по грузоперевозкам

Проверим условие оптимальности для неположительных клеток матричной модели. Знак «+» говорит о том, что условие выполняется, знак «-» - не выполняется.

Vj – Ui ≤ Cij

Таким образом, мы получаем следующую таблицу.

Таблица 7

Проверка оптимальности решения

С помощью признака оптимальности базисного невырожденного плана перевозок мы определили, что допустимое базисное невырожденное решение, полученное с помощью метода минимальной стоимости является неоптимальным. Признаку оптимальности не удовлетворяется целых три клетки таблицы, поэтому для нахождения оптимального плана нам необходимо обратиться к методу потенциалов.

5.   Нахождение оптимального решения методом потенциалов 

Метод потенциалов используется для нахождения оптимального плана. Он стартует с неоптимального базисного невырожденного плана перевозок.

Алгоритм метода потенциалов:

1.    Базисный невырожденный план перевозок

2.    Проверка оптимальности

3.    Нахождение Vj, Ui

4.    Vj – Ui ≤ Cij

5.    Если П. 4 выполняется, то оптимальный план найден.

Если П. 4 не выполняется, то находим p,q по следующей формуле:

6.    Находим Xqp

Xqp=Z

7.    Находим и устраняем цикл.

8.    Возвращаемся к П.2.

Итак, применим метод потенциалов для лучшей из полученных моделей (получена методом минимальной стоимости). Модель представлена в таблице 8, на которой отображена проверка решения на оптимальность.

Таблица 8

Проверка оптимальности решения

В П. 3 было доказано, что анализируемая модель содержит в себе допустимый базисный план перевозок, однако он не является оптимальным. Найдем его с помощью метода потенциалов.

Как мы видим, две клетки (X11, X13,X14) не удовлетворяют признаку оптимальности базисного невырожденного плана перевозок. Клетка X11 содержит максимальное отклонениеV1 – U1 от C11 в 0,02, поэтому разместим в этой клетке значение Z. Теперь, согласно алгоритму метода, нам необходимо устранить образовавшийся в результате появления нового значения Z цикл.

X11,X21,X31,X41,X42,X43,X33,X34,X24,X23,X22,X12 образуют цикл (таблица 9).

Таблица 9

Введение новой переменной Z и способ устранения образовавшего цикла

Чтобы сделать план базисным, надо избавиться от данного цикла, то есть Z должно быть равно min(252;426;287;268). Z = 252.

426 – Z  ≥ 0

150 + Z ≥ 0

268 – Z ≥ 0

185 + Z ≥ 0

287 – Z ≥ 0

243 + Z ≥ 0

252 – Z ≥ 0

Z ≥ 0

ЯчейкаX41 будет равна нулю. Таким образом, четвертый поставщик не будет поставлять продукцию первому потребителю.

Преобразуем нашу таблицу, введем вместо Z реальное значение и устраним цикл (таблица 10).

Таблица 10

Введение вместо переменной Z реальное значение и устранение образовавшего цикла