Мат. методы (Новичихин)
.pdf11
Задаемся потенциалом четвертой строки U4=10. Затем по правилу оптимизации определяем остальные потенциалы; например: при U4=10 потенциал V5 определится:
V 5 = U 4 + c45 = 10 + 10 = 20
U 3 = V 5 − c35 = 20 − 9 = 11 и т.д.
После определения всех потенциалов проверяем оптимальность плана по условию
V j −U i ≤ cij для xij=0
Величиной нарушения будем считать значение:
H = Vj − Ui − cij , т.е. H>0
Наличие хотя бы одного нарушения свидетельствует о том, что проверяемый план не оптимален и должен быть улучшен. Улучшение целесообразно начинать после просмотра всех свободных клеток с клетки, имеющей наибольшее нарушение.
Наибольшее нарушение равное H31=4 имеем в клетке R3P1.
Выявив величину нарушения, вводим поправки в ранее принятый план путем изменения значений xij.
Для этого из выбранной клетки с нарушением проводим замкнутую ломаную линию, двигаясь аналогично ходу шахматной ладьи, при этом изменение движения производим в загруженных клетках на угол 900. Эта линия носит название контура. Там где линия меняет направление, корреспонденции подлежат изменению. Поставим знаки «+» и «-» у вершины контура, начиная с «+» в клетке с нарушением . «+»означает, что корреспонденция должна быть увеличена , а «-» - уменьшена.
Величина потока улучшения должна быть равна минимальной корреспонденции со знаком «-», т.е. xул.=min xij(-). Такая корреспонденция у нас в клетке R3P3=130. Перемещаем эту величину по контуру и получаем новый план (табл.6).
При улучшении плана в одной или нескольких загруженных ранее клетках могут оказаться 0. Если число загруженных клеток равно (m+n-1), то освободившиеся клетки переходят в число незагруженных. Если число загруженных клеток меньше (m+n-1), то одна из освободившихся клеток с 0 может считаться загруженной.
Следующий план (табл.6) оказался снова не оптимальным. Улучшение плана продолжаем дальше.
|
|
|
|
|
|
|
12 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Таблица 6 |
|
|
|
13 |
|
13 |
|
15 |
|
16 |
|
20 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Ri |
Pj |
P1 |
|
P2 |
|
P3 |
|
P4 |
|
P5 |
|
ai |
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
9 |
R1 |
|
10 |
4 |
190 |
4 |
+1 |
5 |
+1 |
6 |
+4 |
7 |
200 |
|
|
- |
|
|
|
|
|
|
+ |
||||
|
|
|
|
|
|
|
|
|
|
|
|||
12 |
R2 |
|
|
7 |
70 |
1 |
230 |
3 |
|
8 |
|
11 |
300 |
|
|
|
|
|
|
|
|
|
|||||
11 |
R3 |
|
130 |
2 |
|
4 |
|
8 |
140 |
5 |
80 |
9 |
350 |
|
+ |
|
|
|
|
|
- |
||||||
10 |
R4 |
|
|
10 |
|
7 |
|
9 |
+3 |
3 |
150 |
10 |
150 |
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
bj |
|
140 |
|
260 |
|
230 |
|
140 |
|
230 |
|
1000 |
Во второй итерации наибольшее нарушение имеет клетка R1P5; H=4. Для этой клетки строим контур, начиная в клетке R1P5; поток улучшения xул.=10 (min значение потока по контуру со знаком «-»). Перемещаем по контуру это значение и получаем новый план (табл.7)
|
|
|
|
|
|
|
|
|
|
|
|
|
Таблица 7 |
|
|
|
13 |
|
17 |
|
19 |
|
16 |
|
20 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Ri |
Pj |
P1 |
|
P2 |
|
P3 |
|
P4 |
|
P5 |
|
ai |
|
|
|
|
|
|
|
|||||||
13 |
R1 |
|
|
4 |
190 |
4 |
+1 |
5 |
|
6 |
10 |
7 |
200 |
|
|
|
|
|
|
|
|
|
|||||
16 |
R2 |
|
|
7 |
70 |
1 |
230 |
3 |
|
8 |
|
11 |
300 |
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
11 |
R3 |
|
140 |
2 |
+2 |
4 |
|
8 |
140 |
5 |
70 |
9 |
350 |
|
|
|
|
|
|
- |
+ |
||||||
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
10 |
R4 |
|
|
10 |
|
7 |
|
9 |
+3 |
3 |
150 |
10 |
150 |
|
|
|
|
|
|
|
|
+ |
- |
||||
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
bj |
|
140 |
|
260 |
|
230 |
|
140 |
|
230 |
|
1000 |
|
|
|
|
|
|
|
|
|
|
|
|
|
Таблица 8 |
|
|
|
13 |
|
17 |
|
19 |
|
13 |
|
20 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Ri |
Pj |
P1 |
|
P2 |
|
P3 |
|
P4 |
|
P5 |
|
ai |
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
13 |
R1 |
|
|
4 |
190 |
4 |
+1 |
5 |
|
6 |
10 |
7 |
200 |
|
|
|
|
- |
|
|
|
|
|
+ |
|||
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
16 |
R2 |
|
|
7 |
70 |
1 |
230 |
3 |
|
8 |
|
11 |
300 |
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
11 |
R3 |
|
140 |
2 |
+2 |
4 |
|
8 |
|
5 |
210 |
9 |
350 |
|
|
|
+ |
|
|
|
|
- |
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
10 |
R4 |
|
|
10 |
|
7 |
|
9 |
140 |
3 |
10 |
10 |
150 |
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
bj |
|
140 |
|
260 |
|
230 |
|
140 |
|
230 |
|
1000 |
13
xул по данной итерации (-140).
Перемещаем xул по контуру и получаем следующий план (табл.8).
Применив к этому варианту все принятые действия, получим новый вариант плана (табл.9) xул=190.
|
|
|
|
Таблица 9 |
13 |
15 |
17 |
13 |
20 |
|
Ri |
Pj |
P1 |
|
P2 |
|
P3 |
|
P4 |
|
P5 |
|
ai |
|
|
|
|
|
|
|
|||||||
13 |
R1 |
|
|
4 |
|
4 |
|
5 |
|
6 |
200 |
7 |
200 |
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
14 |
R2 |
|
|
7 |
70 |
1 |
230 |
3 |
|
8 |
|
11 |
300 |
|
|
|
|
|
|
|
|
|
|||||
11 |
R3 |
|
140 |
2 |
190 |
4 |
|
8 |
|
5 |
20 |
9 |
350 |
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
10 |
R4 |
|
|
10 |
|
7 |
|
9 |
140 |
3 |
10 |
10 |
150 |
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
bj |
|
140 |
|
260 |
|
230 |
|
140 |
|
230 |
|
1000 |
Вполученном плане соблюдены все условия оптимальности, поэтому решение заканчиваем: получаем оптимальный вариант плана.
Если получим клетки с H=Vj-Ui-cij=0, то это значит, что существуют другие оптимальные планы, имеющие минимальные значения критерия оптимальности.
Впрактике, как правило, существуют дополнительные ограничения, и наличие нескольких оптимальных планов позволит выбрать из них наиболее целесообразный практически без нарушения условия оптимальности.
14
3 Двухэтапная транспортная задача
Значительная часть продукции народного хозяйства поступает из мест производства не непосредственно потребителям, а на различные промежуточные базы.
Единый вопрос: «кто кого снабжает?», решаемый транспортной задачей распадается на два взаимосвязанных вопроса: «с какого предприятия - на какой склад?» и «с какого склада - какому потребителю?» следует перевозить продукцию, чтобы получить минимум затрат.
Математической моделью для решения таких задач является, так называемая, двухэтапная транспортная задача.
Двухэтапная транспортная задача формулируется следующим образом. Допустим, имеются пункты производства R1, R2,…,R m с возможными размера-
ми ресурсов a1, a2,…,a m. Известны также потребители ресурсов P1, P2,…,P n с потреб-
ностями b1,…, bj,…,b n.
По пути к потребителю каждая единица продукции должна быть завезена на один из складов D1,…,D k с перерабатывающей способностью S1,…,S k.
cik – затраты на перевозку единицы продукции от любого изготовителя Ri на любой склад Dk;
ckj – затраты на перевозку со склада Dk к потребителю Pj;
Sk – издержки хранения и обработки продукции на складе Dk;
Сумма перерабатывающей способности складов должна быть больше мощности предприятий.
∑ Dk ³ ∑ Ri
( k ) (i )
Общая мощность предприятий должна быть больше потребностей, т.е.
∑ R ³ ∑ Pj
(i) ( j )
Оптимальный план должен предусматривать такие транспортные связи предприятий и складов, чтобы обеспечивалась минимальная общая сумма транспортных и складских расходов.
xik – размер поставки от поставщика Ri на Dk; xkj – размер поставки со склада Dk к Pj.
План должен удовлетворять следующим условиям:
∑ xkj = Pj
( k )
∑ xik £ Ri
k
Поступление продукции на склад не превышает его перерабатывающей способности:
15
∑ xik £ ∑ Dk
(i ) (k )
Сумма поступления продукции на склад равна сумме её вывоза с того же склада:
∑ xik £ ∑ xkj
(i) (k )
Целевая функция выглядит следующим образом:
F = ∑∑cik × xik + ∑∑ckj × xkj + ∑ Sk ∑ xkj ® min
(i) (k ) |
( k ) ( j ) |
(k ) |
j |
или
F = ∑∑cik × xik + ∑∑ckj × xkj + ∑∑ Sk × xik ® min ;
(i) (k ) |
( k ) ( j ) |
k |
k |
так как ∑∑ Sk xkj = ∑∑ Sk × xik
( k ) ( j ) |
(i) ( k ) |
Если ∑ Dk = ∑ Pj , то двухэтапная задача может решаться как две независимых
( k ) ( j )
задачи.
Если ∑ Dk > ∑ Pj , то решения по прикреплению складов к заводам и потреби-
( k ) ( j )
телей к складам взаимосвязаны; проблема оптимизации в этом случае должна решаться как единое целое, т.е. по модели двухэтапной задачи.
Рассмотрим пример:
R1=350; R2=400; R3=550 ед. ресурсов; D1=900; D2=500 ед.
P1=360; P2=230; P3=410; P4=200 ед. ресурсов.
Составляем матрицу. Особенность её заключается в том, что склады представлены в ней и как потребители, и как поставщики (табл. 24).
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Таблица 24 |
|
|
|
|
6 |
|
7 |
|
11 |
|
12 |
|
13 |
|
10 |
|
0 |
|
|
|
Ri |
Pj |
D1 |
|
D2 |
|
P1 |
|
P2 |
|
P3 |
|
P4 |
|
Pф |
|
ai |
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
4 |
R1 |
|
350 |
2 |
+1 |
2 |
|
м |
|
м |
|
м |
|
м |
|
0 |
350 |
|
|
- |
+ |
|
|
|
|
|
|
|
|
|
|
||||
3 |
R2 |
|
|
5 |
400 |
4 |
|
м |
|
м |
|
м |
|
м |
|
0 |
400 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
0 |
R3 |
|
350 |
6 |
100 |
7 |
|
м |
|
м |
|
м |
|
м |
100 |
0 |
550 |
|
+ |
- |
|
|
|
|
|
|
|
|
|
||||||
6 |
D1 |
|
200 |
0 |
|
м |
60 |
5 |
230 |
6 |
410 |
7 |
|
8 |
|
м |
900 |
|
|
|
|
+ |
|
- |
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
8 |
D2 |
|
|
м |
|
0 |
300 |
3 |
|
7 |
+1 |
4 |
200 |
2 |
|
м |
500 |
|
|
|
|
|
|
- |
|
|
+ |
|
|
|
|||||
|
bj |
|
900 |
|
500 |
|
360 |
|
230 |
|
410 |
|
200 |
|
100 |
|
2700 |
|
|
Начальный план при решении задачи составляется в следующем порядке. |
16
В начале методом наименьшего значения показателя оптимальности заполняется первая нижняя часть матрицы. Избыток мощности складов заносят в клетки фиктивной диагонали (D1D1 и D2D2) – левый нижний квадрант.
Далее потребность столбцов Dk уменьшается на величину потоков, занесённых в фиктивную диагональ. После этого методом наименьшего показателя оптимальности заполняется левая верхняя часть матрицы. Остатки мощности Ri заносят
вклетки столбца фиктивного потребителя.
Врезультате решения (методом потенциалов) получаем оптимальную матрицу (табл.25).
Как видно из табл.25 мощность поставщика R3 используется не полностью. Перерабатывающая способность складов недоиспользуется на 200ед.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Таблица 25 |
|
|
|
|
6 |
|
6 |
|
11 |
|
12 |
|
13 |
|
11 |
0 |
|
|
|
Ri |
Pj |
D1 |
|
D2 |
|
P1 |
|
P2 |
|
P3 |
|
P4 |
Pф |
|
ai |
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
4 |
R1 |
|
250 |
2 |
100 |
2 |
|
м |
|
м |
|
м |
м |
|
0 |
350 |
|
|
|
|
|
|
|
|
|
|
|
|
|||||
2 |
R2 |
|
|
5 |
400 |
4 |
|
м |
|
м |
|
м |
м |
|
0 |
400 |
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
0 |
R3 |
|
450 |
6 |
|
7 |
|
м |
|
м |
|
м |
м |
100 |
0 |
550 |
|
|
|
|
|
|
|
|
|
|
|
|
|||||
6 |
D1 |
|
200 |
0 |
|
м |
360 |
5 |
230 |
6 |
110 |
7 |
8 |
|
м |
900 |
|
|
|
|
|
|
|
|
|
|
9 |
D2 |
м |
0 |
3 |
7 |
300 |
4 |
200 |
2 |
|
м |
500 |
|
|
|
|
|
|
|
|
|||||
|
bj |
900 |
500 |
360 |
230 |
410 |
|
200 |
|
100 |
|
2700 |
В левом верхнем квадранте матрицы получено оптимальное прикрепление поставщиков к складам, в правом нижнем – прикрепление потребителей к складам.