Научная электронная библиотека
Монографии, изданные в издательстве Российской Академии Естествознания
3.2. Нахождение исходного базисного решения
Для транспортной задачи итерационный процесс вычисления оптимального решения, как и в задачах линейного программирования, начинают с построения исходного базисного решения. Существуют несколько методов нахождение исходного базисного решения: северо-западного угла, минимальной стоимости, двойного предпочтения и др. [25]. Среди них наиболее предпочтительным является метод минимальной стоимости, а наиболее понятным и простым – метод минимальной стоимости. Метод минимальной стоимости позволяет находить исходное базисное решение более близкое к оптимальному решению и, следовательно, уменьшает число итераций. Алгоритм этого метода состоит из трех шагов.
Шаг 1. В таблице стоимостей (табл. 3.1) находят клетку с минимальной стоимостью
Если таких стоимостей несколько берется любой из них.
Шаг 2. В эту клетку помещают меньшее из чисел ai и bj. Затем из рассмотрения исключают либо строку, соответствующую поставщику, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку, и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя. В зависимости от этих условий меняют величину запаса поставщика или величину спроса потребителя.
Шаг 3. Проверяют удовлетворены ли все потребности. Если нет переход на шаг 1.
Шаг 4. Получено исходное базисное решение.
Применение метода минимальной стоимости покажем на следующем примере 3.1, исходные данные которого представлены в табл. 3.2.
Таблица 3.2
|
5 |
8 |
1 80 |
2 |
80 |
|
4 60 |
6 |
9 |
8 10 |
70 |
|
9 |
2 25 |
3 15 |
6 55 |
85 60 |
|
60 |
25 |
95 15 |
55 |
|
Здесь число пунктов отправления m = 3, а число пунктов назначения n = 4. Следовательно, базисное решение задачи определяется числами, стоящими в 4 + 3 – 1 = 6 заполненных клетках.
Шаг 1. Выбираем в таблице наименьшую стоимость c13 = 1.
Шаг 2. Так как a1 < b3 80 единиц продукции помещаем в эту клетку и исключаем из рассмотрения первую строку. Новое значение потребности b3 = 15. В оставшейся таблице стоимостей наименьшей является стоимость c32 = 2.
Так как b2 < a3, 25 единиц продукции помещаем в эту клетку и исключаем из рассмотрения второй столбец и корректируем величину запаса a3 = 85 – 25 = 60. В оставшейся таблице снова выбираем наименьшую стоимость и продолжаем процесс до тех пор, пока все запасы не будут распределены, а потребности удовлетворены. В результате получим исходное базисное решение:
Метод северо-западного угла. При нахождении начального базисного решения транспортной задачи методом северо-западного угла на каждом шаге рассматривают первый из оставшихся пунктов отправления и первый из оставшихся пунктов назначения. Заполнение клеток таблицы условий начинается с левой верхней клетки для неизвестного x11 («северо-западный угол») и заканчивается клеткой для неизвестного xmn, то есть идет как бы по диагонали таблицы.
Применение метода северо-западного угла покажем на следующем примере 3.2, исходные данные которого представлены в табл. 3.3 и совпадают с условиями примера 3.1.
Здесь также число пунктов отправления m = 3, а число пунктов назначения n = 4. Следовательно, базисное решение задачи определяется числами, стоящими в 4 + 3 – 1 = 6 заполненных клетках.
Таблица 3.3
|
5 60 |
8 20 |
1 |
2 |
80 |
|
4 |
6 5 |
9 65 |
8 |
70 |
|
9 |
2 |
3 30 |
6 55 |
85 |
|
60 |
25 |
95 |
55 |
|
Заполнение таблицы начинается с клетки для неизвестного x11 («северо-западный угол»). Необходимо удовлетворить потребности первого пункта назначения за счет запасов первого пункта отправления. Так как запасы первого пункта отправления больше, чем потребности первого пункта назначения, то x11 = 60 и это значение записывается в соответствующей клетке табл. 3.3 и временно исключается из рассмотрения первый столбец, и при этом запасы первого пункта отправления становятся равными 20. Далее по схеме северо-западного угла рассматриваются первые из оставшихся пунктов отправления и назначения. Оставшиеся запасы первого пункта (20) не покрывают потребности второго пункта назначения. Поэтому x12 = 20 и это значение записывается в соответствующей клетке табл. 3.3 и временно исключается из рассмотрения первая строка, так как запасы первого пункта отправления исчерпаны. Не удовлетворенные потребности второго пункта назначения уменьшаются до 5. Теперь заполняется клетка для неизвестного x22 и т.д.
В результате получим исходное базисное решение:
