КАТЕГОРИИ:
Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)
Метод минимального элемента (минимальной стоимости)
|
|
|
|
Метод минимальной стоимости прост, он позволяет построить опорное решение, достаточно близкое к оптимальному, так как использует матрицу стоимостей транспортной задачи 
Как и метод северо-западного угла, он состоит из ряда однотипних шагов, на каждом из которых заполняется только одна клетка таблицы, соответствующая минимальной стоимости 
, и исключаетсч из рассмотрения только одна строка (поставщик) или один столбец (потребитель). Очередную клетку, соответствующую , заполняют по тем же правилам, что и в методе северо-западного угла. Поставщик исключается из рассмотрения, если его запасы использованы полностью. Потребитель исключается из рассмотрения, если его запасы удовлетворены полностью. На каждом шаге исключается либо один поставщик, либо один потребитель. При этом если поставщик еще не исключен, но его запасы равны нулюЮ то на том шаге, корда от данного постащика требуется поставить груз, в соответствующую клетку таблицы заносится базисный нуль и лиш затем поставщик исключается из рассмотрения. Аналогично с потребителем.
Пример:
Имеется три поставщика А1,А2 и А3, а так же четыре потребителя В1,В2,В3 и В4. Количество груза, находящегося у поставщика, равно соответственно: 
Количество груза, необходимого потребителю Вj, равно соответственно: 
Данаматрица тарифов (издержек или транспортных расходов):
Решение:
Так как 
то данная задача – закрытого типа. Составим первоначальный опорный план двумя различными способами.
1. Способ северо-западного угла
Таблица 4.7
| В1 | В2 | В3 | В4 | 
| |
| A1 | |||||
| - | - | 60,20,0 | |||
| A2 | |||||
| - | 40,35,15 | ||||
| A3 | |||||
| - | - | - | 35,0 | ||
| bj | 40,0 | 25,5,0 | 20,0 | 50,35.0 |
X=
F=5*40+4*20+2*5+6*20+3*15+4*35=595(y.d.e)
2. Способ минимального элемента.
Таблица 4.8
| В1 | В2 | В3 | В4 |
| |
| A1 | |||||
| - | - | 60,40,0 | |||
| A2 | |||||
| - | 40,15,5 | ||||
| A3 | |||||
| - | - | - | 35,0 | ||
| bj | 40,35,0 | 25,0 | 20,0 | 50,10,0 |
X=
F=1*20+2*40+4*5+2*25+3*10+7*35=445(y.d.e)
Таким образом, опорный план, найденный способом минимального элемента, ближе к оптимальному, чем план, найденный способом северо-западного угла.
|
|
|
|
|
Дата добавления: 2014-01-04; Просмотров: 563; Нарушение авторских прав?; Мы поможем в написании вашей работы!