Теорема 1.9.2. (Признак оптимальности)

Если план транспортной задачи является оптимальным, то ему соответствует система из m + n чисел , удовлетворяющих условиям:

- для занятых клеток ;

- для свободных клеток .

Числа и называются потенциалами соответственно i - го поставщика и j - го потребителя. Если рассматривать транспортную задачу как задачу линейного программирования, то эти числа являются двойственными оценками исходной задачи (1.17). Величина показывает величину увеличения (если ) или уменьшения (если ) значение целевой функции транспортной задачи, если в клетку (i; j) сделать поставку равную 1.

Проверка плана на оптимальность проводится следующим образом. Решается система уравнений

(1.19)

Так как уравнений m + n – 1 (по количеству занятых клеток), то решений бесконечно много. Выделяем одно из них, полагая один из потенциалов равным нулю. Нулем лучше положить потенциал, которому соответствует наибольшее количество занятых клеток. После того, как все потенциалы найдены, проверяем выполнение оценок

(1.20)

для всех свободных клеток. Если все неравенства (1.20) выполняются, то план оптимальный. Пусть имеется несколько отрицательных оценок (1.20). Тогда переходим к построению нового опорного плана.

Выбираем наибольшую по модулю отрицательную оценку. Напомним, что отрицательная оценка показывает, на какую величину убудет целевая функция, если в эту клетку сделать поставку в единицу груза. Следовательно, так как требуется минимизировать целевую функцию, выгодно сделать в эту клетку наибольшую возможную поставку. Чтобы определить величину поставки и те клетки, в которых будут изменяться величины поставок, строим, начиная из выбранной клетки, цикл по занятым клеткам. Такой цикл существует и притом только один. Выбранную клетку помечаем знаком «+», а далее по циклу чередуем знаки. Затем среди клеток помеченных знаком «–» выбираем наименьшую поставку d. Далее, двигаясь по циклу, прибавляем величину d в клетках помеченных знаком «+» и вычитаем величину d в клетках помеченных знаком «–». Получен новый опорный план. Затем нужно снова проверить его на оптимальность и т.д., пока не будет найден оптимальный план.

Запишем в нашем примере уравнения для занятых клеток.

.

Положим тогда, решая эти уравнения, получим

.

Теперь вычислим оценки для свободных клеток по формуле (1.20).

, , , ,

, , , .

Имеется клетка с отрицательной оценкой, значит план не оптимальный. Так как только одна клетка (2; 2) имеет отрицательную оценку, то будем заполнять поставкой именно эту клетку. Строим цикл, начиная из клетки (2; 2). Получается следующий цикл

(2; 2), (2; 3), (3:3), (3; 2), (2; 2).

При этом, знаком «+» помечены клетки (2; 2), (3:3), а знаком «–» клетки (2; 3), (3; 2).

	v1 = 10	v2 = 11	v3 = 12	v4 = 14	v5 = 0
u1 = – 2
u2 = 0		+ 10	– 12
u3 = – 2		– 9	+ 10

Среди клеток, помеченных знаком «–» минимальная поставка равна 20. В клетках помеченных знаком «–» вычтем эту величину, а в клетках помеченных знаком «+» добавим эту величину. Получим матрицу с новым опорным планом. Рассчитаем для него потенциалы.

	v1 = 10	v2 = 10	v3 = 9	v4 = 14	v5 = 0
u1 = – 2
u2 = 0
u3 = – 1

Рассчитаем оценки свободных клеток

, , , , , , , .

План снова не оптимальный. Нужно сделать максимально возможную поставку в единственную клетку с отрицательной оценкой (3; 4). Находим цикл, начиная из этой клетки. Это будет цикл (3; 4), (3; 2), (2; 2), (2; 4), (3; 4). Расставляем знаки

	v1 = 10	v2 = 10	v3 = 9	v4 = 14	v5 = 0
u1 = – 2
u2 = 0		+ 10		– 14
u3 = – 1		– 9		+ 12

Среди клеток, помеченных знаком «–» минимальная поставка – 20. Так же как в прошлый раз, прибавляем и вычитаем эту величину из поставок в помеченных клетках в соответствии со знаком. Рассчитываем вновь потенциалы.

	v1 = 10	v2 = 10	v3 = 8	v4 = 14	v5 = 0
u1 = – 2
u2 = 0
u3 = – 2

Тогда оценки свободных клеток будут иметь вид

, , , , , , , .

Так как все оценки не отрицательные, то план оптимальный. Запишем ответ:

- первый поставщик везет первому потребителю 50 единиц груза;

- второй поставщик везет второму потребителю 40 единиц груза, четвертому потребителю 20 единиц и 10 единиц груза у него остается на складе (пятого потребителя не существует);

- третий поставщик везет третьему потребителю 70 единиц груза, а четвертому потребителю – 20.

Литература

1. Акулич И.Л. Математическое программирование в примерах и задачах: Учебное пособие.2-е изд. – СПб [и др.]: Лань, 2009. – 352с.

2. Кузнецов А.В. Высшая математика: математическое программирование: учебник/Кузнецов А.В., Сакович В.А., Холод Н.И.; Кузнецов А.В. (общ. ред.). – СПб [и др.]: Лань, 2010. – 351с.

3. Таха Х. Введение в исследование операций, 7-е издание. Пер. с англ.- М.: Издательский дом «Вильямс», 2005.- 912с.

4. Шапкин А.С., Мазаева Н.П. Математические методы и модели исследования операций: Учебник. – М.: Издательско-торговая корпорация «Дашков и К◦», 2004. – 400с.

5. Элементы линейного программирования: Методические указания/ Рольщиков В.Е. – Челябинск: Челябинский государственный университет, 2000. 50с.

6. Введение в сетевые методы: Методические указания/ Рольщиков В.Е. – Челябинск: Челябинский государственный университет, 2000. 21с.

1. Морозов В.В., Сухарев А.Г., Федоров В.В. Исследование операций в задачах и упражнениях. М.: Высш. шк., 1986. 287с.

2. Калихман И.Л., Войтенко М.А. Динамическое программирование в примерах и задачах. М.: Высш.шк., 1979. 124с.

3. *Костевич Л.С., Лапко А.А. Теория игр. Исследование операций. Минск: Вышейш. шк., 2008. – 368с.

Дата добавления: 2014-12-27