| Страница: 1 из 2 <-- предыдущая следующая --> | Перейти на страницу: |
По дисциплине:"Методы оптимизации"
На тему:"Решение задач транспортного типа методом потенциалов "
 | | | | | | |
| ПН ПО | В1 | В2 | В3 | В4 | В5 | Запасы аi |
| А1 | 10 | 8 | 5 | 6 | 9 | 48 |
| А2 | 6 | 7 | 8 | 6 | 5 | 30 |
| А3 | 8 | 7 | 10 | 8 | 7 | 27 |
| А4 | 7 | 5 | 4 | 6 | 8 | 20 |
| Заявки bj | 18 | 27 | 42 | 12 | 26 | 125 |
Будем заполнять таблицу перевозками постепенно начиная с левой верхней ячейки ("северо-западного угла" таблицы). Будем рассуждать при этом следующим образом. ПунктВ1подал заявку на 18 единиц груза. Удовлетворим эту заявку за счёт запаса 48, имеющегося в пункте А1 , и запишем перевозку 18 в клетке (1,1). После этого заявка пункта В1 удовлетворена, а в пункте А1 осталось ещё 30 единиц груза. Удовлетворим за счёт них заявку пункта В2 (27 единиц), запишем 27 в клетке (1,2); оставшиеся 3 единицы пункта А1 назначим пункту В3. В составе заявки пункта В3 остались неудовлетворёнными 39 единиц. Из них 30 покроем за счёт пункта А2, чем его запас будет исчерпан, и ещё 9 возьмём из пункта А3. Из оставшихся 18 единиц пункта А3 12 выделим пункту В4; оставшиеся 6 единиц назначим пункту В5, что вместе со всеми 20 единицами пункта А4 покроет его заявку. На этом распределение запасов закончено; каждый пункт назначения получил груз, согласно своей заявки. Это выражается в том, что сумма перевозок в каждой строке равна соответствующему запасу, а в столбце - заявке. Таким образом, нами сразу же составлен план перевозок, удовлетворяющий балансовым условиям. Полученное решение является опорным решением транспортной задачи:
| | | | | | |
| ПН ПО | В 1 | В 2 | В 3 | В 4 | В 5 | Запасы а i |
| А 1 | 10 18 | 8 27 | 5 3 | 6 | 9 | 48 |
| А 2 | 6 | 7 | 8 30 | 6 | 5 | 30 |
| А 3 | 8 | 7 | 10 9 | 8 12 | 7 6 | 27 |
| А 4 | 7 | 5 | 4 | 6 | 8 20 | 20 |
| Заявки b j | 18 | 27 | 42 | 12 | 26 | 125 |
Составленный нами план перевозок, не является оптимальным по стоимости, так как при его построении мы совсем не учитывали стоимость перевозокСij.
Другой способ - способ минимальной стоимости по строке - основан на том, что мы распределяем продукцию от пунктаAiне в любой из пунктовBj,а в тот, к которому стоимость перевозки минимальна. Если в этом пункте заявка полностью удовлетворена, то мы убираем его из расчетов и находим минимальную стоимость перевозки из оставшихся пунктовBj.Во всем остальном этот метод схож с методом северо-западного угла. В результате, опорный план, составленный способом минимальной стоимости по строке выглядит, так как показано в таблице № 3.
При этом методе может получиться, что стоимости перевозокCijиCikот пунктаAiк пунктамBjиBkравны. В этом случае, с экономической точки зрения, выгоднее распределить продукцию в тот пункт, в котором заявка больше. Так, например, в строке 2:C21=C24, но заявкаb1больше заявкиb4, поэтому 4 единицы продукции мы распределим в клетку (2,1).
| | | | | | |
| ПН ПО | В1 | В2 | В3 | В4 | В5 | Запасы аi |
| А1 | 10 | 8 | 5 42 | 6 6 | 9 | 48 |
| А2 | 6 4 | 7 | 8 | 6 | 5 26 | 30 |
| А3 | 8 | 7 27 | 10 | 8 | 7 0 | 27 |
| А4 | 7 14 | 5 | 4 | 6 6 | 8 | 20 |
| Заявки bj | 18 | 27 | 42 | 12 | 26 | 125 |
Способ минимальной стоимости по столбцу аналогичен предыдущему способу. Их отличие состоит в том, что во втором способе мы распределяем продукцию от пунктовBiк пунктамAjпо минимальной стоимостиCji.
Опорный план, составленный способами минимальных стоимостей, обычно более близок к оптимальному решению. Так в нашем примере общие затраты на транспортировку по плану, составленному первым способомF0= 1039, а по второмуF0= 723.
Клетки таблицы, в которых стоят ненулевые перевозки, являютсябазисными. Их число должно равнятьсяm + n - 1.Необходимо отметить также, что встречаются такие ситуации, когда количество базисных клеток меньше чем m + n - 1. В этом случае распределительная задача называется вырожденной. И следует в одной из свободных клеток поставить количество перевозок равное нулю. Так, например, в таблице № 3:
| | | | | | |
| ПН ПО | В1 | В2 | В3 | В4 | В5 | Запасы аi |
| А1 | 10 | 8 27 | 5 21 | 6 | 9 | 48 |
| А2 | 6 18 | 7 | 8 12 | 6 | 5 | 30 |
| А3 | 8 | 7 | 10 9 | 8 12 | 7 6 | 27 |
| А4 | 7 | 5 | 4 | 6 | 8 20 | 20 |
| Заявки bj | 18 | 27 | 42 | 12 | 26 | 125 |
На этом способе уменьшения стоимости в дальнейшем и будет основан алгоритм оптимизации плана перевозок. Циклом в транспортной задаче мы будем называть несколько занятых клеток, соединённых замкнутой, ломанной линией, которая в каждой клетке совершает поворот на 90°.
Существует несколько вариантов цикла:
1.) 2.) 3.)
Нетрудно убедиться, что каждый цикл имеет чётное число вершин и значит, чётное число звеньев (стрелок). Условимся отмечать знаком + те вершины цикла, в которых перевозки необходимо увеличить, а знаком - , те вершины , в которых перевозки необходимо уменьшить. Цикл с отмеченными вершинами будем называть означенным. Перенести какое-то количество единиц груза по означенному циклу, это значит увеличить перевозки, стоящие в положительных вершинах цикла, на это количество единиц, а перевозки, стоящие в отрицательных вершинах уменьшить на то же количество. Очевидно, при переносе любого числа единиц по циклу равновесие между запасами и заявками не меняется: по прежнему сумма перевозок в каждой строке равна запасам этой строки, а сумма перевозок в каждом столбце - заявке этого столбца. Таким образом, при любом циклическом переносе, оставляющем перевозки неотрицательными допустимый план остаётся допустимым. Стоимость же плана при этом может меняться: увеличиваться или уменьшатся. Назовём ценой цикла увеличение стоимости перевозок при перемещении одной единицы груза по означенному циклу. Очевидно, цена цикла ровна алгебраической сумме стоимостей, стоящих в вершинах цикла, причём стоящие в положительных вершинах берутся со знаком + , а в отрицательных со знаком - . Обозначим цену цикла черезg.При перемещении одной единицы груза по циклу стоимость перевозок увеличивается на величинуg.При перемещении по немуkединиц груза стоимость перевозок увеличиться наkg.Очевидно, для улучшения плана имеет смысл перемещать перевозки только по тем циклам, цена которых отрицательна. Каждый раз, когда нам удаётся совершить такое перемещение, стоимость плана уменьшается на соответствующую величинуkg.Так как перевозки не могут быть отрицательными, мы будем пользоваться только такими циклами, отрицательные вершины которых лежат в базисных клетках таблицы, где стоят положительные перевозки. Если циклов с отрицательной ценой в таблице больше не осталось, это означает, что дальнейшее улучшение плана невозможно, то есть оптимальный план достигнут.
| Страница: 1 из 2 <-- предыдущая следующая --> | Перейти на страницу: |
| © 2007 ReferatBar.RU - Главная | Карта сайта | Справка |