Відповідь: Fmax=9,5 Xопт=(0,5;4,5;0;0;0;0)

ЛІТЕРАТУРА

1 Деордіца Ю.С., Нефедов Ю.М. Дослідження операцій в плануванні і управлінні: Навчань допомога. - ДО.: Вища шк., 1991. - 270 с.

2 Кузнецов Ю.Н. Математическое программирование. Высшая школа. 1980р.

3 Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. Математическое программирование. «Наука», 1980 г.

4 Солодовников А.С., Бабайцев В.А., Браилов А.В. Математика в экономике. «Финансы и статистика», 1998 г.

Додаток А

unit SimplexM;

interface

uses

Windows, Messages, SysUtils, Classes, Controls, ExtCtrls,StdCtrls,Grids,

Buttons,Chart, Dialogs;

type

TSimplexM = class(TCustomPanel)

private

FStrGr: TStringGrid;

FLabel1,

FLabel2: TLabel;

FBitBtn1,

FBitBtn2,

FBitBtn3,

FBitBtn4,

FBitBtn5: TBitBtn;

FColX: Integer;

FGroupBox: TGroupBox;

FBottomPanel,

FRightPanel,

FCenterPanel: TPanel;

FRadioButton1,

FRadioButton2: TRadioButton;

maxRow, maxCol, NumMinCol: integer;

Data: array of TStrings;

procedure SetColX (Value: integer);

procedure SGColRow;

{ Private declarations }

procedure Main(var flag: boolean; MaxRow: integer);

function Res(var NumMinCol:integer): boolean;

procedure Resultat(flag: boolean);

procedure MinPlusDate(var Answ: boolean; xov, NumMinCol: integer; var ColSet, RowSet: integer; var date:real);

procedure InputData(var xov, MaxRow: integer);

procedure Name0Str(xov: integer);

procedure Name0Col(xov: integer);

procedure divizion(NumMinCol: integer);

procedure Adding (RowSet, ColSet, Maxcol, MaxRow, NumMinCol:integer);

procedure SaveData;

procedure LoadData;

protected

{ Protected declarations }

FOnBitBtn1Click, FOnBitBtn2Click, FOnBitBtn3Click: TNotifyEvent;

procedure SetBitBtnClick(Sender: TObject);

procedure SetBitBtn4Click(Sender: TObject);

procedure SetBitBtn5Click(Sender: TObject);

public

constructor Create(AOwner: TComponent); override;

{ Public declarations }

published

{ Published declarations }

property Color;

property Caption;

property Align;

property Height;

property ColX: Integer read FColX write SetColX;

property StrGr: TStringGrid read FStrGr write FStrGr;

property Label1: TLabel read FLabel1 write FLabel1;

property Label2: TLabel read FLabel2 write FLabel2;

property BitBtn1: TBitBtn read FBitBtn1 write FBitBtn1;

property BitBtn2: TBitBtn read FBitBtn2 write FBitBtn2;

property BitBtn3: TBitBtn read FBitBtn3 write FBitBtn3;

property RadioButton1: TRadioButton read FRadioButton1 write FRadioButton1;

property RadioButton2: TRadioButton read FRadioButton2 write FRadioButton2;

property OnBitBtn1Click: TNotifyEvent read FOnBitBtn1Click

write FOnBitBtn1Click;

property OnBitBtn2Click: TNotifyEvent read FOnBitBtn2Click

write FOnBitBtn2Click;

property OnBitBtn3Click: TNotifyEvent read FOnBitBtn3Click

write FOnBitBtn3Click;

end;

procedure Register;

implementation

procedure Register;

begin

RegisterComponents('Probnic', [TSimplexM]);

end;

{ TSimplexTab }

constructor TSimplexM.Create(AOwner: TComponent);

begin

inherited Create(AOwner);

FCenterPanel := TPanel.Create(Self);

FCenterPanel.Align := alClient;

FCenterPanel.Parent := Self;

FStrGr := TSTringGrid.Create(Self);

with FStrGr do

begin

Parent := FCenterPanel;

Align := alClient;

Options := [goFixedVertLine, goFixedHorzLine, goVertLine, goHorzLine,

goRangeSelect, GoEditing];

Left := 8;

Top := 8;

Width := 473;

Height := 105;

ColCount := 6;

RowCount := 4;

Cells[0,0] := 'Базис';

Cells[1,0] := 'Св.чл.';

Font.Name := 'Comic Sans MS';

end;

FRightPanel := TPanel.Create(Self);

with FRightPanel do

begin

Parent := Self;

Left := 511;

Top := 1;

Width := 89;

Height := 463;

Align := alRight;

end;

FBottomPanel := TPanel.Create(Self);

with FBottomPanel do

begin

Parent := Self;

Left := 1;

Top := 464;

Width := 599;

Height := 40;

Align := alBottom;

end;

FLabel1 := TLabel.Create(Self);

with FLabel1 do

begin

Parent := FBottomPanel;

Caption := `Оптимальное значение функции:';

Left := 8;

Top := 5;

Height := 13;

Anchors := [akLeft, akBottom];

end;

FLabel2 := TLabel.Create(Self);

with FLabel2 do

begin

Parent := FBottomPanel;

Left := 300;

Top := 5;

Height := 13;

Anchors := [akBottom];

Caption:= '';

end;

FBitBtn1 := TBitBtn.Create(Self);

with FBitBtn1 do

begin

Parent := FRightPanel;

Left := 5;

Top := 16;

Width := 81;

Height := 25;

Anchors := [akTop, akRight];

Kind := bkOk;

Caption := '&Вычислить';

OnClick := SetBitBtnClick;

end;

FBitBtn2 := TBitBtn.Create(Self);

with FBitBtn2 do

begin

Parent := FBottomPanel;

Left := 512;

Top := 5;

Width := 81;

Height := 25;

Anchors := [akRight, akBottom];

Kind := bkClose;

Caption := '&Выход';

TabOrder := 2;

end;

FBitBtn3 := TBitBtn.Create(Self);

with FBitBtn3 do

begin

Parent := FRightPanel;

Left := 5;

Top := 123;

Width := 81;

Height := 25;

Anchors := [akRight, akTop];

Kind := bkRetry;

Caption := '&Очистить';

TabOrder := 2;

OnClick := SetBitBtnClick;

end;

FBitBtn4 := TBitBtn.Create(Self);

with FBitBtn4 do

begin

Parent := FRightPanel;

Left := 5;

Top := 155;

Width := 81;

Height := 25;

Anchors := [akRight, akTop];

Caption := '&Сохранить';

OnClick := SetBitBtn4Click;

end;

FBitBtn5 := TBitBtn.Create(Self);

with FBitBtn5 do

begin

Parent := FRightPanel;

Left := 5;

Top := 182;

Width := 81;

Height := 25;

Anchors := [akRight, akTop];

Caption := '&Читать';

OnClick := SetBitBtn5Click;

end;

FGroupBox := TGroupBox.Create(Self);

with FGroupBox do

begin

Parent := FRightPanel;

Left := 5;

Top := 48;

Width := 81;

Height := 65;

Anchors := [akTop, akRight];

Caption := ' Найти ';

end;

FRadioButton1 := TRadioButton.Create(Self);

with FRadioButton1 do

begin

Parent := FGroupBox;

Caption := 'Min';

Left := 3;

Top := 15;

Width := 60;

Checked := True;

end;

FRadioButton2 := TRadioButton.Create(Self);

with FRadioButton2 do

begin

Parent := FGroupBox;

Caption := 'Max';

Left := 3;

Top := 35;

Width := 60;

end;

Height := 255;

Width := 490;

Constraints.MinHeight := 235;

Constraints.MinWidth := 490;

FColX := 2;

end;

procedure TSimplexM.SetBitBtnClick(Sender: TObject);

var

flag: boolean;

i, j: integer;

begin

if Sender = FBitBtn1 then

begin

if Assigned(FOnBitBtn1Click) then FOnBitBtn1Click(Sender)

else begin

flag := FRadioButton2.Checked;

end;

main(flag, MaxRow);

end;

Exit;

end;

if Sender = FBitBtn3 then

begin

if Assigned(FOnBitBtn3Click) then FOnBitBtn3Click(Sender)

else begin

for i:= 1 to FStrGr.ColCount-1 do

for j := 1 to FStrGr.RowCount-1 do

FStrGr.Cells[i, j] := '';

end;

Label2.Caption:='';

Exit;

end;

end;

procedure TSimplexM.SetColX(Value: integer);

begin

FColX := Value;

FStrGr.ColCount := Value;

SGColRow;

Name0str(FColX);

Name0col(FColX);

end;

procedure TSimplexM.SGColRow; //построение таблицы

begin

maxrow:=2+FColX;

maxcol:=2+2*FColX;

FStrGr.ColCount := 2*FColX+2;

FStrGr.RowCount := 2+FColX;

end;

function TSimplexM.Res(var NumMinCol:integer): boolean;

// ищем отрицательные числа в строке F ,если есть - выходим из цикла

var i: integer;

begin

res:=true;

for i:=2 to MaxCol-1 do

begin

if strtofloat(FStrGr.Cells[i,maxRow-1])<0 then

begin

NumMinCol:=i;

res:=false;

break;

end

end;

end;

procedure TSimplexM.divizion(NumMinCol: integer); // деление гл.строки на нужный коэффициент

var i: integer;

d: real;

begin

d:=strtofloat(FStrGr.Cells[NumMinCol,1]);

for i:=1 to MaxCol-1 do

FStrGr.Cells[i,1]:=floattostr

( (strtofloat(FStrGr.Cells[i,1]))/d );

end;

procedure TSimplexM.Adding(RowSet, ColSet, MaxCol, MaxRow, NumMinCol :integer);

//сложение главной строки с другими для получения нуля

var

i, j: integer;

tmp: string;

t: real;

begin

if RowSet>1 then

begin

for i:=0 to MaxCol-1 do

begin

tmp:=FStrGr.Cells[i,1]; // поднимаем главную строку в первую строку

FStrGr.Cells[i,1]:=FStrGr.Cells[i,RowSet];

FStrGr.Cells[i,RowSet]:=tmp;

end;

end;

divizion(NumMinCol);

for i:=2 to MaxRow-1 do

begin

t:=strtofloat(FStrGr.Cells[NumMinCol,i]); // коффициенты в др.строках

for j:=1 to MaxCol-1 do

begin

if t<0 then FStrGr.Cells[j,i]:=floattostr (strtofloat(FStrGr.Cells[j,1])*abs(t)+strtofloat(FStrGr.Cells[j,i]))

// умножаем на нужный коэффициент другой строки и складываем

else FStrGr.Cells[j,i]:=floattostr (strtofloat(FStrGr.Cells[j,1])*(-t)+strtofloat(FStrGr.Cells[j,i]));

end;

end;

end;

// главная процедура

procedure TSimplexM.Main ( var flag: boolean; MaxRow: integer);

var i, NumMinCol, ColSet, RowSet: integer;

date: real;

Answ, nn: boolean;

begin

Answ:=true;

nn:=false;

if flag then

for i:=2 to FColX+1 do

try

FStrGr.Cells[i,MaxRow-1]:=floattostr

(0-strtofloat(FStrGr.Cells[i,MaxRow-1]))

except

raise Exception.Create('Неверный формат данных');

end

else begin

for i:=2 to FColX+1 do

try

if strtofloat(FStrGr.Cells[i,MaxRow-1])<0 then nn:=true;

except

raise Exception.Create(' Неверный формат данных');

end;

if not nn then

begin

resultat(flag);

exit;

end;

end;

while not Res(NumMinCol) do

begin

MinPlusDate(Answ, FColX, NumMinCol, ColSet, RowSet, date);

if Answ=false then raise Exception.Create('Нет решений') else

begin

FStrGr.Cells[0,RowSet]:='X'+inttostr(ColSet-1);

Adding(RowSet, ColSet, MaxCol, MaxRow, NumMinCol);

end;

end;

resultat(flag);

end;

procedure TSimplexM.MinPlusDate( var Answ: boolean; xov, NumMinCol: integer; var ColSet, RowSet:integer; var date:real);

//ищем наименьшее пложительное от деления св.чл. на гл.неизвестые

var t: real;

i, j, count : integer;

begin

count:=0; // кол-во отрицательных значений в столбце

for i:=1 to MaxRow-2 do

if strtofloat(FStrGr.Cells[NumMinCol,i])<0 then

count:=count+1;

if count=xov then // если кол-во отрицательных значений в столбце равно кол-ву неизвестных, то решения не существует

begin

Answ:=false;

exit;

end;

ColSet:=NumMinCol; // присвоение координат минимального из положительных (нужного) в столбце NumMinCol

RowSet:=1;

j:=1;

repeat

date:=(strtofloat(FStrGr.cells[1,j]))/(strtofloat(FStrGr.cells[NumMinCol,j])); // делим св.член на нужное

j:=j+1;

until date>0;

RowSet:=j-1; // опережает

for i:=j to MaxRow-2 do

begin

t:=(strtofloat(FStrGr.cells[1,i]))/(strtofloat(FStrGr.cells[NumMinCol,i]));

if t > 0 then

if t < date then

begin

date:=t;

RowSet:=i;

end;

end;

end;

procedure TSimplexM.Resultat; // вывод результата на экран

begin

if flag=false then Flabel2.caption:= floattostr

(-strtofloat(FStrGr.Cells[1,MaxRow-1]))

else Flabel2.caption:= FStrGr.Cells[1,MaxRow-1]

end;

procedure TSimplexM.Name0str(xov: integer); //именование нулевой строки

var i, j: integer;

begin

j:=0;

for i:=2 to 2*(xov+1) do

begin

j:=j+1;

FStrGr.Cells[i,0]:='X'+inttostr(j);

end;

end;

procedure TSimplexM.Name0Col(xov: integer); //именование нулевого столбца

var i, j: integer;

begin

j:=xov;

for i:=1 to xov do

begin

j:=j+1;

FStrGr.Cells[0,i]:='X'+inttostr(j);

end;

FStrGr.Cells[0,xov+1]:='F';

end;

procedure TSimplexM.InputData(var xov,MaxRow: integer); // введение количества неизвестных

begin

xov:=FColX;

maxrow:=2+xov;

maxcol:=2+2*xov;

FStrGr.RowCount:=maxrow;

FStrGr.ColCount:=maxcol ;

end;

procedure TSimplexM.SaveData; //сохранение вводимых в таблицу данных

var

i: Integer;

begin

SetLength(Data, FStrGr.Rowcount);

for i := 0 to FStrGr.RowCount do

begin

Data[i] := TStringList.Create;

Data[i].Assign(FStrGr.Rows[i]);

end;

end;

procedure TSimplexM.LoadData; //чтение в таблицу сохранённых данных

var

i: Integer;

begin

for i := 0 to Length(Data) do

begin

FStrGr.Rows[i].Assign(Data[i]);

end;

SetLength(Data, 0);

end;

procedure TSimplexM.SetBitBtn4Click(Sender: TObject);

begin

SaveData;

end;

procedure TSimplexM.SetBitBtn5Click(Sender: TObject);

begin

Label2.Caption:='';

LoadData;

end;

end.

ОПИС ОСНОВНИХ ПРОЦЕДУР І ФУНКЦІЙ

-procedure Main - головна процедура, що викликає всі останні.

-function Res - пошук негативних значень в рядку F

-procedure MinPlusDate - відшукання позитивних коефіцієнтів в головному стовпці і найменшого приватного при діленні базисних невідомих на коефіцієнти в головному стовпці

-procedure divizion - ділення головного рядка на відповідний коефіцієнт

-procedure Adding - отримання нулів, шляхом складання головного рядка, помноженого на відповідний коефіцієнт з іншими рядками

СКРИНШОТЫ

Теорема 3

Если в псевдоплане есть хотя бы одно отрицательное число

b1 ‹0 такое, что все aij ?0, j=1,n то задача вообще не имеет опорных планов.

Теорема 4

Если в псевдоплане Х имеются отрицательные числа b1 ‹0 такие что для любого их них существует хотя бы одно aij ‹0 то можно перейти к новому псевдоплану.

Інструкція користувачу

Запуск програми здійснюється завантаженням виконуваного файлу simplex.exe будь-яким прийнятим в Windows способом. Після завантаження на екрані з'являється головне вікно додатку.

На екран викликається вікно з умовою завдання. Користувач повинен ввести параметри умови завдання, пропоновані програмою. Ці параметри наступні.

У завданні розмірність таблиць встановлена за умовчанням 2 рядки і два стовпці. При необхідності змінити ці значення треба ввести відповідні кількості в поля введення і натиснути кнопку «Створити таблицю», після чого автоматично згенерують таблицю потрібного розміру.

Після введення умови завдання запуск процесу її рішення здійснюється шляхом натиснення кнопки «Завершити заповнення таблиці». Перевіряється правильність введення початкових даних і у випадку, якщо дані введені не вірно видається відповідне повідомлення. В цьому випадку слід перевірити введення початкових даних. Якщо дані введені вірно проводиться рішення задачі подвійним симплекс-методом. На екран на закладці «Рішення» виводяться етапи рішення - подвійна симплекс-таблиця. У кожній подвійній симплекс таблиці рядки і стовпці пойменовані відповідними базисними і вільними невідомими, а останній рядок і стовпець функцією і вільним членом. Рядок і стовпець вирішуючого елементу виділені інверсним кольором. Для кожної таблиці виводиться значення шуканої функції і номери вільної і базисної змінної, які міняються місцями (окрім останньої таблиці). Рішення задачі видно з останньої таблиці. Значення функції виділене окремо, значення змінних, які опинилися у складі вільних приймаються рівними нулю, а значення змінних, які опинилися у складі

Схема алгоритма двойственного симплекс метода