Исследование операций (стр. 7 )

g12=с12-(a1+b2)=3-(0+10)=-7;

g13=с13-(a1+b3)=2-(0+12)=-10;

g23=с23-(a2+b3)=5-(-3+12)=-4;

g31=с31-(a3+b1)=4-(-4+6)=2;

g41=с41-(a4+b1)=6-(-6+6)=6;

g42=с42-(a4+b1)=8-(-6+10)=4;

4.Выбирается свободная переменная xkt с наименьшим отрицат. gkt В данном случае gkt=g13= -10 если все gkt0-полученное решение оптимальное.

5. Для переменной xkt- строится цикл пересчета, т. е. замкнутая ломанная линия, все вершины которой, кроме xkt находятся в базисных точках (см. Рис.). В данном случае xkt=x13 .Далее

вершине xkt=x13 присваивается знак (+) остальные по очереди(+)(-)

6. Производится «сдвиг»:

а) выбирается вершина цикла пересчета со знаком (-),которой

соответствует минимальное xij

б) ко всем вершинам цикла, в зависимости от знака вершины прибавляется или вычитается xij Эта операция соответствует введению в базис новой переменной xij=x33 в нашем случае x33=5.

7. Строим новую матрицу перевозок и повторяем для нее п. п. 2-7

	B1	B2	B3	ai
A1	6 20	3	2 5
A2	3 10	7 15	5
A3	4	6 15	8
A4	6	8	6 25
bj

Рассчитаем коэффициенты gij для свободных переменных

g12=с12-(a1+b2)=3-(0+10)=-7;

g23=с23-(a2+b3)=5-(-3+2)=4;

g31=с31-(a3+b1)=4-(-4+6)=2;

g33=с33-(a3+b3)=8-(-4+6)=10;

g41=с41-(a4+b1)=6-(4+6)=-4 ;

g42=с42-(a4+b2)=8-(4+10)=-6;

Минимальное gkt=g12= -7 -строим для нее цикл пересчета минимальное xij в цикле со знаком (-) - x22. Производим пересчет и стоим новую таблицу.

	B1	B2	B3
A1	6 5	3 15	2 5
A2	3 25	7	5
A3	4	6 15	8
A4	6	8	6 25

коэффициенты:

g22=с22-(a2+b2)=7-(-3+3)=7;

g23=с23-(a2+b3)=5-(-3+2)=6;

g31=с31-(a3+b1)=4-(3+6)=-5;

g33=с33-(a3+b3)=8-(3+2)=3;

g41=с41-(a4+b1)=6-(4+6)=-4 ;

g42=с42-(a4+b2)=8-(4+3)=1; max g31 - строим цикл пересчета

 

	B1	B2	B3
A1	6	3 20	2 5
A2	3 25	7	5
A3	4 5	6 10	8
A4	6	8	6 25

g11=с11-(a1+b1)=6-(0+1)=5;

g22=с22-(a2+b2)=7-(3+2)=2;

g23=с23-(a2+b3)=5-(2+2)=1;

g33=с33-(a3+b3)=8-(-4+1)=3;

g41=с41-(a4+b1)=6-(4+1)=1 ;

g42=с42-(a4+b2)=8-(4+3)=1;

Все коэффициенты положительны, значит решение оптимальное. Стоимость его реализации:

Несбалансированные (открытые) транспортные задачи.

Транспортная задача называется несбалансированной, если мощность поставщиков не равна спросу, т. е.

åaj¹åbi

Для решения задачи «балансируют»:

1) Если åaj<åbi, т. е. мощность превышает спрос, добавляется «фиктивный склад», затраты на доставку в этот пункт принимаются равными 0.

3. Если åaj>åbi, то добавляют «фиктивного поставщика», в затраты на доставку от этого поставщика включают все убытки, связанные с неудовлетворением спроса.

3 СЕТИ

Множество задач, существующих в инженерной и организационной работе, решаются с помощью, так называемых, сетевых моделей, например:

1) Проектирование газопровода между морской буровой платформы и скважинной на берегу.

2) Определение кратчайшего пути между двумя городами по существующей сети шоссейных дорог.

3. Определение максимальной пропускной способности трубопровода для транспортировки угольной пульпы из шахты на ТЭЦ.

4. Определить наиболее экономичную схему транспортировки нефти из пунктов нефтедобычи на перерабатывающие заводы, учитывая такие варианты, ж. д., грузовики, нефтепроводы и т. д.

сетевые модели принять, классифицировать следующим образом:

а) задача минимизации сетей;

б) задача нахождения кратчайшего маршрута

в) определение максимальной пропускной способности

г) минимизация стоимости потока в сети с заданными пропускными способностями.

Перечисленные задачи, в принципе, можно решить и методом линейного программирования, однако из-за ограничений это нецелесообразно. Поэтому для каждого из видов моделей существуют специализированные методы. Рассмотрим некоторые из них.

3.1 Задачи минимизации сетей

Задача минимизации сети - состоит в нахождение ребер, соединяющие все узлы сети и имеющих минимальную длину. Условием минимизации- является отсутствие циклов - круговых замкнутых сетей. Решение задачи можно проиллюстрировать следующим образом; пусть мы имеем сеть:

18

2

1

4

6

3

 

Ясно, что в минимальной сети узел 3 соединен с 1 и 2, что дает минимальную длину последовательности ребер: 4+6=10.

Соединять узлы 1 и 2 нельзя, т. к.

1) сеть не будет минимальной 4+6+18=28

2) возникает цикл.

Т. к. есть, не содержащая циклов дерево, ее называют - минимальное

дерево-остов.

Алгоритм построения минимального дерева - остов выглядит следующим образом:

1) Начиная с любого узла: соединяют его с ближайшим. Соединенные два узла образуют связное множество . Остальные узлы - несвязное множество

2) В несвязном множестве выбирают узел, ближайший к любому узлу из связного множества и связывают его.

3) Продолжать процесс до тех пор, пока в связное множество не войдут все узлы сети.

ЛЕКЦИЯ 9

Пример: Студия кабельного телевидения планирует сеть для обслужива - ния 5 районов- новостроек.

ТВ-ЦЕНТР

 

Отсутствие ребер показывает отсутствие возможности протя­нуть кабель между узлами:

1) Начиная с узла 1 т. е. с={1};ć={2,3,4,5,6} ближайший к узлу 1- 2, поэтому : с={1,2};ć={3,4,5}

2) Ближайший узел 5 :

с={1,2,5}; ć={3,4,6}

3) с={1,2,5,4}; ć={3,6}

4) с={1,2,5,4,6}; ć={3}

5) с={1,2,5,4,6,3}; ć=0

В случае подключения 3- го узла-2 варианта - 1- 3 и 4- 3, вы­бираем 1- 3 т. к. в этом случае прием будет лучше. Отметим, что если бы начали строение дерева не с 1- го узла, то ре­зультат был бы тот же.

3.2 Задачи о кратчайшем пути.

Мы рассмотрим два алгоритма решения этой задачи. Пер­вый - более простой - для сетей без замкнутых циклов. Вто­рой - более сложный, для сетей с циклами.

3.2.1. Алгоритм для сетей без циклов.

Пример: Рассмотрим алгоритм на примере. 1- начальная

точка, 2- конечная точка. Сеть не имеет циклов, т. е. не имеет цепей, связывающих узел с са­мим собой.

Введем обозначения: dij - расстояния на сети между соеди­няющимися узлами; Uj - кратчайшее расстояние между узлом 1 и j.

Вычисление ведется по формуле:

Из формулы следует, что кратчайшее расстояние uj можно получить лишь после того, как определено кратчайшее расстояние до каждого предыдущего узла i, соединенного с узлом j.

Решение задачи:

этап 1. U1 = 0;

этап 2. U2= U1 + d12 =0+2=2 (из 1)

U3= U1 + d13 =0+4=4 (из 1);

этап 3. =7 (из 3)

этап 4. (из 3)

этап 5.

Самый короткий маршрут составляют от последнего этапа к первому:

его длина 13.

3.2.2. Алгоритм для сетей с циклами.

В случае с циклами, т. е. обратными ходами, возможна ситуация, когда кратчайшей связан с обратным движением из точки с большим номером в точку с маленьким номером. Проще всего алгоритм понимается на примере:

1)   dij заносятся в таблицу.

j i	1	2	3	4	5	6	7	ui
1		2	8	11	9			0
2	4		3		5	1		2
3	1	4				2		5
4	5		9			2	23	11(8)
5	2					7	9	7(4)
6		8	3	5	1		10	3
7				10	4	2		13
Ui	0	2	5	11	7	3	13

2)   Ui и i заполняются значениями Ui, рассчитанными по алгоритму предыдущего параграфа.