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

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Введение

Линейное программирование -- математическая дисциплина, посвящённая теории и методам решения экстремальных задач на множествах n-мерного векторного пространства, задаваемых системами линейных уравнений и неравенств.

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

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

Термин «программирование» нужно понимать в смысле «планирования». Он был предложен в середине 1940-х годов Джорджем Данцигом, одним из основателей линейного программирования, ещё до того, как компьютеры были использованы для решения линейных задач оптимизации.

Алгоритмы решения общей задачи линейного программирования

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

Первый полиномиальный алгоритм, метод эллипсоидов, был предложен в 1979 г. советским математиком Л. Хачияном, разрешив таким образом проблему, долгое время остававшуюся нерешённой. Метод эллипсоидов имеет совершенно другую, некомбинаторную, природу, нежели симплекс-метод. Однако в вычислительном плане этот метод оказался неперспективным. Тем не менее сам факт полиномиальной сложности задач привёл к созданию целого класса эффективных алгоритмов ЛП -- методов внутренней точки, первым из которых был алгоритм Н. Кармаркара, предложенный в 1984 году. Алгоритмы этого типа используют непрерывную трактовку задачи ЛП, когда вместо перебора вершин многогранника решений задачи ЛП осуществляется поиск вдоль траекторий в пространстве переменных задачи, не проходящих через вершины многогранника. Метод внутренних точек, который, в отличие от симплекс-метода, обходит точки из внутренней части области допустимых значений, использует методы логарифмических барьерных функций нелинейного программирования, разработанные в 60-х гг. Фиако (Fiacco) и МакКормиком (McCormick).

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

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

Производитель элементов центрального отопления изготавливает радиаторы четырёх моделей. Ограничения на производство, обусловлены количеством рабочей силы и количеством стальных листов, из которых изготавливаются радиаторы, соответственно равны 500, 2500. Определить максимальную прибыль от продажи радиаторов, используя симплекс-метод. Все необходимые данные приведены в таблице.

Модель радиатора	А	B	C	D
Необходимое количество рабочей силы, человеко-часы	0,5	1,5	2	1,5
Необходимое количество стального листа,	4	2	6	8
Прибыль от продажи одного радиатора, дол.	5	5	12,5	10

2. Математическая модель

Для того чтобы составить математическую модель, вводятся следующие обозначения:

- количество радиаторов А

- количество радиаторов В

- количество радиаторов С

- количество радиаторов D

Ограничения по количеству рабочей силы:

0,5+1,5+2+1,5?500

Ограничения по количеству стальных листов:

4+2+6+8?2500

Т.к. прибыль должна быть максимальной, задача будет иметь вид:

F=5+5+12,5+10max

xj?0 (j=)

Для того чтобы решить задачу с помощью симплекс-метода приведём систему ограничений к каноническому виду:

3. Обзор и анализ существующих методов решения задачи

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

Заметим, что каждое из линейных неравенств на переменные ограничивает полупространство в соответствующем линейном пространстве. В результате все неравенства ограничивают некоторый многогранник (возможно, бесконечный), называемый также полиэдральным конусом. Уравнение W(x) = c, где W(x) -- максимизируемый (или минимизируемый) линейный функционал, порождает гиперплоскость L(c). Зависимость от c порождает семейство параллельных гиперплоскостей. Тогда экстремальная задача приобретает следующую формулировку -- требуется найти такое наибольшее c, что гиперплоскость L(c) пересекает многогранник хотя бы в одной точке. Заметим, что пересечение оптимальной гиперплоскости и многогранника будет содержать хотя бы одну вершину, причём, их будет более одной, если пересечение содержит ребро или k-мерную грань. Поэтому максимум функционала можно искать в вершинах многогранника. Принцип симплекс-метода состоит в том, что выбирается одна из вершин многогранника, после чего начинается движение по его рёбрам от вершины к вершине в сторону увеличения значения функционала. Когда переход по ребру из текущей вершины в другую вершину с более высоким значением функционала невозможен, считается, что оптимальное значение c найдено.

Последовательность вычислений симплекс-методом можно разделить на две основные фазы:

1.нахождение исходной вершины множества допустимых решений,

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

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

4. Описание выбранного алгоритма

Алгоритм:

1. Просматриваем m+1 строку, если среди оценок есть отрицательное, то выбираем минимальную среди отрицательных оценок.

Столбец соответствующий этому условию называется разрешающим столбцом.

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

3. Элемент, стоящий на пересечении разрешающего столбца и разрешающей строки называется разрешающим элементом.

4. Заполняем новую симплексную таблицу, для этого:

a) разрешающую строку делим на разрешающий элемент и записываем в новую таблицу на это же место;

b) все остальные элементы пересчитываются по методу Джордано-Гаусса (метод прямоугольников)

J		k
aij	…	aik
…	…	…
amj	…	amk

5. В новой симплексной таблице заполняется m+1 строка, если все оценки не отрицательны, то полученный опорный план оптимальный, если среди оценок есть хотя бы одна отрицательная оценка, то переходим к пункту 1 алгоритма.

Примечание: Если задача линейного программирования решается на min, то изменяется пункт 1: среди оценок выбирается max среди положительных оценок , и далее переходим к пункту 2 алгоритма

5. Средства решения задачи

5.1 Технические средства решения задачи

Оценка: 5.0 Индекс производительности Windows

Процессор: AMD Athlon™ 64 X2 Dual Core Processor 5200+ 2.70 GHz

Установленная память(ОЗУ): 2.00 ГБ

Тип системы: 32-х разрядная операционная система

5.2 Инструментальные средства разработки

Borland Delphi

Говоря о том или ином средстве разработки приложений, всегда хочется понять, какие тенденции приводят к его появлению. Borland Delphi не является исключением из правил. Итак, что же мы имели к середине 90-х? Одно направление - объектно-ориентированный подход, хорошо структурирующий задачу, как таковую, так и ее решение в виде прикладной системы. Другое направление, возникшее во многом благодаря объектной ориентации, - визуальные средства быстрой разработки приложений (RAD - Rapid Application Development), основанные на компонентной архитектуре. Третья тенденция - использование компиляции, а не интерпретации. Это объясняется тем, что скоростные характеристики компилируемых приложений в десятки раз лучше, чем у систем, использующих интерпретатор. При этом повышается легкость отчуждаемости готовых систем, так как отпадает необходимость "таскать за собой" сам интерпретатор (run-time), выполненный обычно в виде динамической библиотеки и занимающий в лучшем случае несколько сотен килобайт (а большинстве случаев два-три мегабайта). Отсюда и меньшая ресурсоемкость систем. Четвертая тенденция - возможность работы с базами данных универсальными (единообразными) методами. Если мы попытаемся оценить процент систем, которые так или иначе требуют обработки структурированной информации (как для внутрикорпоративного использования, так и для коммерческого или иного распространения), то окажется, что цифра 60- 70% может представлять лишь нижнюю границу.

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

6. Информационное обеспечение задачи

6.1 Входная информация

Входная информация в приложении - это ввод количества базовых переменных, количества переменных, степени точности, задача (на max, на min):

1. Количество базовых переменных

2. Количество переменных

3. Степень точности

1. Задача (на max, на min)

6.2 Выходная информация

Выходная информация в приложении - это таблицы, в первую таблицу заносится условие задачи, во второй таблице будут отражены промежуточные результаты i-ой итерации

1. Таблица, в которую заносится условие задачи

2. Результаты i-ой итерации

7. Программное обеспечение задачи

7.1 Описание программного продукта

В моём приложении 6 процедур:

//по вводу данных формируются матрицы на форме2 "Решение"

procedure TForm1.Button1Click(Sender: TObject);

//процедура ввода данных задачи

procedure TForm1.FormCreate(Sender: TObject);

//процедура решения k-й таблицы

procedure TForm2.resh;

//процедура формирования новой таблицы

procedure TForm2.newtab;

//процедура решения по кнопке "Вычислить"

procedure TForm2.Button1Click(Sender: TObject);

//по закрытию формы - выход из программы

procedure TForm2.FormClose(Sender: TObject; var Action: TCloseAction);

7.2 Руководство пользователю

1.Открыть Program.exe, появится окно приложения, вводим в него количество переменных, количество базовых переменных и степень точности, затем выбираем на максимум или на минимум, нажать кнопку начать, появится форма для ввода задачи

2.Форма для ввода задания

3. Вводим данные в таблицу и нажимаем кнопку «Решение»

4. После нажатия кнопки производится вычисление задачи, высвечивается сообщение с результатом i-ой итерации



На сообщении нажимаем кнопку «ОК», выводится последняя таблица с конечным результатом.

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

Заключение

В процессе работы над курсовым проектом были закреплены, ранее полученные знания по линейному программированию, в частности по решению задач линейного программирования симплекс-методом. А также получены практические навыки по созданию алгоритма вычисления задач в среде ООП Delphi 7.В результате моего курсового проекта было получено решение задачи на нахождение максимальной прибыли от продажи радиаторов, симплекс- методом.

Список литературы

Методы оптимизации в примерах и задачах: Учеб. пособие/ А. В. Пантелеев, Т.А. Летова. - М.: Высш. шк., 2002. - 544.

Конспект по “Мат. Методам”

Приложение

program Program;

uses

Forms,

Unit1 in 'Unit1.pas' {Form1},

Unit2 in 'Unit2.pas' {Form2};

//Unit4 in 'Unit4.pas' {Form4};

{$R *.res}

begin

Application.Initialize;

//Application.CreateForm(TForm4, Form4);

Application.CreateForm(TForm1, Form1);

Application.CreateForm(TForm2, Form2);

Application.Run;

end.

//ФОРМИРОВАНИЕ МАТРИЦ НА ФОРМЕ

unit Unit1;

interface

uses

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

Dialogs, StdCtrls, ExtCtrls, Spin;

type

TForm1 = class(TForm)

Button1: TButton;

Edit1: TEdit;

Edit2: TEdit;

Label1: TLabel;

Label2: TLabel;

panel1: TPanel;

Label3: TLabel;

SpinEdit1: TSpinEdit;

RadioButton1: TRadioButton;

RadioButton2: TRadioButton;

Label4: TLabel;

Label5: TLabel;

procedure Button1Click(Sender: TObject);

procedure FormCreate(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

Form1: TForm1;

mgl:array[1..200,1..200] of tedit;

strm:array[1..100] of tedit;

mp:array[1..2,1..100] of tedit;

x,y:integer;

e:longint;

maxmin:integer;

prz:byte;

sh:byte;

implementation

uses Unit2, Unit3;

{$R *.dfm}

//по вводу данных формируются матрицы на форме2 "Решение"

procedure TForm1.Button1Click(Sender: TObject);

var i,j,k,xtop,yleft:integer;

const cx=45;

ch=20;

nleft=-30;

ntop=80;

cy=20;

cw=45;

begin

inc(sh);

e:=SpinEdit1.Value;

if RadioButton1.Checked then maxmin:=-1 else maxmin:=1;

if (Edit2.Text='')or(Edit1.Text='')or(Edit2.Text='0')or(Edit1.Text='0')

then begin showmessage('Введите значение >0');exit;end;

x:=strtoint(Edit1.Text)+3;

y:=strtoint(Edit2.Text);

for i:=1 to y do

begin

xtop:=ntop+i*cy;

for j:=1 to x do

begin

yleft:=nleft+j*cx;

if (i=1)and(j>2) then

begin

strm[j-2]:=tedit.Create(Form2);

with strm[j-2] do

begin

Parent:=Form2;

Top:=ntop+y*cy+30;

Left:=yleft;

Width:=cw;

Height:=ch;

end;

end;

if (i=1)and(j>3) then

for k:=1 to 2 do

begin

mp[k,j-3]:=tedit.Create(Form2);

with mp[k,j-3] do

begin

Parent:=Form2;

Top:=50+(k-1)*20;

Left:=yleft;

Width:=cw;

Height:=20;

end;

end;

mgl[i,j]:=tedit.Create(Form2);

with mgl[i,j] do

begin

Parent:=Form2;

Top:=xtop;

Left:=yleft;

Width:=cw;

Height:=ch;

end;

end;

end;

Form2.Show;

form1.Visible:=false;

end;

//ввод данных моей задачи

procedure TForm1.FormCreate(Sender: TObject);

begin

Edit1.Text:='12';

Edit2.Text:='7';

RadioButton1.Checked:=true;

end;

end.

//ФОРМА РЕШЕНИЯ

unit Unit2;

interface

uses

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

Dialogs, StdCtrls, Mask, ExtCtrls, jpeg;

type

TForm2 = class(TForm)

Button1: TButton;

Edit1: TEdit;

Edit2: TEdit;

Edit3: TEdit;

Button3: TButton;

Label2: TLabel;

Label3: TLabel;

procedure Button1Click(Sender: TObject);

procedure resh(var x1,y1:byte;var rm:real;var pr:boolean);

procedure newtab(x1,y1:byte;rm:real);

procedure FormClose(Sender: TObject; var Action: TCloseAction);

procedure Button3Click(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

Form2: TForm2;

mgl_r:array[1..200,1..200]of string;

strm_r:array[1..200]of string;

pr:boolean;

xr,yr:byte;

implementation

uses Unit1, Unit3;

{$R *.dfm}

//решение k-й таблицы

procedure TForm2.resh;

var i,j:byte;

dstrm,maxstrm,minp:real;

begin

pr:=true;

maxstrm:=0;

for j:=3 to x do

begin

dstrm:=0;

for i:=1 to y do

begin

mgl_r[i,j]:=mgl[i,j].text;

dstrm:=dstrm+strtofloat(mgl[i,j].text)*strtofloat(mgl[i,2].text);

end;

if(j>3)then

begin

dstrm:=dstrm-strtofloat(mp[1,j-3].text);

if(maxmin*dstrm>maxstrm*maxmin)then begin maxstrm:=dstrm;x1:=j;end;

end;

strm[j-2].text:=floattostr(dstrm);

end;

if(maxmin*maxstrm>0)then pr:=false;

minp:=999999;

for i:=1 to y do

if((strtofloat(mgl[i,x1].Text)>0)and(strtofloat(mgl[i,3].Text)/strtofloat(mgl[i,x1].Text)<minp))then

begin

minp:=strtofloat(mgl[i,3].Text)/strtofloat(mgl[i,x1].Text);

y1:=i;end;

rm:=strtofloat(mgl[y1,x1].text);

mgl[y1,x1].Color:=clskyblue;

mgl[y1,1].text:=mp[2,x1-3].Text;

mgl[y1,2].text:=mp[1,x1-3].Text;

end;

//формирование новой таблицы

procedure TForm2.newtab;

var i,j:byte;

begin

for i:=1 to y do

for j:=1 to x do

begin

if (j in [1,2])and(i<>y1)then mgl_r[i,j]:=mgl[i,j].Text;

if j in [1,2] then continue;

if i=y1 then mgl[i,j].Text:=floattostr(strtofloat(mgl_r[i,j])/rm)

else mgl[i,j].Text:=floattostr((strtofloat(mgl_r[i,j])*rm-strtofloat(mgl_r[y1,j])*strtofloat(mgl_r[i,x1]))/rm);

mgl[i,j].Text:=floattostr(round(strtofloat(mgl[i,j].Text)*e)/e);

end;

end;

//процедура решения по кнопке "Вычислить"

procedure TForm2.Button1Click(Sender: TObject);

var k:byte;

rm:real;

begin

k:=1;

repeat

resh(xr,yr,rm,pr);

if not pr then showmessage(inttostr(k)+'-я таблица-результат');

mgl[yr,xr].Color:=clactiveborder;

if pr then begin showmessage('Результат:');

button1.Enabled:=false;

button3.Visible:=true;exit;end;

newtab(xr,yr,rm);

inc(k);

until pr;

end;

//по закрытию формы - выход из программы

procedure TForm2.FormClose(Sender: TObject; var Action: TCloseAction);

begin

form1.Close;

form3.Close;

end;

Размещено на Allbest.ru