Симплекс-метод в СП DELPHI (стр. 1 )

Научно-практическая конференция учащихся и педагогов

«Первые шаги в науку»

Симплекс-метод в СП DELPHI

Выполнил:

ученик 11 класса

ГУО«Речицкий районный лицей»

Научный руководитель –

учитель информатики

ГУО«Речицкий районный лицей»

Брянск, 2013

Содержание

1. Введение……………………………………………………………………..….3

2. Описание работы…………………………………………………………….....4

2.1. Определение Симлекс-метода. Предназначение Симплекс-метода….….4

2.2. Составление программы нахождения максимума с помощью симплекс метода на DELPHI………………………………………………………………...6

2.3. Рабочий вид программы…………………………………………………....9

3. Литература…………………………………………………………………….12

4. Приложение…………………………………………………………………..13

1. Введение

Цель работы:

· Изучить Симплекс-метод и рассмотреть его применение;

· Научиться решать данным методом серию экономических задач;

· Используя среду разработки Borland Delphi составить программу, осуществляющую решение задач с использованием Симплекс-метода;

2. Описание работы

2.1. Определение Симплекс-метода. Предназначение Симплекс-метода

Симплекс-метод — алгоритм решения оптимизационной задачи линейного программирования путём перебора вершин выпуклого многогранника в многомерном пространстве.

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

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

Далее эта система оформляется в виде симплекс-таблиц

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

строке отрицательных элементов среди базисных неизвестных.) .

Алгоритм перехода к следующей таблице такой:

· просматривается последняя строка (в которой начиная со второго столбца и по (m+1)ый находятся коэффициенты целевой функции взятые с противоположным знаком ) таблицы и среди коэффициентов этой строки (исключая столбец свободных членов ) выбирается наименьшее число при отыскании максимума или наибольшее при поиске минимума(пока эти коэффициенты меньше 0). Если такового нет, то исходное базисное решение является оптимальным и данная таблица является последней;

· просматривается столбец таблицы, отвечающий выбранному отрицательному (положительному) коэффициенту в последней строке является ключевым, и в этом столбце выбираются положительные коэффициенты. Если таковых нет, то целевая функция неограниченна на области допустимых значений переменных и задача решений не имеет;

· среди выбранных коэффициентов столбца выбирается тот, отношения свободного члена (находящегося в столбце свободных членов) к этому элементу минимальна. Этот коэффициент называется разрешающим, а строка в которой он находится ключевой;

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

· разделим каждый элемент ключевой строки (исключая столбец свободных членов) на разрешающий элемент и полученные значения запишем в строку с измененной базисной переменной новой симплекс таблицы.

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

· в новой таблице все элементы ключевого столбца = 0, кроме разрезающего, он всегда равен 1.

· столбец, у которого в ключевой строке имеется 0,в новой таблице будет таким же.

· строка, у которой в ключевом столбце имеется 0,в новой таблице будет такой же.

·

Элемент Ключевой строки

Элемент Ключевого столбца

Старый элемент

Новый элемент

в остальные клетки новой таблицы записывается результат преобразования элементов старой таблицы по следующему принципу:

= - *

2.2. Составление программы нахождения максимума с помощью симплекс-метода на Delphi

На вкладке общая задача, выбирается количество переменных и количество систем ограничений. После этого составляется система ограничений и целевая функция, в которых в поле TEdit вставляются коэффициенты. При нажатии кнопки «Вычислить» программа, как и в частном случае( Пример1,Пример2) ,составляет двумерный массив и обращается к процедуре drogba11 с помощью, которой симплексным методом находится максимум целевой функции

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

min:=maxlongint;

For i:=2 to m+1 do

begin

If (A[n+1,i]<min) then

begin

min:=A[n+1,i];

e:=i;

end;

end;

If min=0 then break;

Просматривается столбец таблицы, отвечающий выбранному отрицательному (минимальному) коэффициенту и выбирается тот, отношения свободного члена (находящегося в столбце свободных членов) к этому элементу минимальна.

min:=maxlongint;

For i:=1 to n do

begin

If (A[i,1]/abs(A[i, e]))<min then

begin

min:=A[i,1]/A[i, e];

v:=i;

s:=A[i, e];

end;

end;

После чего происходит преобразование старой таблицы

For i:=1 to 2*n do

A[v, i]:=A[v, i]/s;

For i:=1 to n+1 do

begin

If i<>v then

begin

s:=A[i, e];

A[i, e]:=0;

For j:=1 to 2*n do

begin

If j<>e then

begin

A[i, j]:=A[i, j]-(A[v, j]*s);

end;

end;

end;

end;

Находим значения переменных, при которых достигается максимум

For i:=1 to n do

For j:=2 to m+1 do

If A[i, j]=1 then X[j-1]:=A[i,1]

2.3. Рабочий вид программы.

Программа представляет собой форму, на которой расположены вкладки, в которых находятся примеры применения симплекс-метода и общая программа для произвольных случаев

Вид программы при выборе вкладки «Пример 1»

Вид программы при выборе вкладки «Пример 2»

Вид программы при выборе вкладки «Общая задача»

3. Литература

Интернет-энциклопедия Википедия – http://wikipedia. org

Интернет-портал – http://matmetod-popova. *****

Интернет-портал – http://simplex-metod. *****

4. Приложение

unit Unit1;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, ComCtrls, StdCtrls, Grids, ExtCtrls, DB, DBTables, acPNG,

sSkinManager;

type

TForm1 = class(TForm)

PageControl1: TPageControl;

TabSheet2: TTabSheet;

TabSheet1: TTabSheet;

Label1: TLabel;

Label2: TLabel;

Label3: TLabel;

Label4: TLabel;

Label5: TLabel;

Label6: TLabel;

Label7: TLabel;

Label8: TLabel;

Label9: TLabel;

Label10: TLabel;

Label11: TLabel;

Label12: TLabel;

Label13: TLabel;

Label14: TLabel;

Label15: TLabel;

Label16: TLabel;

Label17: TLabel;

Label18: TLabel;

Label19: TLabel;

Label20: TLabel;

Label21: TLabel;

Label22: TLabel;

Label23: TLabel;

Label24: TLabel;

Label25: TLabel;

Label26: TLabel;

Label27: TLabel;

Label28: TLabel;

Image2: TImage;

Image3: TImage;

Image4: TImage;

Label29: TLabel;

Label32: TLabel;

Label31: TLabel;

Label33: TLabel;

Label35: TLabel;

Label36: TLabel;

Label30: TLabel;

Label34: TLabel;

Image5: TImage;

Label37: TLabel;

Label38: TLabel;

Label39: TLabel;

Label41: TLabel;

Label42: TLabel;

Label43: TLabel;

Label40: TLabel;

Label44: TLabel;

Label45: TLabel;

Panel1: TPanel;

Panel2: TPanel;

Panel3: TPanel;

Panel4: TPanel;

Panel5: TPanel;

Panel6: TPanel;

Panel7: TPanel;

Panel8: TPanel;

Panel9: TPanel;

Panel10: TPanel;

Panel11: TPanel;

Panel12: TPanel;

Panel13: TPanel;

Panel14: TPanel;