Материалы сайта
Это интересно
Решение транспортной задачи методом потенциалов
Новосибирска государственная академия водного транспорта Якутский филиал Курсовая работа по дисциплине исследование операций на тему: "Решение транспортных задач методом потенциалов" Выполнил: студент 4-го ОП курса Куклин А.Б. шифр ОП – 97 – 102 Проверил: Семёнов М.Ф. г. Якутск 2000 год Содержание. 1. Линейная транспортная задача - 3 стр. 2. Метод потенциалов - 6 стр. 3. Список использованной литературы - 14 стр. Транспортная задача. 1. Линейная транспортная задача. Линейные транспортные задачи составляют особый класс задач линейного программирования. Задача заключается в отыскании такого плана перевозок продукции с m складов к n который потребовал бы минимальных затрат. Если потребитель j получает единицу продукции (по прямой дороге) со склада i, то возникают издержки р i j . Предполагается, что транспортные расходы пропорциональны перевозимому количеству продукции, т.е. перевозка k единиц продукции вызывает расходы k р i j. Далее, предполагается, что [pic] 1 где bi есть количество продукции, находящееся на складе i, и aj – потребность потребителя j. Замечание. Если [pic]то количество продукции, равное [pic]остается на складах. В этом случае мы введем "фиктивного" потребителя n +1 с потребностью [pic] и положим транспортные расходы pi,n+1 равными 0 для всех i. Если [pic]то потребность на может быть покрыта. В этом случае начальные условия должны быть изменены таким образом, чтобы потребность в продукции могла быть обеспечена. Обозначим через xij количество продукции, поставляемое со склада i потребителю j. В предложении (1) нам нужно решить следующую задачу: [pic] 2 [pic] [pic] [pic] [pic] Транспортную задачу мы можем характеризовать транспортной таблицей и таблицей издержек: | |а1 |… |аn | |b1 |. | | | | | | |. | | | | | | | |. | | | | | | | |. | | | | | | | |bm | | | | | | | | | |. | | | | | | | | |. | | | | | | | | |. | | | | | | | | |. | | | | | | | | |. | |p11 |… |p1n | |. | |. | |. | |. | |. | |. | |pm1 |… |pmn | Допустимый план перевозок будем представлять в виде транспортной таблицы: | |а1 |… |аn | |b |[pic][pic] |… |[pic] | |. | | | | |. | | | | |. | | | | |bm | | | | | |. | |. | | |. | |. | | |. | |. | | |[pic] |… |[pic] | Cумма элементов строки i должна быть равна bi, а сумма элементов столбца j должна быть равна aj, и все [pic][pic]должны быть неотрицательными. Пример 1. | |20 |5 |10 |10 |5 | |15 | | | | | | |15 | | | | | | |20 | | | | | | |5 |6 |3 |5 |9 | |6 |4 |7 |3 |5 | |2 |5 |3 |1 |8 | Мы получаем следующую задачу: х11+х12+х13+х14+х15 =15, х21+х22+х23+х24+х55 =15, х31+х32+х33+х34+х35 =20, х11 +х21 +х31 =20, х12 +х22 +х32 =5, х13 +х23 +х33 =10, х14 +х24 +х34 =10, х15 +х25 +х35 =5; хij [pic] 0 для i = 1,2,3; j = 1,2,3,4,5; Кmin=5х11+6х12+3х13+5х14+9х15+6х21+4х22+7х23+3х24+5х25+2х31+5х32+3х33+х34+ 8х35; Такие задачи целесообразно решать при помощи особого варианта симплекс-метода – так называемого метода потенциалов. Все транспортные задачи имеют оптимальное решение. Если все значение aj и bi в условиях транспортной задачи целочисленные, то переменные xij во всех базисных решениях (а так же и в любом оптимальном базисном решении) имеют целочисленные значения. 2. Метод потенциалов. Пусть имеется транспортная таблица, соответствующая начальному решению, хil = [pic] для базисного решения переменных, хil = 0 для свободных переменных (ячейки, соответствующие свободным переменным, остаются пустыми). Далее, нам требуется таблица расходов с заданными pij (ниже мы постоянно будем ссылаться на пример 1). Отыскание симплекс множителей. Заполним таблицу расходов, оставив ячейки, соответствующие свободным переменным, пустыми. В крайний правый столбец внесем значения неизвестных u1,…,um, в нижнюю строку – значения неизвестных v1,…,vn, (см. рис. 1). Эти m + n неизвестных для всех (i, j), соответствующих базисным переменным, должны удовлетворять линейной системе уравнений ui + vj = pij. |pll | |plj | |pln |ul | | |. | |. | |. | | |… | |… | |. | | |. | |. | |. | |pil | |pij | |pin |ui | | |. | |. | |. | | |… | |… | |. | | |. | |. | |. | |pml | |pmj | |pmn |um | |vl | … |vj | … |vn | | Для всех базисных решений эта система имеет треугольный вид, ранг её матрицы равен n + m – 1. Следовательно, систему всегда можно решить следующим способом. Полагают vn = 0. Если значения k неизвестных [pic] определены, то в системе всегда имеется уравнение, одно из неизвестных в котором уже найдено, а другое ещё нет. Переменные ui и vj симплекс - множителями. Иногда они называются также потенциалами, а этот метод решения называют методом потенциалов. Пример 2. |5 | | | | |u1 | |6 |4 |7 | | |u2 | | | |3 |1 |8 |u3 | |v1 |v2 |v3 |v4 |v5 | | v5 = 0 ( u3 = 8, так как u3 + u5 = p35 = 8, ( v4 = -7, так как u3 + v4 = p34 = 1, ( v3 = -5, так как u3 + v3 = 3, ( u2 = 12 ( v2 = -8, ( v1 = -6 ( u1 = 11. Симплекс – множители нужны для того, чтобы найти свободную ячейку (i, j), которая при замене базиса переходит в базисную (это соответствует отысканию разрешающего столбца в симплекс – методе). Для определения симплекс – множителей мы вносим на свободные места в таблице значения p(ij = pij – ui – vj (коэффициенты целевой функции, пересчитанные для свободных переменных). Если все p(ij [pic] 0, то базисное решение оптимально. В противном случае мы выбираем произвольное p((( ( 0, чаще всего наименьшее. Индексом (( помечено свободное переменное х(( , которое должно войти в базис. Соответствующую ячейку транспортной таблицы мы отметим знаком +. Пример 3. |5 |6 |3 |5 |9 | |6 |4 |7 |3 |5 | |2 |5 |3 |1 |8 | pij: |5 | | | | |11 | | |6 |4 |7 | | |12 |( | | | |3 |1 |8 |8 | | |-6 |-8 |-5 |-7 |0 | | | | |5 |3 |-3 |1 |-2 | |( |6 |4 |7 |-2 |-7 | | |0 |5 |3 |1 |8 | Минимальный элемент –7 ( ((, () = (2,5). Кроме ячейки ((, () транспортной таблицы, мы пометим значками – и + другие занятые числами ячейки таким образом, чтобы в каждой строке и в каждом столбце транспортной таблицы число знаков + было равно числу знаков -. Это всегда можно сделать единственным образом, причем в каждой строке и в каждом столбце будет содержаться максимум по одному знаку = и по одному знаку -. Пример 4. |15 | | | | | | |5 |5 |5 | |+ |( | | | |5 |10 |5 | | | |15 | | | | | |( |5 |5 |5- | |+ | | | | |5+ |10 |5- | Знак + поставлен в ячейке (2,5). Соответственно в последнем столбце должен быть поставлен знак -, это можно сделать только в ячейке (3,5). Следовательно, знак + должен быть поставлен в последней строке. В ячейке с числом 10 этого сделать нельзя, так как тогда в соответствующем столбце не было бы знака -, и д.т. Затем мы определяем минимум М из всех элементов, помеченных знаком -, и выбираем ячейку ((, (), где этот минимум достигается. В нашем примере с М = 5 можно выбрать ((, () = (2, 3); при этом ((, () определяет базисное переменное, которое должно стать свободным, т.е. базисное переменное, соответствующее индексу разрешающей строки симплекс – метода. | |20 |5 |10 |10 |5 | |15 |15 | | | | | |15 |5 |5 |5- | |+ | |20 | | |5+ |10 |5- | ( |15 | | | | | |5- |5 | | |5+ | |+ | |10 |10 |0- | ( ( |15- | |+ | | | |5 |5 | | |5 | |0+ | |10- |10 | | ( |5 | |10 | | | |5- |5 | |+ |5 | |10+ | | |10- | | ( |5 | |10 | | | | |5 | |5 |5 | |15 | | |5 | | Копт = 150 Переход к новой транспортной таблице (замена базиса) происходит следующим образом: а). В ячейку ((, () новой таблицы записывается число М. б). Ячейка ((, () остается пустой. в). В других ячейках помеченных знаками – или +, число М вычитается из стоящего в ячейке числа (-) или складывается с ним (+). Результат вносится в соответствующую ячейку новой таблицы. г). Непомеченные числа переносятся в новую таблицу без изменений. Остальные ячейки новой таблицы остаются пустыми. Пример 5. |15 | | | | | | |5 |5 |5- | |+ |( | | | |5+ |10 |5- | | | |15 | | | | | |( |5 |5 | | |5 | | | | |10 |10 |0 | Получается новая транспортная таблица, и повторяется ход предыдущих рассуждений. После конечного числа шагов критерий минимальности будет выполнен (если не учитывать теоретически возможного зацикливания в случае вырождения). Пример 6. Ниже воспроизведен ход решения примера 1 из 1 главы. |5 |3 |-3 |1 |-2 |11 | |6 |4 |7 |-2 |-7 |12 | |0 |5 |3 |1 |8 |8 | |-6 |-8 |-5 |-7 |0 | | |5 |3 |4 |8 |5 |4 | |6 |4 |7 |5 |5 |5 | |-7 |-2 |3 |1 |8 |8 | |-1 |-1 |2 |0 |0 | | |5 |3 |-3 |1 |5 |4 | |6 |4 |0 |-2 |5 |5 | |2 |5 |3 |1 |7 |1 | |1 |-1 |2 |0 |0 | | |5 |3 |3 |1 |5 |4 | |6 |4 |3 |-2 |5 |5 | |2 |5 |3 |1 |7 |1 | |1 |-1 |-1 |0 |0 | | |5 |1 |3 |1 |3 |6 | |2 |4 |5 |3 |5 |5 | |2 |3 |3 |1 |5 |3 | |-1 |-1 |-3 |-2 |0 | | Первая транспортная таблица была получена в 1 главе (составление вспомогательной таблицы и второй транспортной таблицы описано выше). Затем по очередно находятся новая вспомогательная таблица и новая транспортная таблица до тех пор, пока (после четырех замен базисов) не будет достигнут минимум. В вырожденном случае, как и в симплекс – методе, особый метод для предотвращения зацикливания применяется только тогда, когда после нескольких последовательных шагов М становится равным 0. Если дана вырожденная транспортная таблица (её можно узнать по имеющемуся 0, то заменив am на am + n( и все bj на bj + ( , где ( ( 0 подразумевается очень малым, исправим значения [pic] базисных переменных так, что бы для новых ai и bj получилось базисное решение. Это всегда можно сделать единственным способом (как и при отыскании симплекс – множителей). |15 | | | | | |5 |5 | | |5 | | | |10 |10 |0 | | |20 + ( |5 + ( |10 + ( |10 + ( |5 + ( | |15 | | | | | | |15 | | | | | | |20 + ( | | | | | | |15 + 2( | | | | | |5 - ( |5 + ( | | |5 - 2( | | | |10 + ( |10 + ( |3( | Если полученный таким образом элемент [pic]окажется отрицательным, то в этой же строке должен найтись положительный (ещё до изменения) элемент [pic] и в этом же столбце – положительный элемент [pic]. Тогда ячейка (s, r) свободна, отмечаем её знаком + и проводим замену базиса. Так можно избавиться от всех отрицательных значений*[1]. Затем при помощи метода потенциалов расчеты продолжают дальше (вырождение уже никогда больше не встретится). Устремляя ( ( 0, приходим к оптимальному решению исходной задачи. Список использованной литературы: 1. Еремин И.И., Астафьев Н.Н. Введение в теорию линейного и выпуклого программирования М.; Наука, 1976г. 2. Карманов В.Г. Математическое программирование. – М.; Наука, 1986г. 3. Моисеев Н.Н., Иванов Ю.П., Столярова Е.М. Методы оптимизации. – М.; Наука, 1978г. 4. Иванов Ю.П., Лотов А.В. Математические модели в экономике. – М.; Наука, 1979г. 5. Бронштейн И.Н., Семендяев К.А. Справочник по математике. – М.; Наука, 1986г. ----------------------- [1] Часто бывает достаточно везде заменить ( на -(.