 |
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция
Оптимизация полученного допустимого решения
В полученном допустимом решении имеются 4 свободных переменных 
=0, 
=0, 
=0, 
=0. Произвольно выберем свободную переменную и увеличим значение этой переменной от нуля до единицы. При этом нарушаются балансы мощности по 4-му столбцу и по второй строке.
Таблица 4.6
 =15  =1
| =0  =2
|  =20  =3
|  =15  =5
|  =50
|
=0  =4
|  =10  =1
|  =-29  =1
| =+1  =2
|  =40
|
 =15  =1
|  =10  =2
| =+1  =5
|  =-34  =10
|  =60
|
 =30
|  =20
|  =50
|  =50
| Z |
Для восстановления этих балансов, уменьшим на единицу значения базисных переменных, входящих в 3-й столбец и 4-ю строку ( =29, =34), при этом увеличим значение свободной переменной от нуля до единицы. Балансы мощности по всем строкам и столбцам оказываются восстановленными.
В результате выполненных действий в транспортной матрице получен замкнутый цикл, вершины которого отмечены знаками «+» и «-». Так как мы переводим две свободные переменные и в базисные переменные, то они могут одновременно являться начальной вершиной цикла, а остальные вершины цикла лежат в клетках базисных переменных и 
. Знак «+» в вершине цикла соответствует увеличению переменной, знак «-» - ее уменьшению. При увеличении на единицу свободной переменной, изменение целевой функции определится как алгебраическая сумма удельных стоимостей, стоящих в вершинах цикла. Изменение целевой функции при увеличении на единицу свободной переменной составит
∆ Z = - + - = 2-10+5-1= -8+4= -4.
Отсюда видно, что при увеличении свободной переменной , значение целевой функции уменьшается. Эту свободную переменную следует перевести в базис. Итак, в базис переводится переменная и . В соответствии со знаками вершин цикла, при увеличении этих переменных в положительную сторону, базисные переменные и будут уменьшаться. Исходя из этого, мы получаем новое допустимое решение.
Таблица 4.7
| =15 =1
| =0 =2
| =20 =3
| =15 =5
| =50
|
| =0 =4
| =10 =1
| =0 =1
| =30 =2
| =40
|
| =15 =1
| =10 =2
| =30 =5
| =5 =10
| =60
|
| =30
| =20
| =50
| =50
| Z=455 |
В этом решении:
свободные переменные: =0, =0, =0.
базисные переменные: =15, 
=20, =15, =10, =30, 
=15 =10, =30, =35. Значение целевой функции:
Z = 
+ 
+ 
+ 
+ 
+ 
+ 
+ 
+ 
+
+ 
+ 
+ 
.
Z = 15·1+0·2+20·3+15·5+0·4+10·1+0·1+30·2+15·1+10·2+30·5+5·10=455 у.е
(40) (60)
(50)
15 30
5
15 15 10 10 20 30
(50)
(30) (20) (50)
Рис. 4.6. Схема электрической сети
Продолжим оптимизацию данного решения. Произвольно выберем базисную переменную и увеличим ее значение на единицу мощности. При этом нарушаются балансы мощности по 4-му столбцу и по второй строке.
Таблица 4.8
| =15 =1
| =0 =2
| =20 =3
| =15 =5
| =50
|
| =0 =4
| =-9 =1
| =0 =1
| =+31 =2
| =40
|
| =15 =1
| =+11 =2
| =30 =5
| =-4 =10
| =60
|
| =30
| =20
| =50
| =50
| Z |
Для восстановления этих балансов, уменьшим на единицу значения базисных переменных, входящих во 2-й столбец и 3-ю строку ( =9, =4), при этом увеличим значение базисной переменной на единицу мощности величины этой переменной. Балансы мощности по всем строкам и столбцам оказываются восстановленными.
В результате выполненных действий в транспортной матрице получен замкнутый цикл, вершины которого отмечены знаками «+» и «-». Так как мы переводим одну базисную переменную в другую базисную переменную , то начальной вершиной цикла в данном случае будет является базисная переменная , а остальные вершины цикла лежат в клетках базисных переменных , и . Знак «+» в вершине цикла соответствует увеличению переменной, знак «-» - ее уменьшению. При увеличении на единицу свободной переменной, изменение целевой функции определится как алгебраическая сумма удельных стоимостей, стоящих в вершинах цикла. Изменение целевой функции при увеличении на единицу свободной переменной составит
∆ Z = - + - = 2-10+2-1= -8+1= -7.
Отсюда видно, что при увеличении базисной переменной , значение целевой функции уменьшается. В соответствии со знаками вершин цикла, при увеличении базисных переменных и в положительную сторону, базисные переменные и будут уменьшаться. Исходя из этого, мы получаем новое допустимое решение.
Таблица 4.9
| =15
=1
| =0
=2
| =20
=3
| =15
=5
| =50
|
| =0
=4
| =5
=1
| =0
=1
| =35
=2
| =40
|
| =15
=1
| =15
=2
| =30
=5
| =0
=10
| =60
|
| =30
| =20
| =50
| =50
| Z=420 |
В этом решении:
свободные переменные: =0, =0, =0, =0
базисные переменные: =15, =20, =15, =5, =35, =15 =15, =30. Значение целевой функции:
Z = + + + + + + + + +
+ + + .
Z = 15·1+0·2+20·3+15·5+0·4+5·1+0·1+35·2+15·1+15·2+30·5+0·10=420 у.е
(40) (60)
(50)
15 35
15 15 5 15 20 30
(50)
(30) (20) (50)
Рис. 4.7. Схема электрической сети
Поиск по сайту: