Решение
1. Проверим условие разрешимости транспортной задачи:
; 
.
Таким образом, ТЗ закрытая и, следовательно, имеет оптимальное решение.
2. Запишем математическую модель ТЗ.
Обозначим через 
количество перевезенного груза из 
(
) в 
(
), при этом 
. Составим систему ограничений:
условия вывоза груза 
условия доставки груза 
Суммарные затраты на перевозку груза равны
.
Требуется найти такое неотрицательное решение 
системы ограничений, при котором функция 
принимает наименьшее значение.
3. Построим исходный план перевозок методом «минимального элемента».
Последовательность заполнения клеток в распределительной таблице следующая: (2,1), (1,4), (3,3), (3,4), (3,2), (2,2).
Таблица 28
| Потенциалы | |||||
| 
| 
| 
| ||
|
| |||||
Потребности в грузе
100
400
100- 
600
В плане перевозок 
число заполненных клеток равно m + n –1 = 3+4–1 = 6. Транспортные расходы составляют 
.
4. Методом потенциалов проверим план перевозок на оптимальность.
Найдем потенциалы 
и 
из системы уравнений, составленных для заполненных клеток:
В системе 6 уравнений, что меньше числа неизвестных 
, поэтому система имеет бесконечное множество решений, а число свободных неизвестных равно 7 – 6 = 1. Придадим неизвестной (она чаще всего встречается в системе) произвольное значение 
. Тогда остальные потенциалы равны:
; 
; 
; 
; 
; 
; 
.
Вычислим оценки, соответствующих свободным клеткам:
| D11 = с 11 + a1 – b1 = 3 + 1 – 0 = 4; | D12 = с 12 + a1 – b2 = 6 + 1 – 3 = 4; |
| D13 = с 13 + a1 – b3 = 5 + 1 – 1 = 5; | D23 = с 23 + a2 – b3 = 3 –1 – 1 = 1; |
| D24 = с 24 + a2 – b4 = 2 – 1 – 2 = – 1; | D31 = с 31 + a3 – b1 = 4 + 0 – 0 = 4. |
Оценка 
, поэтому план перевозок 
не оптимален, т.е. транспортные расходы не являются наименьшими.
5. Улучшим план перевозок.
Построим в таблице 28 цикл для клетки (2,4): (2,4), (2,2), (3,2), (3,4). Припишем знаки «+» и «–» вершинам цикла, начиная с «+» в клетке (2,4), последовательно чередуя знаки. Найдем число 
(для отрицательных клеток). Переместим по циклу: вычтем 100 из значений отрицательных клеток и прибавим 100 к значениям положительных. В результате клетка (2,4) стала занятой, 
, а две клетки (2,2) и (3,4) освободились.
| Запасы груза |
Потребности в грузе | |||
| 300 | 500 | 100 | 200 | |
|
100 | 3 | 6 | 5 | 1 |
| 100 | ||||
|
400 | 1 |  4
| 3 | 2 |
| 300 | 100 | |||
|
600 | 4 | 3 | 1 | 2 |
| 400 | 100 | 100 | ||
В новом плане перевозок заполненных клеток 5, а должно быть 6. Из двух освободившихся клеток (3,4) и (2,2) заполним базисным нулем клетку (3,4), так как ей соответствует меньшая стоимость перевозок 
, а клетку (2,2) оставим свободной.
|
Запасы груза |
Потребности в грузе | |||
| 300 | 500 | 100 | 200 | |
|
100 | 3 | 6 | 5 | 1 |
| 100 | ||||
|
400 | 1 | 4 | 3 | 2 |
| 300 | 100 | |||
|
600 | 4 | 3 | 1 | 2 |
| 500 | 100 | 0 | ||
Получим новый план перевозок 
, для которого транспортные расходы равны
.
6. Проверим план перевозок 
на оптимальность.
Найдем потенциалы и из новой системы уравнений, составленных для заполненных клеток таблицы 30: 
При получим одно из решений этой системы:
a1 = 1, a2 = 0, a3 = 0, b1 = 1, b2 = 3, b3 = 1, b4 = 2.
Все оценки свободных переменных положительны:
| D11 = с11 + a1 - b1 = 3 + 1 – 1 = 3; | D12 = с12 + a1 - b2 = 6 + 1 – 3 = 4; |
| D13 = с13 + a1 - b3 = 5 + 1 – 1 = 5; | D23 = с23 + a2 - b3 = 3 + 0 – 1 = 2; |
| D22 = с22 + a2 - b2 = 4 + 0 – 3 = 1; | D31 = с31 + a3 - b1 = 4 + 0 –1 = 3. |
Отсутствие отрицательных оценок является признаком оптимальности плана перевозок 
, при котором значение целевой функции минимально и равно 
.
7. Дадимэкономическое истолкование оптимального решения.
Для того чтобы затраты на перевозку груза из пунктов 
, 
, 
были наименьшими и составляли 2200, нужно отправить: 1) 100 ед. груза из в 
; 2) 300 ед. груза из в 
и 100 ед. из в ; 3) 500 ед. груза из в 
и 100 ед. груза из в 
.
Задачи для самостоятельного решения
Задача 1. Дана распределительная таблица транспортной задачи.
Таблица 31
|
Запасы груза
| Потребности в грузе | |||
| 10 | 11 | 8 | 6 | |
| 12 | 10 | 3 | 5 | 8 |
| 5 | 5 | 7 | 6 | 4 |
| 18 | 1 | 4 | 3 | 7 |
Построить в данной распределительной таблице планы перевозок методами "северо-западного угла" и "минимального элемента". Вычислить значения транспортных расходов для этих планов, считая, что элементы 
внутри клеток - тарифы на перевозку единицы груза из пункта 
в пункт 
. Сравнить полученные планы по критерию наименьших общих транспортных расходов.
Задача 2. Решить транспортную задачу методом потенциалов.
Условия транспортной задачи представлены в распределительной таблице.
1. Проверить, является ли транспортная задача закрытой.
2. Построить математическую модель задачи.
3. Построить в распределительных таблицах планы перевозок методами «северо-западного угла» и «минимального элемента».
4. Вычислить значения транспортных расходов для этих планов перевозок, считая, что элементы 
- тарифы на перевозку единицы груза из пункта в пункт 
.
5. Найти оптимальный план перевозок методом потенциалов.
1. Таблица 32
| Запасы груза | Потребности в грузе | ||||
| 70 | 40 | 30 | 60 | 50 | |
| 80 | 4 | 2 | 5 | 7 | 6 |
| 50 | 7 | 8 | 3 | 4 | 5 |
| 120 | 2 | 1 | 4 | 3 | 2 |
2. Таблица 33
| Запасы груза | Потребности в грузе | ||
| 40 | 30 | 40 | |
| 50 | 3 | 1 | 5 |
| 60 | 1 | 2 | 3 |
3. Таблица 34
| Запасы груза | Потребности в грузе | |||
| 30 | 60 | 10 | 20 | |
| 20 | 3 | 6 | 5 | 1 |
| 40 | 1 | 4 | 3 | 2 |
| 60 | 4 | 3 | 1 | 2 |
|
| Поделиться: |
