2018-03-09
138
Пусть исходные данные задачи занесены в таблицу (табл. 4.1). Наиболее простым из методов построения допустимого исходного базисного решения является метод северо-западного угла.
Таблица 4.1
| bk аi | b1 | b2 | ... | bk | ... | bq | ||||||
| a1 | c11 |
| c12 | ... | c1k | ... | c1q | |||||
| x11 |
| x12 | x1k | x1q | ||||||||
| a2 |
| c21 | c22 | ... | c2k | ... | c2q | |||||
| x21 | x22 |
| x2k | x2q | ||||||||
| .... | .... |
| .... |
| .... | ||||||
| аi |
| ci1 |
| ci2 | ... | cik | ... | ciq | ||||
| xi1 | xi2 | xik | xiq | |||||||||
|
| .... |
|
|
| .... | ||||||
| аp |
| cp1 |
| cp2 | ... | cpk | ... | cpq | ||||
| xp1 | xp2 | xpk | xpq | |||||||||
Заполним таблицу, начиная с левого верхнего угла, двигаясь далее или по строке вправо, или по столбцу вниз. В клетку (1, 1) занесем меньшее из чисел а1 и b1, т.е. x11 = min{ а1, b1 }.
Если а1 > b1, то x11 = b1 и первый столбец «закрыт», т.е. потребности первого потребителя удовлетворены полностью. Двигаемся далее по первой строке, записывая в соседнюю клетку (1, 2) меньшее из чисел а1 - b1 и b2, т.е.. x12 = min{ а1 - b1, b2 }.
|
|
|
Если же b2 > a1, то аналогично «закрывается» первая строка и далее переходим к заполнению соседней клетки (2, 1), куда заносим x21 = min{ а2, b1-a1 }. Будем продолжать этот процесс до тех пор, пока на каком-то этапе не исчерпываются ресурсы ар и потребности bq.
Число базисных переменных транспортной задачи равно рангу системы уравнений (4.1), (4.2): r = p + q - 1. Значит, мы должны заполнить p + q – 1 клеток таблицы. Метод северо-западного угла дает допустимое базисное решение, если на каждом шаге заполнения из рассмотрения выпадает или одна строка, или один столбец.
Иногда на некотором шаге из рассмотрения выпадают одновременно и строка и столбец. Допустим, что после заполнения клетки (i, k) из рассмотрения выпадает i -ая строка и k -ый столбец. Для того чтобы получаемое распределение перевозок было допустимым, следует поместить фиктивную (нулевую) перевозку или в клетку (i+ 1, k), или в клетку (i, k+ 1).
Допустимое базисное решение, достаточно близкое к оптимальному, можно построить с помощью метода минимальной стоимости.
Сначала заполняется клетка таблицы, соответствующая минимальной стоимости 
, и исключается из рассмотрения только одна строка или один столбец. Остальные клетки заполняют аналогично методу северо-западного угла. Поставщик исключается из рассмотрения, если его ресурсы использованы полностью. Потребитель исключается из рассмотрения, когда его запросы полностью удовлетворены. На каждом шаге исключается либо один поставщик, либо один потребитель. При этом если поставщик еще не исключен, но его запасы равны нулю, то на том шаге, когда требуется поставить груз от данного поставщика, в соответствующую клетку таблицы записывают базисный нуль, и лишь затем поставщик исключается из рассмотрения. Аналогично поступают и с потребителем.
|
|
|
