Пример решения практической работы №5
Задача. В пунктах 
производится однородная продукция в количествах 
ед. Себестоимость единицы продукции в 
ом пункте равна 
. Готовая продукция поставляется в пункты 
, потребности которых составляют 
ед. Стоимости 
перевозки единицы продукции из пункта 
в пункт 
заданы матрицей [
] размера 3*4. Требуется:
. Установить пункты, в которых остаётся нераспределённая продукция, и указать её объём. Решение.
Транспортная задача (ТЗ) является открытой, так как 
, поэтому вводим фиктивного потребителя (n+1), при этом ci5=0 (
). Сведем исходные данные в таблицу 1.
Таблица 1 - Изначальные данные
|
|
|
|
|
| ||||
| ||||
|
Определяем начальное допустимое базисное решение (опорный план). Находим опорный план (ОП) по методу минимальной стоимости (таблица 2).
Таблица 2 - Начальный ОП
|
|
|
|
|
| |
| 450 | - | + - | 150 - | 150 | 0 |
| - | 200 | - | - | - | -4 |
| - | 100 | - 350 | 100 + | - | 1 |
| 1 | 7 | 9 | 3 | 0 |
Решаем ТЗ методом потенциалов для нахождения оптимального плана.
Находим число занятых клеток в начальном ОП:
m+n-1=3+5-1=7 → ОП является невырожденным (то есть число занятых клеток равно числу свободных; m – количество поставщиков, n – количество потребителей). Построим начальный опорный план: 
.
Определяем суммарные затраты на продукцию:
Определяем потенциалы занятых клеток (таблица 2): 
Считаем оценки свободных клеток таблицы 2:
S12=6-(7+0)=-1 S13=5-(9+0)=-4
S21=4-(1-4)=7 S23=5-(9-4)=0
S24=7-(3-4)=8 S25=0-(0-4)=4
S31=5-(1+1)=3 S35=0-(0+1)=-1
Так как есть отрицательные оценки, то ОП не является оптимальным. Переходим к его улучшению.
Для клетки (А1,В3) строим цикл перераспределения груза (таблица 2). Выбираем те клетки, в которых оценки отрицательные. Из них выбираем ту, которая имеет наименьшее абсолютное значение и для этой клетки, строим цикл: min {150, 350}=150. Найденное количество груза распределяем по циклу и данные заносим в таблицу 3.
Таблица 3 - Опорный план №1
|
|
|
|
|
| |
| 450 | - | + 150 | - | 150- | 0 |
| - | 200 | - | - | - | 0 |
| - | 100 | - 200 | 250 | - + | 5 |
| 1 | 3 | 5 | -1 | 0 |
Получаем следующий опорный план: 
Определяем суммарные затраты на продукцию:
.
Находим число занятых клеток в ОП X1: m+n-1=3+5-1=7 → ОП X1 является невырожденным.
Проверяем план Х1 на оптимальность. Определяем потенциалы занятых клеток (таблица 3):
Считаем оценки свободных клеток таблицы 3:
S12=6-(3+0)=3 S14=3-(-1+0)=4
S21=4-(1+0)=3 S23=5-(5+0)=0
S24=7-(-1+0)=8 S25=0-(0+0)=0
S31=5-(1+5)=-1 S35=0-(0+5)=-5
Так как есть отрицательные оценки, то ОП Х1 не является оптимальным. Переходим к его улучшению.
Для клетки (А3,В5) строим цикл перераспределения груза (таблица 3). Выбираем те клетки, в которых оценки отрицательные. Из них выбираем ту, которая имеет наименьшее абсолютное значение и для этой клетки, строим цикл: min {150, 200}=150. Таблица 4 - Опорный план №2
|
|
|
|
|
| |
| - 450 | - | + 300 | - | 0 | 0 |
| - | 200 | - | - | - | 0 |
| + - | 100 | - 50 | 250 | 150 | 5 |
| 1 | 3 | 5 | -1 | -5 |
Найденное значение груза перераспределяем по циклу и данные заносим в таблицу 4.
Получаем следующий опорный план: 
Определяем суммарные затраты на продукцию:
Находим число занятых клеток в ОП Х2:
m+n-1=3+5-1=7 → ОП Х2 является невырожденным.
Проверяем план Х2 на оптимальность.
Определяем потенциалы занятых клеток (таблица 4):
Считаем оценки свободных клеток таблицы 4:
S12=6-(3+0)=3 S14=3-(-1+0)=4
S15=0-(-5+0)=5 S21=4-(1+0)=3
S23=5-(5+0)=0 S24=7-(-1+0)=8
S25=0-(-5+0)=5 S31=5-(1+5)=-1
Так как есть отрицательные оценки, то ОП Х2 не является оптимальным. Переходим к его улучшению.
Для клетки (А3,В1) строим цикл перераспределения груза (таблица 4). Выбираем те клетки, в которых оценки отрицательные.
Таблица 5 - Опорный план №3
|
|
|
|
|
| |
| 400 | - | 350 | - | 0 | 0 |
| - | 200 | - | - | - | -1 |
| 50 | 100 | - | 250 | 150 | 4 |
| 1 | 4 | 5 | 0 | -4 |
Из них выбираем ту, которая имеет наименьшее абсолютное значение: min {450, 50}=50 и перераспределяем по циклу. Новый опорный план предоставлен в таблице 5.
Строим новый опорный план:
Определяем суммарные затраты на продукцию:
Находим число занятых клеток в ОП Х3:
m+n-1=3+5-1=7 → ОП Х3 является невырожденным.
Проверяем план Х3 на оптимальность.
Определяем потенциалы занятых клеток (таблица 5):
Считаем оценки свободных клеток таблицы 5:
S12 = 6-(4+0) =2 S23 = 5-(-1+5) = 1
S14 = 3-(0+0) = 3 S24 = 7-(-1+0) = 8
S15 = 0-(-4+0) = 4 S25 = 0-(-4-1) = 5
S21 = 4-(-1+1) = 4 S32 = 10-(5+4) = 1
План X3 – является оптимальным планом, так как нет отрицательных оценок, при этом единственным, так как нет оценок равных 0.
Начальное условие выполнено, продукция со склада 3(min себестоимость) полностью распределена.
Ответ: План перевозок продукции, при котором минимизируются суммарные затраты на её изготовление и доставку потребителям, при обязательном условии, что продукция пункта 3, в котором себестоимость её производства наименьшая, распределяется полностью равен X3; суммарные затраты 
=4800.
