Методическое пособие для выполнения контрольной работы по дисциплине
Метод потенциалов нахождения оптимального плана транспортной задачи
жүктеу/скачать 0.49 Mb.
|
| Метод потенциалов нахождения оптимального плана транспортной задачи
Для закрытой транспортной задачи в опорном плане заняты n+m-1 клетка. Полученный опорный план надо проверить на оптимальность. Ответ на этот вопрос дает следующая теорема. Теорема: Если для некоторого опорного плана транспортной задачи x*=(x*ij) (i=1,m; j=1,n) существуют числа ά1, ά2,…, άm и β1, β2,…, βn, такие что βj- άi =cijпри xij>0 βj- άi =cijпри xij=0 для всех значений i и j , то план x* =(x*ij) является оптимальным планом транспортной задачи. Числа άi (i=1,m) и βj (j=1,n) называются потенциалами пунктов назначения и пунктов потребления, соответственно. Эти числа находят из системы уравнений: βj- άi =cij, где cij- тарифы в заполненных клетках опорного планаТ3. Число уравнений в системе равно n+m-1, а число неизвестных n+m. Одно из неизвестных (пусть ά1) полагают равным нулю и находят все потенциалы. Для свободных клеток определяют αij=βj-αi-cij. Если все άij ≤ 0 , то план является оптимальным. Если существует άij> 0 , то находят из этих чисел maxάij. Заполняют эту клетку, а объемы в ряде других занятых клеток изменяют. Определение. Циклом в таблице условий Т3 называетсязамкнутая ломаная линия, вершины которой расположены в занятых клетках таблицы, а звенья ломаной линии – вдоль строк и столбцов, причем в каждой вершине встречаются άij только два звена.
Рис. Примеры циклов в таблице транспортной задачи При правильном построении опорного плана для любой свободной клетке можно построить только один цикл (Рис. ). Правило перемещения грузов по циклу: - каждой из клеток цикла, связанной с данной свободной клеткой, приписывают определенный знак: свободной клетке «+», остальным – по очереди «-»/ «+», при этом направление обхода не имеет значения, т.к. вершин в цикле всегда четное число; - среди минусовых клеток находят minxij. Это число прибавляют ко всем “плюсовым” клеткам и вычитают из всех “минусовых” клеток. Таким образом, клетка, ранее свободная, становится занятой; а “минусовая” клетка с minxijстанет свободной. Алгоритм метода потенциалов: имеется опорный план с (n+m-1)-ой заполненной клеткой; составляют систему уравнений для всех заполненных клеток; из полученной системы уравнений определяют и ; вычисляют потенциал для каждой свободной клетки ; если , то план будет оптимальным; в противном случае среди положительных значений находят max{ }; осуществляют сдвиг по циклу (пересчет поставок); переходят к пункту 2. В качестве примера оптимизации методом потенциалов рассмотрим опорный план предыдущей задачи, полученный по методу Фогеля. Составляем систему уравнений для потенциалов по всем заполненным клеткам: Пусть , тогда из уравнений (1) и (2) получаем , далее из уравнения (6) , из (5) , из (4) , из (3) . Представляя потенциалы как векторы, имеем ; . Вычислим вспомогательные величины для незаполненных клеток: . Так как для всех свободных клеток полученные значения отрицательны, следовательно, данный план является оптимальным. Теперь применим оптимизации методом потенциалов к опорному плану, полученному по методу минимального элемента: Для заполненных клеток составляем систему уравнений: . Положив , последовательно получаем , , , , , . Или в виде векторов ; . Вычисляем коэффициенты для незаполненных клеток: ; ; ; ; ; . Среди полученных значений существует положительное , что свидетельствует о неоптимальности данного плана. Составляем цикл для свободной клетки A1B4: A1B4→ A3B4→ A3B3→ A1B4. Припишем клеткам этого цикла знаки по очереди и , начиная со свободной клетки. Выпишем объемы перевозок среди минусовых клеток (90 и 160) и найдем минимальное значение (90). Из всех минусовых клеток вычтем это значение, а ко всем плюсовым клеткам прибавим это значение: 90-90=0, 160-90=70, 0+90=90, 30+90=120. Итак, получим новый план:
Для заполненных клеток составим систему уравнений: . Положив α1=0, получим β3=1, β4=2, β2=0, α3=-2, β1=-2. α2=-6 или в форме векторов ) и . Вычислим значения вспомогательных величин для свободных клеток: Так как существует положительное значение для клетки A2B2, то имеется возможность улучшения полученного плана. Дляклетки A2B2составимцикл: A2B2→ A3B2→ A3B3→ A1B3 → A1B4→ A2B4→ A2B2. Припишем клеткам этого цикла знаки по очереди и , начиная со свободной клетки. Выпишем объемы перевозок среди минусовых клеток (50, 70 и 20) и найдем минимальное значение (20). Из всех минусовых клеток вычтем это значение, а ко всем плюсовым клеткам прибавим это значение: 50-20=30, 70-50=20, 20-20=0, 0+20=20, 120+20=140, 90+20=110. Итак, получим новый план:
Данный план (опорный план по методу аппроксимации Фогеля) является оптимальным. Задание 3. На четыре базы A1, A2, A3, A4 поступил однородный груз в количествах, соответственно равных 30+m, 25, 15+2n и 30 единиц. Этот груз требуется перевезти в три пункта назначения B1, B2, B3 соответственно в количествах 40, 20+m+2n и 40 единиц. Тарифы перевозок единицы груза с каждого из пунктов отправления в соответствующие пункты назначения указаны в транспортной таблице.
Опорный план найти методом минимального элемента и оптимизировать методом потенциалов. жүктеу/скачать 0.49 Mb. Достарыңызбен бөлісу:
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||