Пример
Экономическая модель
| 
| 
| 
| |
| ||||
| ||||
| ||||
| ||||
|
– это наличие товара у поставщика 
и 
;
– это наличие потребностей у потребителя 
и 
;
– это удельные затраты на перевозку товара от каждого -го поставщика, каждому -ому потребителю.
Математическая модель.
Определим неизвестные. За 
примем количество перевозимой продукции от каждого -го поставщика, каждому -ому потребителю.
– вывезти товара, не менее, чем есть;
– привезти не менее запросов потребителя.
; 
и 
Получили, что суммарный спрос равен суммарному предложению, значит данная транспортная задача является закрытого типа.
Получение начального (опорного) плана методом северо-западного угла
|
|
|
|
|
| ||||
|
| ||||||||
|
| ||||||||
|
| ||||||||
|
| ||||||||
|
| ||||||||
Поверим по формуле, получился ли вырожденный случай:
; 
(невырожденный случай).
Определим начальные (опорные) издержки:
;
Итерации по улучшению плана до получения оптимального решения.
Рассчитаем оценки пустых клеток:
; 
; 
;
; 
; 
;
; 
; 
;
; 
; 
;
Минимальная оценка в клетке (1,3). Сделаем перепоставку по контуру (23 из клетки 3,3 в клетку 1,3) и получим новый план поставки товара.
План после первой итерации
|
|
|
|
|
| ||||
|
| ||||||||
|
| ||||||||
|
| ||||||||
|
| ||||||||
|
| ||||||||
.
Снова рассчитаем оценки пустых клеток:
; 
; 
;
; 
; 
;
; 
; 
;
; 
.
Минимальная оценка в клетке (5,1). Сделаем перепоставку по контуру – это будет число 31 из клетки (1,1). Рассчитаем новый план поставки товара.
План после второй итерации
|
|
|
|
|
| ||||
|
| ||||||||
|
| ||||||||
|
| ||||||||
|
| ||||||||
|
| ||||||||
.
Снова рассчитаем оценки пустых клеток:
; 
; 
;
; 
; 
;
; 
; ;
; 
; .
Выбираем клетку (2,4). Сделаем перепоставку по контуру – это будет число 38 из клетки (2,1). Рассчитаем новый план поставки товара.
План после третьей итерации
|
|
|
|
|
| ||||
|
| ||||||||
|
| ||||||||
|
| ||||||||
|
| ||||||||
|
| ||||||||
.
Снова рассчитаем оценки пустых клеток:
; 
; ;
; 
; ;
; 
; 
;
; 
; .
Выбираем клетку (3,3). Сделаем перепоставку по контуру – это будет число 15 из клетки (5,3). Рассчитаем новый план поставки товара.
План после четвертой итерации
|
|
|
|
|
| ||||
|
| ||||||||
|
| ||||||||
|
| ||||||||
|
| ||||||||
|
| ||||||||
.
Снова рассчитаем оценки пустых клеток:
; ; 
;
; ; 
;
; 
; 
;
; ; 
;
Выбираем клетку (3,4). Сделаем перепоставку по контуру – это будет число 12 из клетки (5,4). Рассчитаем новый план поставки товара.
План после пятой итерации
|
|
|
|
|
| ||||
|
| ||||||||
|
| ||||||||
|
| ||||||||
|
| ||||||||
|
| ||||||||
.
Снова рассчитаем оценки пустых клеток:
; 
; 
;
; 
; ;
; ; ;
; ; 
.
Выбираем клетку (4,1). Сделаем перепоставку по контуру – это будет число 4 из клетки (3,1). Рассчитаем новый план поставки товара.
План после шестой итерации (оптимальный план перевозок)
|
|
|
|
|
| ||||
|
| ||||||||
|
| ||||||||
|
| ||||||||
|
| ||||||||
|
| ||||||||
.
Снова рассчитаем оценки пустых клеток:
; 
; 
;
; ; ;
; ; 
;
; 
; 
.
Как видно из расчетов все оценки положительные, т.е. не уменьшают издержки. Выбран оптимальный план перевозок 
.
Контрольные вопросы
1. Транспортная задача: постановка.
2. Транспортная задача: экономическая значимость.
3. Транспортная задача: условия существования решения.
4. Отличие транспортной задачи от общей задачи линейного программирования.
5. Как найти начальное решение транспортной задачи методом северо-западного угла?
6. Как решается транспортная задача методом минимальной стоимости?
7. Как решается транспортная задача методом потенциалов?
8. Построение замкнутого контура (цикла) при решении транспортной задачи.
9. Открытая и закрытая транспортная задача.
10. Приведение открытой транспортной задачи к закрытому типу.
Тесты
1. Что требуется определить в транспортной задаче?
а) такой план перевозок, чтобы все заявки не были выполнены, а общая стоимость всех перевозок была бы минимальна;
б) такой план перевозок, чтобы все заявки были выполнены, а общая стоимость всех перевозок была бы минимальна;
в) такой план перевозок, чтобы все заявки были выполнены, а общая стоимость всех перевозок была бы максимальна;
г) такой план перевозок, чтобы все заявки были не выполнены, а общая стоимость всех перевозок была бы максимальна;
д) содержание п. а и г.
2. Транспортные задачи являются одним из видов задач:
а) линейного программирования;
б) нелинейной оптимизации;
в) динамического программирования;
г) теории игр.
3. Система ограничений в транспортной задаче включает в себя:
а) уравнения баланса по поставщикам;
б) уравнения баланса по потребителям;
в) суммарное время перевозок;
г) п.п. а, б;
д) п.п. а-в.
4. Целевой функцией в транспортной задаче является:
а) суммарные транспортные издержки;
б) суммарное время перевозок;
в) длина маршрута перевозок.
5. Оценка пустой клетки показывает:
а) на сколько изменится значение целевой функции, после совершения единичной поставки в рассматриваемую клетку;
б) максимально возможную поставку в рассматриваемую клетку;
в) стоимость перевозки единицы товара.
6. Как решается транспортная задача:
а) методом потенциалов;
б) методом обратной матрицы;
в) методом «северо-западного угла».
7. Транспортная задача может быть
а) замкнутая;
б) закрытая;
в) обособленная.
8. Для нахождения опорного плана транспортной задачи применяется
а) метод скользящей средней;
б) метод потенциалов;
в) метод «северо-западного угла».
9. Сколько занятых клеток в транспортной таблице соответствует опорному плану перевозок:
а) n+m; б) n+m – 1; в) n+m+1.
10. Всегда ли для пустой клетки транспортной таблицы существует контур перепоставки?
а) да;
б) нет;
в) при соблюдении определенных условий.
Ответы к тестам
| 1) б | 6) а |
| 2) а | 7) б |
| 3) г | 8) в |
| 4) а | 9) б |
| 5) а | 10) а |
