Математика для экономистов - Красс М.С.
ISBN 5-94723-672-9
Скачать (прямая ссылка):
Рассмотрим переход от одного опорного решения к другому на заданном примере.
Строим цикл для клетки (1.3), имеющей положительную оценку. У вершин цикла ставим знаки ( + ) и ( ) и записываем грузы.
90
50
60
У вершин со знаком (-) выбираем минимальный груз, он равен 60. Его прибавляем к грузам, стоящим у положительных вершин, и отнимаем от величин фу зои. с о ответе ї в у ющ и X отрицательным вершинам. Получаем новый цикл:
30
по Li
¦q во
Новое опорное решение имеет вид
( 30 0 60)
X1.
0 300 100
но о о
IS'
292 Глава 14. Линейное программирование
Проверим полученное решение на оптимальность. Для этого запишем полученное решение в новую распределительную таблицу и найдем потенциалы занятых и оценки свободных клеток.
1
2
3
"і
140
300
LSO
I
90
2
30
5
2
60
0
2
400
А
I
300
5
100
3
3
JlO
3
НО
6
В
2
¦»
2
i_
-2
2
Опять вычисляем оценки свободных клеток:
Д,г = -7. Дг, = 1 >0, Д.1} = -7. A^ = -5. Построим цикл для клетки с положительной оценкой A2, = 1:
30 F +160
Произведем перераспределение грузов по указанному ранее правилу:
! 90
30
70
Получим новое решение, которому соответствует новая таблица. Проверим его на оптимальность:
A11 =-\, An =-1. A6., =-6, Дм =-4.
Все оценки свободных клеток отрицательные, следовательно, найденное решение оптимальное.
Г 0 0 т\ 30 300 70 110 0 0
14.4. Транспортная задача 293
•г—- -
1
2
3
140
300
160
I
90
2
90
О
г
400
і
30
1
300
5
70
3
3
110
3
по
6
S
2
щ
2
-2
2
Стоимость транспортных расходов составляет:
L(X)1111n =90 ¦2 + 30- 4 + 300-1 + 70-5 + 110-3= 1280 ден. ед.
По сравнению с исходным опорным решением транспортные расходы уменьшились на 1610 1280 = 330 ден. ед.
Вырожденность а транспортных задачах
В случае вырожденной транспортной задачи число занятых клеток меньше, чем т + » - 1. Здесь целесообразно поменять местами поставщиков и потребителей или ввести в свободную клетку с наименьшим тарифом нулевую поставку. Нуль помещают в такую клетку, чтобы в каждой строке и столбце было не менее одной занятой клетки.
Рассмотрим вырожденность в транспортной задаче на примере. Пример 2.
Фирма осуществляет поставку бутылок на 4 завода, занимающихся производством прохладительных напитков. Она имеет3 склада, причем на складе 1 находится 6000 бутылок, на складе 2 — 3000 бутылок и на складе 3 — 4000 бутылок. Первому заводу требуется 4000 бутылок, второму заводу - 5000 бутылок, третьему заводу — 1000 бутылок, четвертому — 3000 бутылок. Матрицей задана стоимость перевозки одной бутылки от каждого склада к каждому заводу:
294 Глава 14. Линейное программирование
t
¦1000
2
5000
3 1000
4
3000
и,
1
(5000
6
А
3000
У
Є
3000
0
а
3000
.5.
3
2000
2
1000
R
-
-1
3
4000
2
4000
3
0
6
S
-1
3
А
3
В
Оценки свободных клеток будут равны
'6 4 9 8' 5 з 2 H . 2 3 6 8
V S
Как следует организовать доставку бутылок на заводы, чтобы стоимость перевозки была минимальной?
Решение.
Запишем исходные данные в распределительную таблицу, найдем исходное опорное решение по методу минимального тарифа. Число заполненных клеток равно Я, т + п - 1 = 6, следовательно, задача является вырожденной.
Для исключения вырожденности необходимо в какую-то клетку ввести нулевую поставку. Такая клетка становится условно занятой, ее целесообразно определить при вычислении потенциалов занятых клеток, она должна иметь наименьший тариф по сравнению с другими клетками, которые могут быть условно занятыми.
Так, для нахождения потенциала u:i поместим нулевую поставку в клетку (1, 3), после чего представляется возможным вычислить остальные потенциалы.
14.4. Транспортная задача 295
Л,, = -3, А,., = -6". А,
-3. А,,
-J.
Поскольку оценки отрицательные, то мы получили оптимальное решение:
' 0 3000 0 ЗОООї. Х,„ = 0 2000 1000 0 4000 0 0 0
Стоимость транспортных расходов составит: L (.V11111) = 28 000 ден. ед.
14.4.2. Открытая транспортная задача
При открытой транспортной задаче сумма запасов не совпадаете суммой потребностей, т. е.
1-] J-I
(14.19)
При этом, o свою очередь, возможны два варианта: а) если
1-м J-I
(14.20)
т. с. объем запасов превышает объем потребления, то все потребители будут удовлетворены полностью и часть запасов останется не вывезенной. Для решения задачи вводят фиктивного (и + 1) потребителя, потребности которого равны разности объемов запаса н потребления:
:2>-SV
(14.21)
Модель такой задачи будет иметь вид поиска минимума целевой функции (14.17) при ограничениях:
-V a0, 1=1,/71+1, / = 1, П;
б)если
296 Глава 14. Линейное программирование
(14.22)
т. е. объем потребления превышает объем запасов, то часть потребностей останется неудовлетворенной. Для решения задачи вводим фиктивного (/«-+- 1) поставщика с объемом поставки, раипым разности объемов потребления и поставок:
