←предыдущая следующая→
1 2
Новосибирска государственная академия водного транспорта
Якутский филиал
Курсовая работа
по дисциплине исследование операций
на тему:
"Решение транспортных задач
методом потенциалов"
Выполнил: студент 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), которая при замене базиса переходит в базисную (это соответствует отысканию разрешающего столбца в симплекс – методе).
Для определения симплекс – множителей мы вносим на свободные места в таблице значения
pij = pij – ui – vj
(коэффициенты целевой функции, пересчитанные для свободных переменных). Если все pij 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 этого сделать нельзя, так как тогда в соответствующем столбце не было бы знака -, и д.т.
Затем
←предыдущая следующая→
1 2