Решение задач оптимизации симплекс-методом

 

 

 

 

 

 

 

 

 

 

Курсовая работа

 

по дисциплине «Основы алгоритмитизации и программирование»

 

на тему: «Решение задач оптимизации симплекс-методом»

 

 

 

 

 

 

 

 

 

 

 

 

 

                                                       

 

 

 

 

 

 

 

 

 

 

 

 

Содержание:

 

1. Цель работы…………………………………………………………3

2. Постановка задачи…………………………………………….……4

3. Описание метода решения………………………………………….5

4. Программная реализация…………………………………………..7

  4.1. Описание основных  процедур и функций……………………..7

  4.2. Блок-схемы основных  процедур……………………………….8

  4.3. Листинг………………………………………………………….15

5. Контрольный пример………………………………………………26

6. Инструкция пользования…………………………………………..28

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1.Цель работы.

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2.Постановка  задачи.

На основе изученного алгоритма симплекс-метода создать  работающее программное приложение в виде компонента для решения  задач по отысканию максимума  или минимума функции.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3.Описание  метода.

Для решения  производственных задач линейного  программирования существует множество  методов. Рассмотрим один из них.

Симплексный метод

Симплексный метод  задач линейного программирования основан на переходе от одного опорного плана к другому, при котором значение целевой функции возрастает (при условии, что данная задача имеет оптимальный план, и каждый ее опорный план является невырожденным). Указанный переход возможен, если известен какой-нибудь исходный опорный план. Рассмотрим задачу, для которой этот план можно непосредственно записать.

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

 

ƒ = C₀ + C₁x₁ + C₂x₂ +...+ C_nx_n

 

и система m линейных уравнений с n неизвестными. Это называется системой ограничений:

 

a₁₁x₁ + a₁₂x₂ +...+ a_1nx_n = b₁

a₂₁x₁ + a₁₂x₂ +...+ a_2nx_n = b₂

  ...

a_m1x₁ +a_m2x₁₂ +...+ a_mnx_n = b_m

 

 

Целевую функцию  представим в виде:

 

ƒ - C₁x₁-C₂x₂ -...-C_nx_n = C₀

 

Составим симплекс-таблицу.В дальнейшем будем считать, что ранг матрицы системы ограничений равен r.В системе ограничений выбран базис(основные неизвестные)x₁,x₂,...x_n и коэффициенты в правой части не отрицательны.

В этом случае система ограничений  будет иметь вид:

 

 

x₁ +...+ a_1,r+1x_r+1 +...+ a_1nx_n = b₁

                 x₂ + a_2,r+1x_r+1 +...+ a_2nx_n = b₂

       ...

                  x_r+ a_r,r+1x_r+1 +...+ a_rnx_n = b_r

 

 

Тогда целевая функция  имеет вид:

 

 

ƒ + C_r+1x_r+1 + C_r+2x_r+2 -...- C_nx_n = C₀

 

 

Нахождение  оптимального плана симплексным методом включает    следующие этапы:

1. Находят опорный  план.

  2. Составляют  симплекс-таблицу. В общем виде:

 

Базисные неизвестныеСвободные членыx₁x_2...x_rx_r+1x_jx_nx₁

x₂

_...

x_i

_...

x_rb₁

b₂

_...

b_i

_...

b_r1

0

_...

0

_...

00

1

 

0

 

00

0

_...

0

_...

1a_1,r+1

a_2,r+1

_...

a_i,r+1

_...

a_r,r+1a_1j

a_2j

_...

a_ij

_...

a_rja_1n

a_2n

_...

a_in

_...

a_rnƒC₀00_...0C_r+2C_jC_n

 

3. В нижней  строчке симплекс-таблицы необходимо  отыскать отрицательные числа  (не считая коэффициент С_о). Если таких чисел нет, то данное базисное решение является оптимальным.

4. Пусть элемент С_j<0,тогда в j-ом столбце необходимо найти положительный элемент. Если все коэффициенты этого столбца отрицательные, то решения не существует.

5. Если положительный  коэффициент в j-ом столбце  один, то выбранную строку с номером i надо поделить все коэффициенты на число a_ij.Результат деления записываем в новую симплекс-таблицу. Если же положительных коэффициентов несколько, необходимо составить отношение b_i/a_ij и из полученных значений выбрать наименьшее, соответствующее i-ой строке.

6. В новой симплекс-таблице  в столбце базисных неизвестных  вместо x_i пишется x_j. Продолжается заполняться таблица. В столбце с номером j необходимо получить нули(включая строку с целевой функцией). Для этого надо умножить i-ую записанную строку на нужное число и сложить с остальными строками.

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

 

4.1.Описание  основных процедур и функций

-procedure Main – главная  процедура, вызывающая все остальные.

-function  Res –  поиск отрицательных значений  в строке F

-procedure MinPlusDate –  отыскание положительных коэффициентов  в главном столбце и наименьшего  частного при делении базисных неизвестных на коэффициенты в главном столбце

-procedure divizion – деление  главной строки на соответствующий  коэффициент

-procedure Adding – получение  нулей, путём сложения главной  строки, умноженной на соответствующий  коэффициент с другими строками

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

4.2.Блок-схемы  основных процедур

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

4.3.Листинг

 

 

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);