Фирма «Три Толстяка» занимается доставкой мясных консервов с трёх складов

Записываем исходные данные задачи (табл. 2.2):
Таблица 2.3 – Исходные данные
A\B 300 500 200
700 3 5 1
200 7 2 3
100 4 3 1
Целевая функция:
.
– вектор запасов поставщиков (склады №1, №2, №3),
– вектор запросов потребителей (магазины №1, №2, №3).
Проверяем выполнение необходимого и достаточного условия разрешимости задачи. Находим суммарные запасы поставщиков и суммарные запросы потребителей:
;
.
Так как имеем задачу с правильным балансом.
Находим начальное опорное решение методом северо-западного угла (табл. 2.3).
Таблица 2 3 – Опорное решение. 1-й шаг метода потенциалов
A\B 300 500 200
700 3
300 5
400 [-] 1
[+]
200 7
2
100 [+] 3
100 [-]
100 4
3
1
100
Значение целевой функции на данном опорном решении:
.
Решаем задачу методом потенциалов.
Для проверки оптимальности опорного решения находим потенциалы . Записываем систему уравнений для нахождения потенциалов. Система состоит из 5 уравнений и имеет 6 неизвестных. Система неопределённая. Одному из потенциалов задаём значение произвольно: пусть u1 = 0. Получаем:
Проверяем опорное решение на оптимальность. Для этого вычисляем оценки для всех незаполненных клеток таблицы:
;
;
;
.
Полученное опорное решение не является оптимальным, т.к. имеются положительные оценки.
Шаг 1.
Переходим к новому опорному решению. Для клетки (1, 3) строим цикл (табл. 2.3). Осуществляем сдвиг по циклу на величину