 |
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция
Симплекс-метод. Построение начального опорного плана
|
Читайте также: |
Построение начального опорного плана
Рассмотрим 3 случая.
Пусть система ограничений имеет вид
Xi+ 
ijXj=bi , bi=>0,(i=1,m)
X0=(0,0,…,0,bi)
Ограничение канонической задачи линейного программирования имеет предпочтительный вид, если при неотрицательной его части левая часть содержит переменную, входящую с коэффициентом равным 1, а остальные с коэффициентом равным 0. Если каждое ограничение канонической задачи линейного программирования имеет предпочтительный вид, т.е. система ограничений приведена к единичному неотрицательному базису, то начальный опорный план строиться следующим образом: Предпочтительные переменные выбираются в качестве базисных, а все остальные свободные. Свободные переменные приравниваются к нулю, а базисные – к свободным членам(bi).
Пример:
minZ=-5X1+6X3
2X1-2 X3+ X4=2| X4
2 X1+ X2- X3=3 | X2
X1>=0
X0=(0,3,0,2)
ijXj<=bi, bi>=0
Xn+i>=0
ijXj+Xn+1=bi, bi>=0
X0=(0,…,0,bi,...,bm)
Пример 2:
minZ=10 X1-7 X2-5 X3
6 X1+15 X2+6 X3<=9
14 X1+42 X2+16 X3<=21
2X1+8 X2+2 X3<=4
тогда
6 X1+15 X2+6 X3+ X4=9
14 X1+42 X2+16 X3+ X5=21
2X1+8 X2+2 X3+ X6=4
X0=(0,0,0,9,21,4)
ijXj>=bi , bi>=0
ijXj-Xn+i=bi
M-задача
Max(min)Z= 
jXj-(+)M 
i
minZ=-5 X1+4X2+3 X3+6X4
X1+21X2+ X3+2X4<=3
-X1-14X2-2X3+3X4>=2
-X1-6X2+X3-X4>=1
X1+21X2+ X3+2X4+ X5=3
-X1-14X2-2X3+3X4- X6+W1=2
-X1-6X2+X3-X4- X7 +W2=1
X0=(0,0,0,0,3,0,0,2,1)
Z(X0)=3M
Пример:
maxZ=5 X1+7 X2+6 X3+11X4
3X1+4 X2 -3 X3 <=12|+ X5
X1 -4 X4 <=22 | +X6
X2 + X3 +3 X4 <=6 |+ X7
X0 =(0,0,0,0,12,22,6)
Пример 2:
maxZ= X1 +2 X2 +3 X3 +4 X4
4X1+3X2+7X3 =9 |+Wi
X1 +2 X2 -5 X4 >=21|- X5 +W2
4 X2 +7 X3 – X4 >=7|- X6 +W3
X0 =(0,0,0,0,0,0,9,21,7)
Z(X0)=37M
Симплексные таблицы
maxZ= 18X1 +20 X2 +32 X3
18X1+15X2+12X3 <=720
6X1 +4 X2 +8 X4 <=384
5X1 +3X2 +12X3 >=360
| БП | СБ | А0 | Х1 | Х2 | Х3 | Х4 | Х5 | Х6 |
| Х4 | ||||||||
| Х5 | ||||||||
| Х6 | ||||||||
| Сj | -18 | -20 | -32 |
Рабочая часть таблицы начинается с 3 строки и 3 столбцы. В БП занесены базисные(предпочтительные) переменные; СБ содержит коэффициенты целевой функции, стоящие при базисных переменных; Ао содержит свободные члены Вi. Сверху, над рабочей частью таблицы указаны все переменные и коэффициенты целевой функции.
Хо=(0,0,0,720,384,360)
Z(Xo)=0
Поиск по сайту: