Математическая модель.

Определим неизвестные. За примем количество перевозимой продукции от каждого -го поставщика, каждому -ому потребителю.

– вывезти товара, не менее, чем есть;

– привезти не менее запросов потребителя.

; и

Получили, что суммарный спрос равен суммарному предложению, значит данная транспортная задача является закрытого типа.

Получение начального (опорного) плана методом северо-западного угла

Поверим по формуле, получился ли вырожденный случай:

; (невырожденный случай).

Определим начальные (опорные) издержки:

;

Итерации по улучшению плана до получения оптимального решения.

Рассчитаем оценки пустых клеток:

; ; ;

; ; ;

; ; ;

; ; ;

Минимальная оценка в клетке (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) а