На
Главную
ГДЗ:
Английский
язык Алгебра Геометрия Физика Химия Русский
язык Немецкий
язык
Подготовка к экзаменам (ЕГЭ) Программы и пособия Краткое содержание Онлайн учебники
Шпаргалки Рефераты Сочинения Энциклопедии Топики с переводами
Все темы:"Рефераты по Математике"
Решение транспортной задачи методом потенциалов .
Новосибирска государственная академия водного транспорта
Якутский филиал
Курсовая работа
по дисциплине исследование операций
на тему:
"Решение транспортных задач
методом потенциалов"
Выполнил: студент 4-го ОП курса
Куклин А.Б. шифр ОП – 97 – 102
Проверил: Семёнов М.Ф.
г. Якутск
2000 год
Содержание.
1. Линейная транспортная задача - 3 стр.
2. Метод потенциалов - 6 стр.
3. Список использованной литературы - 14 стр.
Транспортная задача.
1. Линейная транспортная задача.
Линейные транспортные задачи составляют особый класс задач линейного
программирования. Задача заключается в отыскании такого плана перевозок
продукции с m складов к n который потребовал бы минимальных затрат. Если
потребитель j получает единицу продукции (по прямой дороге) со склада i,
то возникают издержки р i j . Предполагается, что транспортные расходы
пропорциональны перевозимому количеству продукции, т.е. перевозка k
единиц продукции вызывает расходы k р i j.
Далее, предполагается, что
1
где bi есть количество продукции, находящееся на складе i, и aj –
потребность потребителя j.
Замечание. Если то количество продукции, равное остается
на складах. В этом случае мы введем "фиктивного" потребителя n +1 с
потребностью и положим транспортные расходы pi,n+1 равными 0 для
всех i.
Если то потребность на может быть покрыта. В этом случае
начальные условия должны быть изменены таким образом, чтобы потребность в
продукции могла быть обеспечена.
Обозначим через xij количество продукции, поставляемое со склада i
потребителю j. В предложении (1) нам нужно решить следующую задачу:
2
Транспортную задачу мы можем характеризовать транспортной таблицей и
таблицей издержек:
| |а1 |… |аn |
|b1 |. | | | | | |
|. | | | | | | |
|. | | | | | | |
|. | | | | | | |
|bm | | | | | | |
| | |. | | | | |
| | | |. | | | |
| | | | |. | | |
| | | | | |. | |
| | | | | | |. |
|p11 |… |p1n |
|. | |. |
|. | |. |
|. | |. |
|pm1 |… |pmn |
Допустимый план перевозок будем представлять в виде транспортной
таблицы:
| |а1 |… |аn |
|b | |… | |
|. | | | |
|. | | | |
|. | | | |
|bm | | | |
| |. | |. |
| |. | |. |
| |. | |. |
| | |… | |
Cумма элементов строки i должна быть равна bi, а сумма элементов
столбца j должна быть равна aj, и все должны быть
неотрицательными.
Пример 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 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 = для базисного решения переменных, х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 неизвестных определены, то в
системе всегда имеется уравнение, одно из неизвестных в котором уже
найдено, а другое ещё нет.
Переменные 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 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
подразумевается очень малым, исправим значения базисных переменных
так, что бы для новых 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( |
Если полученный таким образом элемент окажется отрицательным, то
в этой же строке должен найтись положительный (ещё до изменения) элемент
и в этом же столбце – положительный элемент . Тогда ячейка (s,
r) свободна, отмечаем её знаком + и проводим замену базиса. Так можно
избавиться от всех отрицательных значений*[1].
Затем при помощи метода потенциалов расчеты продолжают дальше
(вырождение уже никогда больше не встретится). Устремляя ( ( 0, приходим к
оптимальному решению исходной задачи.
Список использованной литературы:
1. Еремин И.И., Астафьев Н.Н. Введение в теорию линейного и выпуклого
программирования М.; Наука, 1976г.
2. Карманов В.Г. Математическое программирование. – М.; Наука, 1986г.
3. Моисеев Н.Н., Иванов Ю.П., Столярова Е.М. Методы оптимизации. –
М.; Наука, 1978г.
4. Иванов Ю.П., Лотов А.В. Математические модели в экономике. – М.;
Наука, 1979г.
5. Бронштейн И.Н., Семендяев К.А. Справочник по математике. – М.;
Наука, 1986г.
-----------------------
[1] Часто бывает достаточно везде заменить ( на -(.
1 2
