146850 (Решение транспортной задачи методом потенциалов), страница 2
Описание файла
Документ из архива "Решение транспортной задачи методом потенциалов", который расположен в категории "". Всё это находится в предмете "транспорт" из , которые можно найти в файловом архиве . Не смотря на прямую связь этого архива с , его также можно найти и в других разделах. Архив можно найти в разделе "рефераты, доклады и презентации", в предмете "транспорт" в общих файлах.
Онлайн просмотр документа "146850"
Текст 2 страницы из документа "146850"
Для определения симплекс – множителей мы вносим на свободные места в таблице значения
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 этого сделать нельзя, так как тогда в соответствующем столбце не было бы знака -, и д.т.
Затем мы определяем минимум М из всех элементов, помеченных знаком -, и выбираем ячейку (, ), где этот минимум достигается.
В нашем примере с М = 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.
| 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 Часто бывает достаточно везде заменить на -.
