Составьте математическую модель исходной задачи. 2. Найдите опорный план методом северо-западного угла. 3. Найдите оптимальный план

Составьте математическую модель исходной задачи. 2. Найдите опорный план методом северо-западного угла. 3. Найдите оптимальный план перевозок, используя метод потенциалов. База Магазины Запас продукции 7 21 5 15 17 220 14 12 13 6 23 150 10 17 11 9 20 130 Спрос на продукцию 90 160 70 100 80

1. Так как и равны между собой, то имеем закрытую (сбалансированную) модель транспортной задачи.
Пусть – матрица перевозок, где – объемы перевозок от -й базы к -му магазину.
Произведение определяет затраты на перевозку груза, тогда суммарные затраты на перевозку всех грузов равны: . Как правило, в транспортной задаче необходимо найти минимум суммарных затрат. Следовательно, целевая функция задачи имеет вид: или
Запасы всех складов должны быть полностью исчерпаны, т.е. или ; и .
Потребности всех потребителей должны быть полностью удовлетворены, т.е. или ; ; ; и .
Учитывая условие не отрицательности объемов перевозок, математическая модель выглядит следующим образом:
;
;
;
;
;
;
;
.
, , .
2. Определим начальное опорное решение методом cеверо-западного угла.
План начинается заполняться с верхнего левого угла. Искомый элемент равен 7. Для этого элемента запасы равны 220, потребности 90. Поскольку минимальным является 90, то оставляем: x11=min(220,90)=90. При этом запасы первой базы равны 220-90=130, а потребности первого магазина удовлетворены, x21=x31=0 (в транспортной таблице нулевые значения не пишем).
База Магазины Запас продукции

7[90] 21 5 15 17 130
14 12 13 6 23 150
10 17 11 9 20 130
Спрос на продукцию 0 160 70 100 80
Снова берем незаполненный элемент с верхнего левого угла. Искомый элемент равен 21. Для этого элемента запасы равны 130, потребности 160. Поскольку минимальным является 130, то оставляем: x12=min(130,160)=130

. При этом запасы первой базы исчерпаны, а потребности второго потребителя равны 160-130=30, x13=x14=x15=0.
База Магазины Запас продукции

7[90] 21[130] 5 15 17 0
14 12 13 6 23 150
10 17 11 9 20 130
Спрос на продукцию 0 30 70 100 80
Аналогичными рассуждениями приходим к начальному решению (плану):
База Магазины Запас продукции

7[90] 21[130] 5 15 17 0
14 12[30] 13[70] 6[50] 23 0
10 17 11 9[50] 20[80] 0
Спрос на продукцию 0 0 0 0 0
Запишем начальный опорный план в матричном виде:
Транспортные затраты (значение целевой функции) по этому плану равны:
.
3. Так как количество заполненных (не нулевых) ячеек последней транспортной таблицы равно 7, а должно быть , то – невырожденный план.
Проверим полученный начальный опорный план на оптимальность методом потенциалов.
База Магазины Запас продукции

7[90] 21[130] 5 15 17 220
14 12[30] 13[70] 6[50] 23 150
10 17 11 9[50] 20[80] 130
Спрос на продукцию 90 160 70 100 80
Для базисных (ненулевых) ячеек система потенциалов имеет вид :




Пусть , тогда
, ; ; , , ; ; .
Находим относительные оценки для свободных (нулевых) ячеек по формуле :




Не все относительные оценки , поэтому начальный опорный план можно улучшить. Для этого вводим в базис ячейку (1;3) (с наименьшей отрицательной относительной оценкой) при помощи цикла перерасчета.
База Магазины Запас продукции

7[90] –21[130] +5 15 17 220
14 +12[30] –13[70] 6[50] 23 150
10 17 11 9[50] 20[80] 130
Спрос на продукцию 90 160 70 100 80
Перерасчет проводим на величину .
Запишем полученный опорный план в матричном виде:
Транспортные затраты (значение целевой функции) по этому плану равны:
.
Так как количество заполненных (не нулевых) ячеек последней транспортной таблицы равно 7, а должно быть , то – невырожденный план