Решение линейных задач метод симплекса

Ответ записывается следующим  образом:

- Каждому отрицательному  коэффициенту в векторе решения  ставится в соответствие нулевой  коэффициент для соответствующей  переменной в ответе.

- Для каждого нулевого  коэффициента в векторе решения  ставится в соответствие значение  свободного члена из строки, содержащей  единицу в столбце данной переменной.

- Фиктивные переменные  в ответе не учитываются.

Ведущим может быть назначен любой столбец, удовлетворяющий  одному из условий:

1)      Первый столбец, содержащий положительный элемент в векторе решений.

2)      Столбец, содержащий наибольший положительный элемент в строке решения.

3)      Если столбец удовлетворяет условию max(C_j min b_j/a_ij) при решении на max, и min(C_j min b_j/a_ij) при решении задач на min.

C_j – коэффициент целевой функции в столбце j, a_ij – коэффициент в столбце j и строке i.

Решение задачи

Определим максимальное значение целевой функции F(X) = 3500 x₁ +3200 x₂  +1500 x₃ при следующих условиях ограничений. 

 

4 x₁ + 2 x₂ + 5 x₃ <=190

5 x₁ + 3 x₂ + 4 x₃ <=320

7 x₁ + 9 x₂ + 5 x₃ <=454 

 

Для построения первого опорного плана систему неравенств приведем к системе  уравнений путем введения дополнительных переменных. 

 

4x₁ + 2x₂ + 5x₃ + 1x₄ + 0x₅ + 0x₆ = 190

5x₁ + 3x₂ + 4x₃ + 0x₄ + 1x₅ + 0x₆ = 320

7x₁ + 9x₂ + 5x₃ + 0x₄ + 0x₅ + 1x₆ = 454 

 

Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

Базисные переменные это  переменные, которые входят только в одно уравнение системы ограничений  и притом с единичным коэффициентом.

Решим систему уравнений  относительно базисных переменных:

x₄ , x₅ , x₆

Полагая, что свободные  переменные равны 0, получим первый опорный план: X1 = (0,0,0,190,320,454)

Поскольку задача решается на максимум, то ведущий столбец  выбирают по максимальному отрицательному числу и индексной строке. Все  преобразования проводят до тех пор, пока не получатся в индексной  строке положительные элементы.

Переходим к основному  алгоритму симплекс-метода.

 

X1	X2	X3	X4	X5	X6	св. чл.
4	2	5	1	0	0	190
5	3	4	0	1	0	320
7	9	5	0	0	1	454
-3500	-3200	-1500	0	0	0	0

Итерация №0

Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты

В качестве ведущего выберем  столбец, соответствующий переменной x₁, так как наибольший коэффициент по модулю.

Вычислим значения D _i по строкам как частное от деления

и из них выберем наименьшее:

Следовательно, 1-ая строка является ведущей

Разрешающий элемент равен 4 и находится на пересечении ведущего столбца и ведущей строки

Формируем следующую часть  симплексной таблицы.

Вместо переменной x в план 1 войдет переменная x₁

Строка, соответствующая  переменной x₁ в плане 1, получена в результате деления всех элементов строки x₄ плана 0 на разрешающий элемент РЭ=4

На месте разрешающего элемента в плане 1 получаем 1.

В остальных клетках столбца x₁ плана 1 записываем нули.

Таким образом, в новом  плане 1 заполнены строка x₁ и столбец x₁ .

Все остальные элементы нового плана 1, включая элементы индексной  строки, определяются по правилу прямоугольника.

Для этого выбираем из старого  плана четыре числа, которые расположены  в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.

НЭ = СЭ - (А*В)/РЭ

СТЭ - элемент старого  плана, РЭ - разрешающий элемент (4), А  и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.

Представим расчет каждого  элемента в виде таблицы:

X1	X2	X3	X4	X5	X6	св. чл.
1	1/2	5/4	1/4	0	0	190/4
5	3	4	0	1	0	320
7	9	5	0	0	1	454
3500	3200	1500	0	0	0

X1	X2	X3	X4	X5	X6	св. чл.
1	1/2	5/4	1/4	0	0	190/4
0	1/2	-9/4	-5/4	1	0	165/2
0	11/2	-15/4	-7/4	0	1	243/2
0	-1450	2875	875	0	0

Итерация №1

Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты

В качестве ведущего выберем  столбец, соответствующий переменной x₂, так как наибольший коэффициент по модулю.

Вычислим значения D _i по строкам как частное от деления и из них выберем наименьшее:

Следовательно, 3-ая строка является ведущей

Разрешающий элемент равен 5.5 и находится на пересечении  ведущего столбца и ведущей строки

Формируем следующую часть  симплексной таблицы.

Вместо переменной x в план 2 войдет переменная x₂

Строка, соответствующая  переменной x₂ в плане 2, получена в результате деления всех элементов строки x₆ плана 1 на разрешающий элемент РЭ=5.5

На месте разрешающего элемента в плане 2 получаем 1.

В остальных клетках столбца x₂ плана 2 записываем нули.

Таким образом, в новом  плане 2 заполнены строка x₂ и столбец x₂ .

Все остальные элементы нового плана 2, включая элементы индексной  строки, определяются по правилу прямоугольника.

Для этого выбираем из старого  плана четыре числа, которые расположены  в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.

НЭ = СЭ - (А*В)/РЭ

СТЭ - элемент старого  плана, РЭ - разрешающий элемент (5.5), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.

Представим расчет каждого  элемента в виде таблицы:

Конец итераций: найден оптимальный  план

 

Окончательный вариант симплекс-таблицы:

X1	X2	X3	X4	X5	X6	св. чл.
1	0	159/100	41/100	0	-9/100	729/20
0	0	-191/100	-109/100	1	-9/100	1429/20
0	1	-15/22	-7/22	0	9/50	243/11
0	0	1886.36	413.64	0	263.64

Оптимальный план можно записать так:

x1 = 729/20=36.45

x5 =1429/20= 71.45

x2 =243/11= 22.09

F(X) = 3500*36.45 + 3200*22.09 = 198281.82

 

 

 

 

 

 

Программная реализация

unit Unit1;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, StdCtrls, ExtCtrls;

type

TForm1 = class(TForm)

Label1: TLabel;

Label2: TLabel;

Edit2: TEdit;

Exit: TButton;

Button_Next: TButton;

Edit1: TEdit;

Button_Prev: TButton;

ScrollBox1: TScrollBox;

Conditions: TGroupBox;

Label3: TLabel;

Extrem: TComboBox;

Memo1: TMemo;

procedure ExitClick(Sender: TObject);

procedure Button_NextClick(Sender: TObject);

procedure Button_PrevClick(Sender: TObject);

procedure FormCreate(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

const

mm = 100; nn = 100;

var

Form1: TForm1;

table_changed,done,solve,is_ok,kanon,need_basis,need_i_basis,is_basis,written: boolean;

m,n,y,i_basis,i0,j0,step,iter: integer;{m - элементов , n - ограничений}

pole: array [1..nn, 1..mm] of TEdit; {поля для ввода}

podpis: array [0..nn, 0..mm] of TLabel; {подписи полей}

znak: array [1..nn] of TComboBox; {знаки сравнения ограничений}

matrix: array [1..nn, 1..mm] of double; {массив для рассчетов}

all_basis: array [1..nn] of integer;{номера базисных переменных}

f: text;{файловая переменная для отчета}

tochnost: double;

implementation

{$R *.dfm}

procedure Init;

{инициализация: ввод размеров  системы}

Begin

form1.Button_Prev.Enabled:=false;

form1.Edit1.Enabled:=true;

form1.Edit2.Enabled:=true;

form1.Extrem.Enabled:=true;

form1.ScrollBox1.DestroyComponents;{расчищаем место под табличку}

table_changed:=true;

tochnost:=0.000000001;

assign(f, 'report.htm');

end;

procedure Step1;

{шаг первый: создание  таблички и ввод значений}

var

i,j: integer;

nadpis: string;

begin

form1.Memo1.ReadOnly:=false;

form1.Memo1.Lines.Clear;

form1.Memo1.ReadOnly:=true;

form1.Extrem.Enabled:=true;

if table_changed=true then {если меняли количество эл-тов или ограничений,}

begin     {то создаем новую табличку}

table_changed:=false;

m:=strtoint(form1.Edit1.Text);{считываем количество переменных}

n:=strtoi

nt(form1.Edit2.Text);{и ограничений}

form1.Edit1.Enabled:=false;{блокируем поля для их ввода}

form1.Edit2.Enabled:=false;

i:=0; {используем нулевую  строку массива подписей для  заголовков}

for j:=1 to 3 do {подписываем что is что} 

begin 

podpis[i,j]:=TLabel.Create(Form1.ScrollBox1); 

podpis[i,j].parent:=form1.ScrollBox1; 

podpis[i,j].Left:=5; 

podpis[i,j].Top:=32*(j-1); {расстояние между надписями} 

case j of 

1: nadpis:='Целевая функция:'; 

2: nadpis:='F(x)='; 

3: nadpis:='Система ограничений:';  

end; 

podpis[i,j].Caption:=nadpis;

end;

i:=n+1; {используем последнюю  строку массива полей для целевой ф-ции} 

for j:=1 to m+1 do 

 begin 

 pole[i,j]:=TEdit.Create(Form1.ScrollBox1); 

 pole[i,j].parent:=form1.ScrollBox1; 

 pole[i,j].Height:=20; 

 pole[i,j].Width:=40; 

 pole[i,j].Left:=80*(j-1)+30; 

 pole[i,j].Top:=30; 

 pole[i,j].Text:='0'; 

 if j<=m then 

 begin  

 podpis[i,j]:=TLabel.Create(Form1.ScrollBox1);   

 podpis[i,j].parent:=form1.ScrollBox1;  

 podpis[i,j].Height:=20;  

 podpis[i,j].Width:=20;  

 podpis[i,j].Left:=pole[i,j].Left+pole[i,j].Width+2;   

 podpis[i,j].Top:=pole[i,j].Top+2;  

 podpis[i,j].Caption:='X['+inttostr(j)+']';  

 if j<>m+1 then podpis[i,j].Caption:=podpis[i,j].Caption+' +';  

 {если поле не последнее, то дописываем плюсик} 

 end; 

 end; 

for i:=1 to n do {поля для ввода ограничений}  

 for j:=1 to m+1 do 

 begin 

 pole[i,j]:=TEdit.Create(Form1.ScrollBox1); 

 pole[i,j].parent:=form1.ScrollBox1; 

 pole[i,j].Height:=20; 

 pole[i,j].Width:=40; 

 pole[i,j].Left:=80*(j-1)+5; {расстояние между соседними + отступ от края} 

 pole[i,j].Top:=40*(i-1)+100; 

 pole[i,j].Text:='0'; 

 if j<=m then

begin 

 podpis[i,j]:=TLabel.Create(Form1.ScrollBox1);  

 podpis[i,j].parent:=form1.ScrollBox1; 

 podpis[i,j].Height:=20; 

 podpis[i,j].Width:=20; 

 podpis[i,j].Left:=pole[i,j].Left+pole[i,j].Width+2;  

 podpis[i,j].Top:=pole[i,j].Top+2; 

 podpis[i,j].Caption:='X['+inttostr(j)+']'; 

if j<>m then podpis[i,j].Caption:=podpis[i,j].Caption+' +' 

 {если поле не последнее, то дописываем плюсик; иначе пишем знак}    

 else begin    

 znak[i]:=TComboBox.Create(Form1.ScrollBox1);     

 znak[i].parent:=form1.ScrollBox1;    

 znak[i].Height:=20;    

 znak[i].Width:=40;    

 znak[i].Left:=podpis[i,j].Left+podpis[i,j].Width+25;     

 znak[i].Top:=pole[i,j].Top;    

 znak[i].Items.Insert( 0,'> ');    

 znak[i].Items.Insert( 1,'>=');    

 znak[i].Items.Insert( 2,' =');    

 znak[i].Items.Insert( 3,'<=');    

 znak[i].Items.Insert( 4,'< ');    

 znak[i].ItemIndex:=1;   

 end; 

 end else pole[i,j].Left:=pole[i,j].Left+70; //поля для правой части            

 //ограничений

end; 

end else {если табличку создавать не надо, то разблокируем поля}  

 begin  

 for i:=1 to n+1 do  

 for j:=1 to m+1 do

begin   

 pole[i,j].Enabled:=true;   

 if i<=n then znak[i].Enabled:=true;   

 end;  

 end; 

end;

{/////////////////}

procedure write_system(strok,stolb: integer);

{записывает массив в  виде уравнений} 

var 

i,j: integer; 

begin 

write(f,'<P>F(x) = '); 

for j:=1 to stolb do 

begin 

write(f,matrix[strok,j]:0:3); 

if j<stolb then 

 begin 

 write(f,'x_',j,''); 

 if (kanon=true) and (j=stolb-1) then write(f,' = ') else 

 if (matrix[strok,j+1]>=0) then write(f,' + ') else write(f,' '); 

 end; 

end;

writeln(f,'</P>'); 

writeln(f,'<P>При ограничениях:</P><P>');  

for i:=1 to strok-1 do 

begin 

for j:=1 to stolb do

BEGIN

write(f,matrix[i,j]:0:3); 

 if j<stolb then write(f,'x_',j,' '); 

 if j=stolb-1 then  

 if kanon=false then write(f,' ',znak[i].text,' ')  

 else write(f,' = '); 

 if (matrix[i,j+1]>=0) and (j<stolb-1) then write(f,'+'); 

 end; 

writeln(f,'<br>'); 

end; 

writeln(f,'</P>');  

end;

{/////////////////}

procedure zapisat(strok,stolb: integer; v_strok,v_stolb:integer);

{записывает массив в  виде таблички} 

var 

i,j:integer; 

begin 

writeln(f,'<TABLE BORDER BORDERCOLOR=black CELLSPACING=0 CELLPADDING=5>'); 

for i:=0 to strok do 

begin 

writeln(f,'<TR>'); 

for j:=1 to stolb+1 do 

 begin 

 write(f,'<TD '); 

 if i=0 then 

 begin 

 if (i_basis<>0) and (j>m+y-i_basis) and (j<=m+y) then  

 write(f,'BGCOLOR=yellow ')  

 else  

 write(f,'BGCOLOR=green '); 

 end 

 else 

  

 

 

 if (i=v_strok) or (j=v_stolb) then write(f,'BGCOLOR=silver ') else  

 if (i=strok) or (j=stolb) then   

 if (j<>stolb+1) then write(f,'BGCOLOR=olive ');

write(f,'align='); 

 if (i=0) and (j<stolb) then write(f,'center>X<sub>',j,'<sub>') else  

if (i=0) and (j=stolb) then write(f,'center>св. чл.') else  

 if (i=0) and (j=stolb+1) then write(f,'center>базис') else  

 if (j=stolb+1) then   

 if i<>n+1 then write(f,'center>X_{',all_basis[i],'}') else   

 write(f,'center>&nbsp')  

 else  

  write(f,'right>',matrix[i,j]:1:3); 

 writeln(f,'</TD>'); 

 end; 

writeln(f,'</TR>'); 

end; 

writeln(f,'</TABLE>'); 

end;

{/////////////////}

procedure findved;

{ищет ведущий элемент} 

var 

i,j,k: integer; 

temp: double;

begin 

done:=false; 

solve:=false; 

is_ok:=true; 

temp:=100000; 

i0:=0; 

j0:=0; 

i:=n+1; 

for j:=1 to m+y do

if (i0=0) or (j0=0) then 

 if matrix[i,j]>0 then