Задачи для самостоятельного решения

Для данных транспортных задач (таблицы 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) составить начальные опорные решения методами северо-западного угла и минимальной стоимости и сравнить значения целевой функции.

В А                             Таблица 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 не учитываются.