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

Федеральное агентство по образованиюРФ

Федеральноегосударственное образовательное учреждение

Среднегопрофессионального образования

Барнаульскийстроительный колледж


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

Подисциплине: «Математические методы»

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


Выполнил: Нунгесер М.В.

Специальность: ПОВТ

Группа: 0881

Преподаватель: КлепиковаН.Н.

Барнаул 2010


 

Содержание:

Введение

Линейноепрограммирование

Симплекс метод

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

Разработка алгоритма

Решение задачи

Программная реализация на языке Delphi

Приложение

Заключение

Список используемой литературы


Введение

В последние годы вприкладной математике большое внимание уделяется новому классу задачоптимизации, заключающихся в нахождении в заданной области точек наибольшегоили наименьшего значения некоторой функции, зависящей от большого числапеременных. Это так называемые задачи математического программирования, возникающиев самых разнообразных областях человеческой деятельности и прежде всего вэкономических исследованиях, в практике планирования и организациипроизводства. Изучение этого круга задач и методов их решения привело ксозданию новой научной дисциплины, получившей позднее название линейногопрограммирования. В конце 40-х годов американским математиком Дж. Данцигом былразработан эффективный метод решения данного класса задач – симплекс-метод. Кзадачам, решаемых этим методом в рамках математического программированияотносятся такие типичные экономические задачи как «Определение наилучшегосостава смеси», «Задача об оптимальном плане выпуска продукции», «Оптимизациямежотраслевых потоков», « Задача о выборе производственной программы»,«Транспортная задача», «Задача размещения», «Модель Неймана расширяющейсяэкономики» и другие. Решение таких задач дает большие выгоды как народномухозяйству в целом, так и отдельным его отраслям.

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


Линейное программирование

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

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

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

 

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

Нужно определить максимумлинейной целевой функции (линейной формы)

/>

при условиях

/>/>

Иногда на xiтакже накладывается некоторый набор ограничений в виде равенств, но от нихможно избавиться, последовательно выражая одну переменную через другие иподставляя её во всех остальных равенствах и неравенствах (а также в функции f).

Такуюзадачу называют «основной» или «стандартной» в линейном программировании.Наиболее известным и широко применяемым на практике для решения общей задачилинейного программирования (ЛП) является симплекс метод.Симплекс метод

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

Применениесимплекс-метода для задачи линейного программирования предполагаетпредварительное приведение ее формальной постановки к канонической форме с nнеотрицательными переменными: (X1, ..., Xn),где требуется минимизация линейной целевой функции при m линейныхограничениях типа равенств. Среди переменных задачи выбирается начальный базисиз m переменных, для определенности (X1, ..., Xm),которые должны иметь неотрицательные значения, когда остальные (n-m) свободныепеременные равны 0. Целевая функция и ограничения равенства преобразуются кдиагональной форме относительно базисных переменных, переменных, где каждая базиснаяпеременная входит только в одно уравнение с коэффициентом 1.

Данная формальная модельзадачи линейного программирования обычно задается в форме, так называемой />симплекс-таблицы, удобной для выполнения операцийсимплекс-метода:


Симплекс-таблица

1

X1

X2

...

Xm

Xm+1

...

Xn

X0

A0,0

...

A0,m+1

...

A0,n

X1

A1,0

1 ...

A1,m+1

...

A1,n

X2

A2,0

1 ...

A2,m+1

...

A2,n

... ... ... ... ... ... ... ... ...

Xm

Am,0

... 1

Am,m+1

...

Am,n

Верхняя строкасимплекс-таблицы представляет целевую функцию задачи. Каждая строкасимплекс-таблицы, кроме первой, соответствует определенномуограничению-равенству задачи. Свободные члены ограничений составляют крайнийлевый столбец таблицы. Слева от таблицы записаны текущие базисные переменные (X1, ..., Xm).Сверху от таблицы приведен набор всех переменных задачи, где Xm+1, ..., Xn — свободные переменные задачи.

На начальномшаге алгоритма симплекс-метода должно быть выбрано базисное допустимое решение (X1, ..., Xm) >= 0при Xj = 0 (j = m+1, ..., n),следовательно, все свободные члены ограничений Ai,0 >= 0(i = 1, ..., m). Когда это условие выполнено,симплекс-таблица называется прямо-допустимой, так как в этом случае базисныепеременные, равные Ai,0, определяют допустимое решение прямойзадачи линейного программирования. Если все коэффициенты целевой функции A0,j >= 0(j = 1, ..., m), то симплекс-таблица называется двойственно-допустимой,поскольку соответствующее решение является допустимым для двойственной задачилинейного программирования.

Еслисимплекс-таблица является одновременно прямо и двойственно допустимой, т.е.одновременно все Ai,0 >= 0 и A0,j >= 0,то решение оптимально.

Действительно, посколькудопустимыми являются лишь неотрицательные значения управляемых параметров, тоизменение целевой функции за счет вариации свободных переменных, через которыеона выражена, возможно только в сторону увеличения, т.e. будет ухудшаться. Еслисреди ее коэффициентов имеются A0,j < 0, тозначение целевой функции еще можно уменьшить (т.e. улучшить), увеличиваязначение любой свободной переменной Xj с отрицательнымкоэффициентом A0,j при побочном уменьшении базисныхпеременных, чтобы оставались справедливы ограничения задачи. Теоретически можноиспользовать любую свободную переменную Xj с A0,j < 0,но на практике обычно действуют в соответствии со стратегией наискорейшегоспуска, выбирая минимальный элемент A0,p < 0 извсех отрицательных A0,j < 0:

A0,p = min A0,j < 0.

j

Столбец pсимплекс-таблицы, соответствующий выбранному коэффициенту A0,p < 0,называется ведущим столбцом. Свободная переменная ведущего столбцадолжна быть введена в базис вместо одной из текущих базисных переменных.Очевидно, из базиса следует исключить такую переменную Xq,которая раньше других обращается в нуль при увеличении переменной Xpведущего столбца.

Её индекслегко определить, если среди положительных элементов ведущего столбца pнайти элемент, минимизирующий отношение (Ai,0 / Ai,p):

 

Aq,0               Ai,0

— = min —, i = 1,...,m.

Aq,p  i            Ai,p

Элемент Aq,p называется ведущим элементом,cтрока q симплекс-таблицы, содержащая ведущий элемент, называется,соответственно, ведущей строкой. Переменная ведущей строки Xqзаменяется в базисе переменной ведущего столбца Xp истановится свободной переменной с значением 0, в то время как новая базиснаяпеременная Xp достигнет максимально возможного значения,равного: max Xp = ( Aq,0 / Aq,p).

После указанноговзаимообразного обмена переменными Xp и Xqмежду наборами свободных и базисных переменных нужно модифицировать исходную каноническуюмодель задачи путем приведения ее к диагональной форме относительно новогомножества базисных переменных. Для указанного преобразования можно формальноиспользовать процедуру исключения Гаусса, которая, как известно, состоитиз двух элементарных операций, применяемых к системе алгебраических уравнений (в данном случае ограничений — равенств):

·          умножениеуравнения E1(X) = 0 на константу K1и замена уравнения E1(X) = 0 уравнением K1*E1(X) = 0;

·          сложениеуравнений E1(X) = 0 и E2(X) = 0c последующей заменой уравнения E2(X) = 0уравнением E1(X) + E2(X) = 0.

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

Ai,p = 0, еслиi не равно q

и

Ai,p = 1, еслиi = q.

Указанные шагисимплекс-метода повторяются, пока не будет получена симплекс-таблица, котораяодновременно является прямо и двойственно допустимой. Если положит в такой симплекс-таблицетекущие базисные переменные равными Ai,0, а свободные — нулю,то будет получено оптимальное решение.

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

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

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

 

Количество единиц корма, которое ежедневно должны получать

 

Вид корма

Норка

Выдра

Нутрия

Общее количество корма

I

4

2

5

190

II

5

3

4

320

III

7

9

5

454

Прибыль от реализации одной шкурки, руб.

150

320

350

 


 

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

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

1)        Поставленнаяописательная задача переводится в математическую форму (целевая функция иограничения).

2)        Полученноематематическое описание приводят к канонической форме.

3)        Каноническуюформу приводят к матричному виду.

4)        Ищут первоедопустимое решение. Для этого матрица должна быть правильной. Матрица в ЗЛПназывается правильной, если она содержит минимум m правильных (базисных)столбцов, где m – число строк в матрице. Столбец в канонической ЗЛП называетсяправильным (базисным), если все его элементы равны нулю, кроме единственногоравного единице.

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

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

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

Ответ записываетсяследующим образом:

— Каждому отрицательномукоэффициенту в векторе решения ставится в соответствие нулевой коэффициент длясоответствующей переменной в ответе.

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

— Фиктивные переменные вответе не учитываются.

Ведущим может бытьназначен любой столбец, удовлетворяющий одному из условий:

1)      Первый столбец,содержащий положительный элемент в векторе решений.

2)      Столбец, содержащийнаибольший положительный элемент в строке решения.

3)      Если столбецудовлетворяет условию max(Cj min bj/aij)при решении на max, и min(Cj min bj/aij)при решении задач на min.

Cj – коэффициент целевой функции встолбце j, aij – коэффициент в столбце j и строке i.

Решение задачи

Определиммаксимальное значение целевой функции F(X)= 3500 x1 +3200x2  +1500x3 приследующих условиях ограничений.

 

4x1 +2 x2 +5 x3 <=190

5x1 +3 x2 +4 x3 <=320

7x1 +9 x2 +5 x3 <=454

 

Дляпостроения первого опорного плана систему неравенств приведем к системе  уравненийпутем введения дополнительных переменных.

 

4x1+ 2x2+ 5x3+ 1x4+ 0x5+ 0x6= 190

5x1+ 3x2+ 4x3+ 0x4+ 1x5+ 0x6= 320

7x1+ 9x2+ 5x3+ 0x4+ 0x5+ 1x6= 454

 

Матрицакоэффициентов A = a(ij)этой системы уравнений имеет вид:

<p/>

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

Решимсистему уравнений относительно базисных переменных:

x4,x5,x6

Полагая,что свободные переменные равны 0, получим первый опорный план: X1= (0,0,0,190,320,454)

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

Переходимк основному алгоритму симплекс-метода.


X1

X2

X3

X4

X5

X6

св. чл.

4

2 5 1 190 5 3 4 1 320 7 9 5 1 454 -3500 -3200 -1500

Итерация №0

Текущийопорный план неоптимален, так как в индексной строке находятся отрицательныекоэффициенты

Вкачестве ведущего выберем столбец, соответствующий переменной x1, так как наибольший коэффициент по модулю.

Вычислимзначения D i по строкам как частное от деления

и изних выберем наименьшее:

Следовательно,1-ая строка является ведущей

Разрешающийэлемент равен 4 и находится на пересечении ведущего столбца и ведущей строки

Формируемследующую часть симплексной таблицы.

Вместопеременной x в план 1 войдет переменная x1

Строка,соответствующая переменной x1в плане 1,получена в результате деления всех элементов строки x4 плана 0 на разрешающий элемент РЭ=4

Наместе разрешающего элемента в плане 1 получаем 1.

Востальных клетках столбца x1плана 1 записываемнули.

Такимобразом, в новом плане 1 заполнены строка x1 и столбец x1.

Всеостальные элементы нового плана 1, включая элементы индексной строки,определяются по правилу прямоугольника.

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

НЭ =СЭ — (А*В)/РЭ

СТЭ — элемент старого плана, РЭ — разрешающий элемент (4), А и В — элементы старогоплана, образующие прямоугольник с элементами СТЭ и РЭ.

Представим расчет каждогоэлемента в виде таблицы:

X1

X2

X3

X4

X5

X6

св. чл. 1 1/2 5/4 1/4 190/4 5 3 4 1 320 7 9 5 1 454 3500 3200 1500

X1

X2

X3

X4

X5

X6

св. чл. 1 1/2 5/4 1/4 190/4 1/2 -9/4 -5/4 1 165/2

11/2

-15/4 -7/4 1 243/2 -1450 2875 875

Итерация №1

Текущийопорный план неоптимален, так как в индексной строке находятся отрицательныекоэффициенты

Вкачестве ведущего выберем столбец, соответствующий переменной x2, так как наибольший коэффициент по модулю.

Вычислимзначения D i по строкам как частное от деления и из них выберем наименьшее:

Следовательно,3-ая строка является ведущей

Разрешающийэлемент равен 5.5 и находится на пересечении ведущего столбца и ведущей строки

Формируемследующую часть симплексной таблицы.

Вместопеременной x в план 2 войдет переменная x2

Строка,соответствующая переменной x2в плане 2,получена в результате деления всех элементов строки x6 плана 1 на разрешающий элемент РЭ=5.5

Наместе разрешающего элемента в плане 2 получаем 1.

Востальных клетках столбца x2плана 2 записываемнули.

Такимобразом, в новом плане 2 заполнены строка x2 и столбец x2.

Всеостальные элементы нового плана 2, включая элементы индексной строки,определяются по правилу прямоугольника.

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

НЭ =СЭ — (А*В)/РЭ

СТЭ — элемент старого плана, РЭ — разрешающий элемент (5.5), А и В — элементы старогоплана, образующие прямоугольник с элементами СТЭ и РЭ.

Представимрасчет каждого элемента в виде таблицы:

Конецитераций: найден оптимальный план


Окончательныйвариант симплекс-таблицы:

X1

X2

X3

X4

X5

X6

св. чл. 1 159/100 41/100 -9/100 729/20 -191/100 -109/100 1 -9/100 1429/20 1 -15/22 -7/22 9/50 243/11 1886.36 413.64 263.64

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

x1 = 729/20=36.45

x5 =1429/20= 71.45

x2 =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;

procedureExitClick(Sender: TObject);

procedureButton_NextClick(Sender: TObject);

procedureButton_PrevClick(Sender: TObject);

procedureFormCreate(Sender: TObject);

private

{ Privatedeclarations }

public

{ Publicdeclarations }

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 3do {подписываем что 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<=mthen

  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)+']';

   ifj<>m+1 then podpis[i,j].Caption:=podpis[i,j].Caption+' +';

   {если поле не последнее, тодописываем плюсик}

  end;

  end;

 for i:=1 to ndo {поля для ввода ограничений}

  for j:=1 tom+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';

  ifj<=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)+']';

  ifj<>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 elsepole[i,j].Left:=pole[i,j].Left+70; //поля для правой части

             //ограничений

end;

 end else {если табличку создавать не надо, то разблокируемполя}

   begin

   for i:=1 ton+1 do

  for j:=1 to m+1 do

begin

    pole[i,j].Enabled:=true;

    if i<=nthen znak[i].Enabled:=true;

    end;

   end;

 end;

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

procedurewrite_system(strok,stolb: integer);

{записывает массив в видеуравнений}

 var

 i,j: integer;

 begin

 write(f,'<P>F(x)= ');

 for j:=1 tostolb do

 begin

 write(f,matrix[strok,j]:0:3);

 if j<stolbthen

  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 tostolb do

BEGIN

write(f,matrix[i,j]:0:3);

  ifj<stolb then write(f,'x<sub>',j,'</sub> ');

  if j=stolb-1then

   ifkanon=false then write(f,' ',znak[i].text,' ')

   elsewrite(f,' = ');

  if(matrix[i,j+1]>=0) and (j<stolb-1) then write(f,'+');

  end;

 writeln(f,'<br>');

 end;

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

 end;

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

procedurezapisat(strok,stolb: integer; v_strok,v_stolb:integer);

{записывает массив в видетаблички}

 var

 i,j:integer;

 begin

 writeln(f,'<TABLEBORDER BORDERCOLOR=black CELLSPACING=0 CELLPADDING=5>');

 for i:=0 tostrok do

 begin

 writeln(f,'<TR>');

 for j:=1 tostolb+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

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

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

procedurefindved;

{ищет ведущийэлемент}

 var

 i,j,k:integer;

 temp: double;

begin

 done:=false;

 solve:=false;

 is_ok:=true;

 temp:=100000;

 i0:=0;

 j0:=0;

 i:=n+1;

 forj:=1 to m+y do

if (i0=0) or(j0=0) then

  ifmatrix[i,j]>0 then

  begin

  j0:=j;

  for k:=1 ton 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 mdo

  ifmatrix[n+1,j]=0 then

  for i:=1 ton do

   if(matrix[i,j]<>0) and (matrix[i,j]<>1) then

   begin

   is_ok:=false;

   j0:=j;

   end;

 if is_ok=falsethen

 begin

 temp:=100000;

 for k:=1 to ndo

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

  ifiter<>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 ton+1 do

 for j:=1 tom+y+1 do

  ifabs(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=falsethen

 begin

 write(f,'<P>Пересчет:</P>');

 temp:=matrix[i0,j0];

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

 for i:=1 ton+1 do

  begin

  temp:=matrix[i,j0];

  for j:=1 tom+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 thent:=j;

   {если наши предположения (*)подтвердились, то запомним этот элемент}

  end;

 

if t<>0then

   begin

   for k:=1 ton+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 thenall_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;

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

procedureotvet;

{выводитответ}

 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(';

 ifform1.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('');

 form1.Memo1.Lines.Add('при значениях:');

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

 for j:=1 to mdo

 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 ndo

ifall_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 ton+1 do

  for j:=1 tom+1 do

   begin

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

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

   if i<=nthen 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>Необходимо');

ifform1.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

 ifznak[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

 elseneed_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]<0then {если правая часть отрицательна,}

 {то отнимаем всю строкуот нуля}

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

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

{выведем ее в отчет}

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

{если ф-ция на минимум,то нужно поменять знаки в последней строке}

ifform1.Extrem.ItemIndex=1 then

 for j:=1 tom+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 tom+y do

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

  if(is_basis=false) then

 begin

all_basis[i]:=j;

  is_basis:=true;

  for k:=1 ton do

   ifk<>i then

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

    if(is_basis=true) then

    begin

    is_basis:=false;

    all_basis[i]:=0;

    end;

  end;

 ifis_basis=false then

  begin

  i_basis:=i_basis+1;

  y:=y+1;

  for k:=1 ton+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,'<H2>Необходимо ввести искусственныйбазис</H2>');

 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=0then

 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=0then

 begin

 iter:=0;

 findved;

 if done=falsethen

 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;

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

{///////// все, что ниже, относится кпереходам между шагами ////////////////}

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

procedureTForm1.ExitClick(Sender: TObject);

 begin

 Close();

 end;

procedureTForm1.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;

elsestep:=step-1;

 end;

 form1.Caption:='Симплексметод — шаг '+inttostr(step);

end;

procedureTForm1.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;

 elsestep:=step+1;

 end;

 form1.Caption:='Симплексметод — шаг '+inttostr(step);

 end;

procedureTForm1.FormCreate(Sender: TObject);

begin

Init;

end;

Заключение

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

Такимобразом, вычислительная техника в настоящее время находит широкое применение,как в общей математике, так и в одном из её разделов – математических методах.


Список используемой литературы

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

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

3. А.Н. Карасев, Н.Ш. Кремер, Т.Н.Савельева «Математические методы в экономике», М.2000

4. Орлов А.И. Теория принятиярешений. Учебное пособие. — М.: Издательство «Март», 2004

5. Интернет

еще рефераты
Еще работы по информатике, программированию