Для данных транспортных задач (таблицы 6.2.8, 6.2.9, 6.2.10, 6.2.11): построить начальные опорные решения методом северо-западного угла и методом минимальной стоимости; определить соответствующие значения целевой функции; сравнить значения целевой функции, полученные этими методами.
Таблица 6.2.8.
Таблица 6.2.11
Таблица 6.2.9
|
Таблица 6.2.10
|
Практическая работа № 7. «Транспортная задача. Открытая модель»
Цель работы:
Открытую модель необходимо сначала свести к закрытой, для чего вводится фиктивный поставщик (с запасами, равными разности между запасами и запросами) или фиктивный потребитель (с аналогично определяемыми запросами). Стоимости перевозок в соответствующих строке или столбце равны нулю, но в методе минимальной стоимости они учитываются в последнюю очередь. В ответе фиктивная строка (столбец) не учитывается.
Пример 7.1. Для предложенной транспортной задачи (таблица 7.1) составить начальные опорные решения методами северо-западного угла и минимальной стоимости и сравнить значения целевой функции.
| |
Решение. Прежде всего очевидно, что суммарные запасы равны 100, а суммарные запросы – 90. Поэтому необходимо ввести фиктивного потребителя, запросы которого равны 10 (это дополнительный столбец, значения стоимостей в котором будут равны 0) – см. таблицу 7.2, с которой начнем построение начального решения методом северо-западного угла. На первом шаге для ячейки (1;1) значения запасов и запросов одинаковы и равны 30, поэтому объема перевозок равен 30, вычеркиваем, например, строку (при этом запросы в соответствующем столбце становятся равными 0). На следующем шаге (см. таблицу 7.3) в ячейку (2;1) ставится значение объема перевозок 0 – как минимальное из чисел 0 и 20, при этом вычеркивается первый столбец.
Таблица 7.2.
Таблица 7.3.
|
Таблица 7.4.
|
Таблица 7.5.
|
Таблица 7.6.
| При получении таблиц 7.4-7.6 действовали по стандартной схеме. Занятыми оказались, как и положено, 5 клеток (3+3-1=5), остается найти значение целевой функции для найденного опорного решения:
|
Проведем теперь построение начального опорного решения методом минимальной стоимости (таблицы 7.7-7.11).
Таблица 7.7.
|
Таблица 7.8.
|
Таблица 7.9.
|
Таблица 7.10.
|
Таблица 7.11.
| Опять заняты 5 клеток, находим значение целевой функции для найденного опорного решения:
Замечание. При записи ответа (начального опорного решения) последние столбцы в таблицах 7.6 и 7.11 не учитываются.
|