Читайте также:
|
1. Исходный опорный план проверяется на условие "вырождения".
Согласно теореме Данцига количество занятых клеток в оптимальном плане не должно превышать суммарного числа строк и столбцов (суммы количества пунктов отправления и назначения):
Кз £ m + n – 1,
где Кз – число занятых клеток; m – число строк матрицы (пунктов отправления); n – число столбцов (пунктов назначения).
Естественно, этому же условию должен отвечать исходный опорный план. Если это условие не выполняется, то исходный опорный план составлен неверно.
Если Кз = m + n – 1, задача решается обычным порядком.
Если Кз < m + n – 1, задача называется "вырожденной" и распадается на несколько самостоятельных задач. Чтобы этого избежать, назначаются дополнительные фиктивные перевозки (перевозки равные 0).
В нашей задаче 9 < 4+7-1, задача является "вырожденной". Для устранения “вырождения” назначаем фиктивную перевозку в клетку на пересечении строки 2 и столбца 2 (табл. 7).
Таблица 7
| Станция Отправления | Избыток порожних вагонов | Станция назначения и недостаток порожних вагонов | ||||||
| B1=65 | B2=35 | B3=50 | B4=30 | B5=45 | B6=35 | B7=40 | ||
| А1 | ||||||||
| А2 | ||||||||
| А3 | ||||||||
| А4 |
2. Одной из строк присваивается произвольный потенциал. Удобнее всего начать со строки, имеющей наибольшее число занятых клеток, а величину потенциала выбрать больше, чем любое расстояние (или другой показатель критерия оптимизации) в матрице условий.
Таблица 8
| Станция Отправления | Избыток порожних вагонов | Станция назначения и недостаток порожних вагонов | Ui | ||||||
| B1=65 | B2=35 | B3=50 | B4=30 | B5=45 | B6=35 | B7=40 | |||
| А1 | |||||||||
| А2 | 46н2 | 37н3 | |||||||
| А3 | |||||||||
| А4 | |||||||||
| Vj |
Значение целевой функции составит:
L =40*65+36*35+35*0+40*10+38*40+43*25+34*5+37*45+28*35+41*40=11310
Проверка на оптимальность. План считается оптимальным, если соблюдаются следующие условия:
Vj - Ui Ј cij, при xij = 0 (клетка свободна),
Vj - Ui = cij, при xij > 0 (в клетке назначена перевозка).
В табл. 8 для клетки (1,3) 149 – 101 = 48 >46, т.е. нарушение в данной клетке составляет 2. Для клетки (2, 7) 141 – 101 = 410 >37, нарушение 3. Для остальных свободных и занятых клеток условия оптимальности выполняются. Так как в матрице перевозок имеются нарушения условий оптимальности, данный начальный опорный план не является оптимальным. Он может быть улучшен за счет клеток с нарушениями.
Таблица 9
| Станция Отправления | Избыток порожних вагонов | Станция назначения и недостаток порожних вагонов | Ui | ||||||
| B1=65 | B2=35 | B3=50 | B4=30 | B5=45 | B6=35 | B7=40 | |||
| А1 | 41 | ||||||||
| А2 | 37н1 | ||||||||
| А3 | |||||||||
| А4 | |||||||||
| Vj |
Значение целевой функции составит:
L =40*65+36*35+46*0+40*10+38*40+43*25+34*5+37*45+28*35+41*40=11310
| Станция Отправления | Избыток порожних вагонов | Станция назначения и недостаток порожних вагонов | Ui | ||||||
| B1=65 | B2=35 | B3=50 | B4=30 | B5=45 | B6=35 | B7=40 | |||
| А1 | |||||||||
| А2 | |||||||||
| А3 | |||||||||
| А4 | |||||||||
| Vj |
Полученный новый план перевозок (табл.10) имеет конечное значение целевой функции:
L =40*65+36*35+46*0+40*10+38*40+43*25+34*5+37*45+28*35+41*40=11310
Условие “вырождения” выполняется. После присвоения потенциалов всем столбцам и строкам новой матрицы (табл.10) нарушений условия оптимальности нет, значит данный план перевозок является оптимальным.
Дата добавления: 2015-11-30; просмотров: 77 | Нарушение авторских прав