Решение задач линейного программирования симплекс методом

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

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

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

Cj - коэффициент целевой функции в столбце j, aij - коэффициент в столбце j и строке i.

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

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

4 x1 + 2 x2 + 5 x3 <=190

5 x1 + 3 x2 + 4 x3 <=320

7 x1 + 9 x2 + 5 x3 <=454

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

4x1 + 2x2 + 5x3 + 1x4 + 0x5 + 0x6 = 190

5x1 + 3x2 + 4x3 + 0x4 + 1x5 + 0x6 = 320

7x1 + 9x2 + 5x3 + 0x4 + 0x5 + 1x6 = 454

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

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

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

x4 , x5 , x6

Полагая, что свободные переменные равны 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

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

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

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

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

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

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

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

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

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

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

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

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

Все остальные элементы нового плана 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

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

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

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

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

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

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

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

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

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

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

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

Все остальные элементы нового плана 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

begin

j0:=j;

for k:=1 to n do

if (matrix[k,j]>0) then

if (matrix[k,m+y+1]/matrix[k,j]<temp) then

begin

temp:=matrix[k,m+y+1]/matrix[k,j];

i0:=k;

end;

end;

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

for j:=1 to m do

if matrix[n+1,j]=0 then

for i:=1 to n do

if (matrix[i,j]<>0) and (matrix[i,j]<>1) then

begin

is_ok:=false;

j0:=j;

end;

if is_ok=false then

begin

temp:=100000;

for k:=1 to n do

if (matrix[k,j0]>0) then

if (matrix[k,m+y+1]/matrix[k,j0]<temp) then

begin

temp:=matrix[k,m+y+1]/matrix[k,j0];

i0:=k;

end;

end;

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

begin

writeln(f, '<P>Конец вычислений</P>');

done:=true;

solve:=true;

end

else if (j0<>0) and (i0=0) then

begin

writeln(f, '<P>Не удается решить систему</P>');

done:=true;

solve:=false;

end

else

if iter<>0 then

begin

writeln(f,'<P><b>Итерация ',iter,'</b></P>');

writeln(f, '<P>Найдем ведущий элемент:</P>');

zapisat(n+1,m+y+1,i0,j0);

writeln(f,'<P>Ведущий столбец: ',j0,'<br>Ведущая строка: ',i0,'</P>');

write(f,'<P>В строке ',i0,': базис ');

writeln(f,'X_{',all_basis[i0],'} заменяем на X_',j0,'</P>');