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

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

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

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

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

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

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

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

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