2015-10-22
1870
Задачи линейного программирования имеют каноническую форму если:
-все ограничения, кроме условия отрицательности переменных, имеют вид строгих равенств, а все свободные члены не отрицательны
Сведём задачу линейного программирования к канонической форме добавив к левым частям системы ограничений дополнительные переменные- Xn+1. В целевую функцию дополнительные переменные вводятся с коэффициентом 0.
Min Z = 2*x1+3*x2
------------
x1+x2=10
-2*x1+3*x2<=-5 (-1)
7*x1-4*x2<=6
x1,x2>=0
------------
------------
x1+x2=10
2*x1-3*x2-0*x3=5
7*x1-4*x2+0*x4=6
x1,x2>=0
------------
Угловая точка с неотрицательным коэффициентом называется опорной. А соответствующий план- опорный план. Базисом опорного плана будем называть систему М линейно-независимых векторов из условия задачи в которую входят все вектора соответствующие не нулевым координатам опорного плана.
Min Z =-5*x1+6*x3
-----------
2*x1-2*x3<=2
2*x1+x2-x3>=3
Xj>=0,j=1..5
----------
-----------
2*x1-2*x3+x4=2
2*x1+x2-x3-x5=3
Xj>=0,j=1..5
----------
Базисная переменная x4 и x5.В целевую функцию не входит знак нуля.
Построение начального опорного плана
|
|
|
Ограничение канонической задачи имеет предпочтительный вид, если при неотрицательности его правой части левая часть содержит переменную входящую с коэффициентом равным единице, а остальные ограничения с коэффициентом равным нулю.
---------
2*x1-2*x3+x4=2
2*x1+x2-x3=3
--------
x0={0;3;0;2}
Если каждое ограничение имеет предпочтительный вид, т.е. система ограничений приведена к единичному неотрицательному базису, то начальный опорный план строится так- предпочтительные переменные выбираются в качестве базисных, а все остальные- свободные. Свободные переменные приравниваются к нулю, а базисные к свободным членам.
Max Z = 2*x1-x3+3*x4+x5
------
X1+4*x3+x4=4
16*x2+x3-2*x4=16
5*x2+x5=6
------
Z(x0)=10
Min Z = 10*x1-7*x2-5*x3+0*x4+0*x5+0*x6
------
6*x1+15*x2+6*x3+x4=9
14*x1+42*x2+16*x3+x5=21
2*x1+8*x2+2*x3+x6=4
------
X0={0;0;0;9;21;4}
Z(x0)=0
