Симплекс-метод 2 (стр. 2 из 3)
Нахождение решения каждой задачи распадается на два этапа:
1. нахождение опорного плана;
2. отыскание оптимального решения.
В процессе первого этапа выясняется, имеет ли данная задача допустимые не отрицательные решения, если да, то находиться опорное решение, для которого все остальные переменные равны 0, а все базисные не отрицательные.
В процессе второго этапа выясняется, ограничена ли снизу функция L, которая стремиться к минимуму, если нет, то оптимального решения не существует. Если да, то оно отыскивается после замены x на y.
Двойственные задачи ОЗЛП.
В процессе расчета задачи ОЗЛП может получиться один или несколько отрицательных свободных членов, это означает, что полученное решение не является опорным, соответственно не может быть оптимальным. Рассмотрим случай, когда среди свободных членов есть отрицательный. Для того, чтобы избавиться от них необходимо пересчитать таблицу обмена базисных и свободных переменных пока не придем к опорному решению или не убедимся в том, что решение не существует. Необходимо так обменивать базисные и свободные переменные, чтобы эта процедура приближала к области допустимых решений, чтобы число отрицательных свободных членов убывало или по крайне мере убывали их абсолютные величины.
Допустим, имеется одно из уравнений с отрицательным свободным членом:
| СЧ | x1 | x2 | x3 | |||||
| y1 | 1 | 2 | -1 | 1 | -2 | 1 | -1 | 0 |
| y2 | -5 | 4 | -2 | 2 | 1 | 2 | 1 | 0 |
| y3 | 2 | 2 | 1 | 1 | 1 | 1 | 0 | 0 |
| y4 | 1 | 0 | 0 | 0 | -1 | 0 | 1 | 0 |
Ищем в данной строке (y2) отрицательный элемент aij,если такого элемента нет, то данная система уравнений не совместна. При отсутствии отрицательных элементов в строке вся правая часть соответствующего уравнения может быть только отрицательной, а это противоречит условиям не отрицательных переменных.
Если такой элемент есть, то выбираем столбец, в котором он находиться в качестве разрешающего. Далее необходимо найти сам разрешающий элемент. Для рассмотрения берем в данном столбце только те элементы, которые имеют одинаковый знак со свободным членом. Находим отношения свободного члена и элемента в той же строке и среди полученных отношений берем min по модулю, таким образом находиться разрешающая строка.
| СЧ | x1 | x2 | x3 | |
| y1 | 3 | 2 | 1 | 2 |
| y2 | 1 | 2 | 3 | -1 |
| y3 | 2 | 1 | -1 | 0 |
| y4 | 1 | 0 | -1 | 0 |
Блок – схема алгоритма.
Пример решения задачи с использованием симплекс-метода.
Даны данные: из которых составляется система уравнений вида:
Целевая функция этой системы уравнений стремится в максимум, и имеет вид:
Базисное решение является допустимым, так как в правой части неравенств не содержатся отрицательные значения.
В данной системе 3 – уравнения с 3 – неизвестными, принимают за основные X4, X5, X6 – переменных.
После этого выражают основные переменные (добавочные) через неосновные, и находят базисное решение соответствующее.
Вводим добавочные неотрицательные переменные (которые еще называют «неосновные»), и сводим систему неравенств к эквивалентной системе уравнений.
Так как в полученной системе уравнений нет отрицательных свободных членов, то базисное решение является допустимым (0; 0; 0; 60; 100; 36).
Выразим целевую функцию через неосновные переменные: для этого находят абсолютные величины отношений свободных членов уравнений, к коэффициентам при переменной, переводимой в основные, причем только из тех уравнений, в которых эти коэффициенты положительны.
Х2: {60/1; 100/1; 36/1} переводим Х2 в основные переменные: из третьего уравнения, так как 36/1=36 наименьший коэффициент.
Подставим в целевую функцию =>Х2:
Рассмотрим полученную систему уравнений и целевую функцию:
Если отыскивается максимум линейной формы, и в ступени выражений нет основных переменных с положительным знаком, то критерий оптимальности выполнен и полученное базисное решение служит оптимальным (задача решена), но в примере еще есть две переменные с положительным знаком.
Переходим к новому базисному решению {0; 5; 0; 0; 20; 50}. Из не основных переменных, входящих в линейную форму (уравнения) с положительным коэффициентом выбираем ту, которой соответствует наибольший коэффициент и переводит ступени в основные.
Рассмотрим переменную Х1 {10; 10; 17}. Выразим из первого уравнения переменную Х1:
Рассмотрим полученную систему уравнений и целевую функцию:
Если отыскивается максимум линейной формы, и в ступени выражений нет основных переменных с положительным знаком, то критерий оптимальности выполнен и полученное базисное решение служит оптимальным (задача решена), но в примере еще есть одна переменная с положительным знаком (Х3).
Переходим к новому базисному решению {10; 0; 0; 0; 40; 20}. Из не основных переменных, входящих в линейную форму с положительным коэффициентом выбираем Х3, которой соответствует наибольший коэффициент (5) и переводит ступени в основные.
Рассмотрим переменную Х3 {0; 8; 20}. Выразим из второго уравнения переменную Х3:
Рассмотрим полученную систему уравнений и целевую функцию:
Отыскивается максимум линейной формы, так как в ступени выражений нет основных переменных с положительным знаком – критерий оптимальности выполнен и полученное базисное решение служит оптимальным (задача решена).
То есть при Х1=10; Х2=0; X3=8 максимальное значение функции равно 80 (Lmax=80).
Листингпрограммы.
Program Simplex_Metod;
Uses crt;
label
POVZNAC, NACH;
var
Fo, FunctPr, B, H, Hnew, C, Cnew, CPr, Cprnew, FX: array[1..30] of real;
X, Xnew: array[1..30,1..30] of real;
BS, Bvsp,ZNAC: array[1..30] of string[3];
MIN, I1, I, J, Kx, Ky, Kit, NachKell, NachY, K_st: integer;
PriznacY, KLstr, KLst, ErrCode, Dop_X: integer;
P, P1, Mo, F0, Epsilon, Z, CHLEN: real;
VSP, S, PrOper: string;
F: text;
DPx, DPy, MinMax, Kell, SNom: integer;
Function MakeIndex (V:integer; S:char): string;
var
M,Z: string;
begin
STR(V,M);
Z:=S+M;
MakeIndex:=Z;
end;
Procedure enter;
var
BUF :string;
NEXT :boolean;
begin
clrscr;
repeat
write ('Введите количество уравнений: ');
readln (SNom);
if (SNom > 10) or (SNom <=0) then
begin
writeln ('Введите число 1 до 10: ');
readln;
end
else NEXT:=True;
until NEXT;
repeat
NEXT:=False;
write ('Количество элементов: ');
readln (Kell);
if (Kell > 10) or (Kell <=0) then
begin
writeln (Введите число от 1 до 10: ');
readln;
end
else NEXT:=True;
until NEXT;
NachKell:=Kell;
DPx:=Kell+1;
DPy:=1;
Epsilon:=0.00001;
for I:=1 to SNom do
begin
for J:=1 to Kell do
begin
write ('Введите ',J,'-й элемент ',I,'-го уравнения: ');
readln (Xnew [I,J]);
end;
repeat
write ('Введите знак: ');
readln (ZNAC [I]);
if (ZNAC [I] <> '>=') and (ZNAC [I] <> '=') and (ZNAC [I] <> '<=') then
begin
write ('Неправильно задан знак!');
readln;
end;
if (ZNAC [I] = '=') or (ZNAC [I] = '>=') then PriznacY:=1;
until (ZNAC [I] = '>=') or (ZNAC [I] = '=') or (ZNAC [I] = '<=');
write ('Введите свободный член: ');
read (B[I]);
end;
write ('Введите свободный член целевой функции: ');
readln (CHLEN);
for J:=1 to Kell do
begin
write ('Введите ',J,'-й коэффициент целевой функции: ');
read (FX[J]);
end;
readln;
write ('Целевая функция стремится к максимуму (Д/Н): ');
readln (BUF);
if (BUF='Д') or (PrOper='Д') then MinMax:=1
else MinMax:=2;
write ('Целочисленное решение (Д/Н): ');
readln (PrOper);
if (PrOper='Д') or (PrOper='Д') then PrOper:='Д'
else PrOper:='Н';
end;
procedure DOP_PER;
begin
if ZNAC[I1]='=' then
begin
Kell:=Kell+1;
Bvsp[Kell]:=MakeIndex (DPy, 'Y');
DPy:=DPy+1;
Xnew[I1,Kell]:=1;
if MinMax=1 then FX [Kell]:=-1
else FX [Kell]:=1;
FunctPr[Kell]:=1;
for I:=1 to SNom do
if I<>I1 then Xnew [I,Kell]:=0;
end;
if ZNAC[I1]='>=' then
begin
Kell:=Kell+1; Bvsp[Kell]:=MakeIndex(DPx,'X');
DPx:=Dpx+1; Dop_X:=Dop_X+1;
Xnew[I1,Kell]:=-1; FX[Kell]:=0;
for I:=1 to SNom do
if I<>I1 then Xnew[I,Kell]:=0;