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

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

x 1 = 729/20 = 36.45

x 5 = 1429/20 = 71.45

x 2 = 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 <sub>', j, '</ sub>');

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 <sub>', j, '</ sub>');

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 <sub>', all_basis [i ],'</ sub> ') else

write (f, 'center>')

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 <sub>', all_basis [i0 ],'</ sub> замінюємо на X <sub> ', j0,' </ sub> </ P> ');

all_basis [i0]: = j0;

end;

end;

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

procedure okr;

{Округлює дрібні похибки}

var

i, j: integer;

begin

for i: = 1 to n +1 do

for j: = 1 to m + y +1 do

if abs (matrix [i, j]-round (matrix [i, j])) <tochnost then

matrix [i, j]: = round (matrix [i, j]);

end;

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

procedure preobr;

{Перетворює масив щодо ведучого елемента}

var

i, j, k, l, t: integer;

temp: double;

begin

if done = false then

begin

write (f, '<P> Перерахунок: </ P>');

temp: = matrix [i0, j0];

for j: = 1 to m + y +1 do matrix [i0, j]: = matrix [i0, j] / temp;

for i: = 1 to n +1 do

begin

temp: = matrix [i, j0];

for j: = 1 to m + y +1 do

if (i <> i0) then

matrix [i, j]: = matrix [i, j]-matrix [i0, j] * temp;

end;

okr;

zapisat (n +1, m + y +1, -1, -1);

{///////////////////////// Прибираємо штучний базис ///////////////////// }

if i _ basis> 0 then {якщо він є}

begin

t: = 0;

for j: = m + y - i _ basis +1 to m + y do {від першого ісскусственного елемеента до кінця}

begin

need _ i _ basis: = false; {припускаємо, що елемент не потрібен (*)}

for i: = 1 to n do {переглядаємо стовпець}

if all _ basis [i] = j then {і якщо елемент у базисі}

need _ i _ basis: = true; {тоді він все-таки потрібен}

if need_i_basis = false then t: = j;

{Якщо наші припущення (*) підтвердилися, то запам'ятаємо цей елемент}

end;

if t <> 0 then

begin

for k: = 1 to n +1 do {у всіх рядках}

begin

for l: = t to m + y do {від поточного стовпця до останнього}

matrix [k, l]: = matrix [k, l +1]; {замінюємо елемент на сусідній}

matrix [k, m + y +1]: = 0; {а останній прибираємо}

end;

{Стовпець знищений! треба це запам'ятати}

y: = y-1;

i_basis: = i_basis-1;

if i _ basis> 0 then {якщо залишилися ще штучні змінні,}

for l: = m + y - i _ basis +1 to m + y do {то від першої з них до останньої}

for i: = 1 to n do {переглядаємо рядка у стовпці}

if matrix [i, l] = 1 then all_basis [i]: = l; {туди, де 1, заносимо в базис}

writeln (f, '<P> Штучна мінлива виключена з базису <br>');

writeln (f, 'і може бути вилучена з таблиці.');

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

zapisat (n +1, m + y +1, -1, -1);

end;

end;

{/////////////// Закінчили прибирати штучний базис ////////////////////}

end;

end;

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

procedure otvet;

{Виводить відповідь}

var

i, j: integer;

begin

writeln (f, '<P> <b> ВІДПОВІДЬ: </ b> </ P>');

form1.Memo1.ReadOnly: = false;

form1.Memo1.Lines.Clear;

form1.Memo1.Lines.Add ('ВІДПОВІДЬ:');

form1.Memo1.Lines.Add ('');

if (solve = true) and (i_basis = 0) then

write (f, 'F (');

form1.Memo1.Lines.Text: = form1.Memo1.Lines.Text + 'F (';

if form1.Extrem.ItemIndex = 0 then

begin

write (f, 'max) =' ,0-matrix [n +1, m + y +1]: 0:3);

form1.Memo1.Lines.Text: = form1.Memo1.Lines.Text + 'max) =';

form1.Memo1.Lines.Text: = form1.Memo1.Lines.Text + floattostr (0-matrix [n +1, m + y +1]);

end

else

begin

write (f, 'min) =', matrix [n +1, m + y +1]: 0:3);

form1.Memo1.Lines.Text: = form1.Memo1.Lines.Text + 'min) =';

form1.Memo1.Lines.Text: = form1.Memo1.Lines.Text + floattostr (matrix [n +1, m + y +1]);

end;

writeln (f, '<br> при значеннях: <br>');

form1.Memo1.Lines.Add ('');

form1.Memo1.Lines.Add ('');

form 1. Memo 1. Lines. Add ('при значеннях:');

form1.Memo1.Lines.Add ('');

for j: = 1 to m do

begin

writeln (f, 'x <sub>', j, '</ sub> =');

form1.Memo1.Lines.Text: = form1.Memo1.Lines.Text + 'X [';

form1.Memo1.Lines.Text: = form1.Memo1.Lines.Text + inttostr (j);

form1.Memo1.Lines.Text: = form1.Memo1.Lines.Text + '] =';

written: = false;

for i: = 1 to n do

if all_basis [i] = j then

begin

writeln (f, matrix [i, m + y +1]: 0:3, '<br>');

form1.Memo1.Lines.Text: = form1.Memo1.Lines.Text + floattostr (matrix [i, m + y +1]);

form1.Memo1.Lines.Add ('');

form1.Memo1.Lines.Add ('');

written: = true;

end;

if written = false then

begin

writeln (f, '0 .000 <br> ');

form1.Memo1.Lines.Text: = form1.Memo1.Lines.Text + 0 ";

form1.Memo1.Lines.Add ('');

form1.Memo1.Lines.Add ('');

end;

end;

end else

begin

writeln (f, '<P> Рішення НЕ знайдено. (</ P> ');

form1.Memo1.Lines.Text: = form1.Memo1.Lines.Text + 'Рішення НЕ знайдено. ';

end;

form1.Memo1.ReadOnly: = true;

end;

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

procedure Step2;

{Крок другий: вирішення завдання і формування звіту}

var

i, j: integer;

k: integer;

begin

for i: = 1 to n +1 do

for j: = 1 to m +1 do

begin

matrix [i, j]: = strtofloat (pole [i, j]. Text); {Вводимо значення в масив}

pole [i, j]. Enabled: = false; {Блокуємо поля}

if i <= n then znak [i]. Enabled: = false; {блокуємо знаки}

end;

form1.Extrem.Enabled: = false;

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

{Маємо матрицю [n +1, m +1]}

rewrite (f);

writeln (f, '<HTML>');

writeln (f, '<HEAD>');

writeln (f, '<TITLE> Звіт </ TITLE>');

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

writeln (f, '<BODY>');

writeln (f, '<H1> Звіт </ H1>');

write (f, '<P> <b> Необхідно');

if form1.Extrem.ItemIndex = 0 then write (f, 'макс') else write (f, 'хв');

writeln (f, 'імізіровать цільову функцію: </ b> </ P>');

kanon: = false; {ще не в канонічній формі}

write_system (n +1, m +1); {Виведемо її до звіту}

{Приведемо її до канонічного вигляду}

writeln (f, '<P> <b> Наведемо до канонічного вигляду: </ b> </ P>');

y: = 0; {кількість додаткових змінних}

need_basis: = false;

for i: = 1 to n do

if znak [i]. ItemIndex <> 2 then {якщо обмеження не є рівністю}

begin

y: = y +1; {вводимо додаткову змінну, для цього:}

for k: = 1 to n +1 do begin {у всіх обмеженнях і в ЦФ}

{Перед правою частиною додаємо стовпець}

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

matrix [k, m + y]: = 0; {складається з нулів}

end;

{А в поточному обмеження, якщо знак був> або> =}

if (znak [i]. ItemIndex = 0) or (znak [i]. ItemIndex = 1) then

begin

matrix [i, m + y]: =- 1; {записуємо -1}

need_basis: = true;

end

else {інакше, тобто у разі <або <=}

matrix [i, m + y]: = 1; {записуємо 1}

end

else need_basis: = true;

{ЦФ прирівнюється до нуля, а вільний член переноситься в праву частину:}

matrix [n +1, m + y +1]: = 0-matrix [n +1, m + y +1];

{Праві частини обмежень повинні бути ненегативні, перевіримо це:}

for i: = 1 to n do {для всіх обмежень}

if matrix [i, m + y +1] <0 then {якщо права частина негативна,}

{То забираємо всю рядок від нуля}

for j: = 1 to m + y +1 do matrix [i, j]: = (0-matrix [i, j]);

kanon: = true; {система приведена до канонічного вигляду}

{Виведемо її до звіту}

write_system (n +1, m + y +1);

{Якщо ф-ція на мінімум, то потрібно поміняти знаки в останньому рядку}

if form1.Extrem.ItemIndex = 1 then

for j: = 1 to m + y +1 do matrix [n +1, j]: = 0-matrix [n +1, j];

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

{////////////////////////// Тут треба ввести базис /////////////////// ////////}

i_basis: = 0;

for i: = 1 to n do {то у всіх обмеженнях}

begin

is_basis: = false;

for j: = 1 to m + y do

if (matrix [i, j] = 1) then

if (is_basis = false) then

begin

all_basis [i]: = j;

is_basis: = true;

for k: = 1 to n do

if k <> i then

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

if (is_basis = true) then

begin

is_basis: = false;

all_basis [i]: = 0;

end;

end;

if is_basis = false then

begin

i_basis: = i_basis +1;

y: = y +1;

for k: = 1 to n +1 do

begin {у всіх обмеженнях і в ЦФ}

{Перед правою частиною додаємо стовпець}

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

matrix [k, m + y]: = 0; {складається з нулів}

end;

matrix [i, m + y]: = 1;

all_basis [i]: = m + y;

end;

end;

{//////////////// Закінчили введення штучного базису //////////////////////}

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

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

{//////////////// Тепер треба від нього позбавитися //////////////////////////// }

if i _ basis> 0 then

begin

write (f, '<H 2> Необхідно ввести штучний базис </ H 2>');

zapisat (n +1, m + y +1, -1, -1);

writeln (f, '<P> Штучний базис введений. <br>');

writeln (f, 'Позбувшись від нього, отримаємо перше допустиме рішення </ P>');

iter: = 0;

repeat

inc (iter);

findved;

preobr;

until (i_basis = 0) or (iter = 20) or (done = true);

if i_basis = 0 then

begin

writeln (f, '<P> Штучний базис виведений повністю. <br>');

writeln (f, 'Отримано першу допустиме рішення! </ P>');

end

else

begin

writeln (f, '<P> Не вдалося вивести штучний базис. <br>');

writeln (f, 'Рішення не знайдено. </ P>');

end;

end;

{//////////////////////// Спроби позбавлення закінчені ////////////////////// / /}

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

{/////////////////////////////// SIMPLEX START //////////////// /////////////}

if i_basis = 0 then

begin

iter: = 0;

findved;

if done = false then

begin

writeln (f, '<H2> Застосовуємо симплекс метод </ H2>');

repeat

inc (iter);

findved;

preobr;

until (done = true) or (iter = 20);

end;

end;

otvet;

{/////////////////////////////// SIMPLEX END //////////////// ///////////////}

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

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

CloseFile (f);

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

end;

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

{///////// Все, що нижче, відноситься до переходів між кроками ////////////////}

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

procedure TForm1.ExitClick (Sender: TObject);

begin

Close ();

end;

procedure TForm1.Button_NextClick (Sender: TObject);

begin

step: = step +1;

Form1.Button_Prev.Enabled: = true;

case step of

1: Step1;

2: begin

Step2;

Form1.Button_Next.Enabled: = false;

end;

else step: = step-1;

end;

form1.Caption: = 'Симплекс метод - крок' + inttostr (step);

end;

procedure TForm1.Button_PrevClick (Sender: TObject);

begin

step: = step-1;

Form1.Button_Next.Enabled: = true;

case step of

0: begin

Init;

Form1.Button_Prev.Enabled: = false;

end;

1: Step1;

else step: = step +1;

end;

form1.Caption: = 'Симплекс метод - крок' + inttostr (step);

end;

procedure TForm1.FormCreate (Sender: TObject);

begin

Init;

end;

Висновок

У цій роботі було розглянуто рішення задач лінійного програмування симплекс методом. Задача була вирішена симплекс методом, так само завдання було вирішено графічно (побудований графік). Для представленої задачі була складена програма на мові Delphi, програма знаходить значення цільової функції за умови максимізації значення.

Таким чином, обчислювальна техніка в даний час знаходить широке застосування, як у загальній математики, так і в одному з її розділів - математичних методах.

Список використаної літератури

1. Зайченко Ю.П., Шумилова С.А. Дослідження операцій.

2. Ліщенко «Лінійне і нелінійне програмування», М. 2003

3. О.М. Карасьов, Н.Ш. Кремер, Т.М. Савельєва «Математичні методи в економіці», М.2000

4. Орлов О.І. Теорія прийняття рішень. Навчальний посібник. - М.: Видавництво "Март", 2004

5. Інтернет