Транспортная задача (1 а л.) 1 Определение транспортной модели
Определение начального допустимого решения
жүктеу/скачать 0.49 Mb.
|
- Бұл бет үшін навигация:
- Метод минимальных элементов
| 3.2.1 Определение начального допустимого решения
Метод северо-западного угла. Сущность данного метода состоит в том, что начальное решение находят последовательно за (m+n-1) шагов, на каждом из которых в таблицу условий задачи заполняют одну клетку, которую при этом называют занятой. Заполнение одной из клеток обеспечивает полностью либо удовлетворяет потребности в грузе одного из пунктов назначения, либо вывоз груза из одного из пунктов отправления. По этому правилу переменной х11, находящейся в северо-западном углу таблицы, приписывается максимальное значение, допускаемое ограничениями на спрос и объем производства. После этого вычеркивается столбец или строка, запас которой исчерпан полностью. Остальные переменные столбца или строки равны 0. Если ограничения строки и столбца выполняются одновременно, то вычеркивается, либо столбец, либо строка. При этом очередная базисная переменная будет равна 0. В не вычеркнутой строке или столбце надо скорректировать величину объема производства или спроса. После этого максимально допустимое значение приписывается первому, не вычеркнутому элементу нового столбца или строки. Данный процесс продолжается до заполнения всей таблицы. Метод северо-западного угла всегда обеспечивает заполнение (m+n-1) клеток транспортной таблицы, а значит, получение опорного базисного решения. Метод минимальных элементов. Суть метода состоит в том, что в матрице стоимостей С = {сij} выбирается стоимость минимальной перевозки сij. Затем назначается максимальный объем ресурса от производителя i к потребителю j для данной перевозки. При этом возможны три варианта: производитель i имеет ресурса больше, чем надо потребителю j. В этом случае удовлетворяется полностью заявка потребителя j, а остаток произведенного ресурса будет распределен после. Так как потребность потребителя j удовлетворена полностью, то исключается из рассмотрения столбец матрицы стоимости, принадлежащий j-му потребителю; производитель i имеет ресурса меньше, чем надо потребителю j. В этом случае весь имеющийся ресурс производителя i назначается потребителю j. Недостающая часть ресурса потребителю j будет назначена потом. Так как весь ресурс производителя i исчерпан полностью, то из рассмотрения удаляется строка матрицы стоимости, принадлежащая производителю j; производитель i имеет ресурса столько, сколько надо потребителю у. В этом случае, аналогично рассмотренным выше случаям, из рассмотрения удаляются и строка, и столбец матрицы стоимости. Затем из матрицы стоимостей выбирается следующая минимальная стоимость перевозки ресурса от производителя к потребителю, удовлетворяются потребности следующего потребителя ресурса (полностью или частично) и удаляется из рассмотрения очередная строка или столбец матрицы стоимостей. Процесс повторяется до тех пор, пока не будет распределен полностью весь произведенный ресурс между всеми потребителями. Так как ресурса произведено ровно столько, сколько нужно потребителям, то задача распределения будет обязательно выполнена. жүктеу/скачать 0.49 Mb. Достарыңызбен бөлісу:
|