Сформулировать математическую постановку и построить концептуальную модель решения задачи линейного программирования Симплекс-методов

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

Линейное программирование представляет собой наиболее часто используемый метод оптимизации. К числу задач линейного программирования можно отнести задачи:

· рационального использования сырья и материалов; задачи оптимального раскроя;

· оптимизации производственной программы предприятий;

· оптимального размещения и концентрации производства;

· составления оптимального плана перевозок, работы транспорта;

· управления производственными запасами;

· и многие другие, принадлежащие сфере оптимального планирования.

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

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

Математическое программирование - это прикладная отрасль математики, которая является теоретической основой решения задач оптимального планирования.

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

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

1. Постановка задачи моделирования

Математическое описание метода

Допустим, имеется система уравнений ограничений:

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

Избавляемся от отрицательных коэффициентов для этого принимаем

Данная форма записи уравнений называется стандартной.

При пересечении разрешающей строки у₃ и разрешающего столбца х₂ получаем разрешающий элемент а_32.

Необходимо найти коэффициенты, которые получатся в разрешающей строке после обмена х₂ - у_3.

Алгоритм преобразования коэффициентов стандартной таблицы

1. Разрешающий элемент заменяется на обратную ему величину.

2. Все остальные элементы разрешающей строки делятся на разрешающий элемент.

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

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

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

Алгоритм преобразования x_j - y_i стандартной таблицы сводится к следующим операциям:

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

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

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

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

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

6. Переписать таблицу, заменив:

· x_j на y_i;

· элемент разрешающей строки и столбца, числами, стоящими в нижней части тех же ячеек;

· каждый из остальных элементов суммой чисел стоящей в верхней и нижней части той же ячейки.

В любой задаче ОЗЛП существует так же линейная функция L, которая в общем случае выглядит следующим образом:

Для решения ее табличным способом ее так же можно привести к стандартному виду.

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

Нахождение решения каждой задачи распадается на два этапа:

1. нахождение опорного плана;

2. отыскание оптимального решения.

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

В процессе второго этапа выясняется, ограничена ли снизу функция L, которая стремиться к минимуму, если нет, то оптимального решения не существует. Если да, то оно отыскивается после замены x на y.

Двойственные задачи ОЗЛП

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

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

Ищем в данной строке (y₂) отрицательный элемент a_ij, если такого элемента нет, то данная система уравнений не совместна. При отсутствии отрицательных элементов в строке вся правая часть соответствующего уравнения может быть только отрицательной, а это противоречит условиям не отрицательных переменных.

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

2. Инструментальные программные средства

Среди пользователей персональных компьютеров в настоящее время наиболее популярно семейство операционных систем Windows и, естественно программы нужно создавать, используя возможности операционной системы. В связи с этим, выбранным средством создания модели является среда разработки - Delphi.

Среди современных языков программирования язык Delphi является одним из наиболее распространенных. Язык Delphi хорошо зарекомендовал себя эффективностью, лаконичностью записи алгоритмов, логической стройностью программ.

Delphi - это среда быстрой разработки программ, в которой в качестве языка программирования используется Object Pascal. В основе идеологии Delphi лежит технология визуального проектирования и методологии объектно-ориентированного событийного программирования.

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

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

3. Блок - схема алгоритма

4. Операционная среда моделирования

Операционная система Windows 95/98 - это разработанная фирмой Microsoft операционная система, обеспечивающая большое количество возможностей и удобств для пользователей и программистов. Широчайшее распространение Windows сделало ее фактическим стандартом для IBM PC- совместимых компьютеров, подавляющее большинство пользователей таких компьютеров работают в Windows, поэтому в наше время практически все новые программы стали разрабатываться именно для их эксплуатации в среде Windows. А более современные операционные системы Windows 2000, OS/2 Warp поддерживают выполнение программ, рассчитанных на Windows 98.

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

Выпуск систем Windows 95/98 достиг миллионных тиражей, а число пользователей Windows во всем мире вообще невозможно сосчитать. Достоинства этих операционных систем следующие.

Аппаратная и программная совместимость. Существует великое множество совре-менных устройств класса Plug and Play Plug and Play (включил и работай) - это устройства, идентификация и установка которых производится операционной системой автоматически, при минимальном участии поль-зователя., а также менее совершенных устройств, выпущенных ранее. Системы Windows 95/98 устроены таким образом, что они совершенно не зависят от аппаратуры, и в то же время они берут на себя функции ее установки и конфигурирования.

Аналогично аппаратной совместимости с устаревшим оборудованием системы Windows 95/98 совместимы с огромным количеством прикладных программ, разра-ботанных ранее для MS-DOS MS-DOS (Microsoft Disk Operating System) - очень популярная дисковая операционная система фирмы Microsoft, выпущенная в 1981 году и обслуживавшая еще первые модели IBM PC. и для предыдущих версий Windows.

Многозадачность. В старых версиях Windows 3-х был реализован не лучший вариант многозадачности, когда из нескольких запущенных приложений Приложением (Windows-приложением) называется прикладная программа, работающая под управлением операционной системы (Windows). одно могло самовольно брать в свои руки управление системой, что исключало параллельную работу приложений в реальном времени. В Windows 95/98 применяется иной тип многозадачности, так называемая многозадачность с вытеснением. Согласно этой модели, каждому запущенному процессу присваивается уровень приоритета, и в первую очередь выполняется процесс с более высоким приоритетом.

Многопоточность. Для реального одновременного выполнения процессов в Windows 95/98 применен механизм, называемый многопоточностью. Потоки - это как бы фрагменты исполняемого программного кода, которые могут работать одно-временно.

Обмен информацией между приложениями. При работе в многозадачной среде особенно важен обмен информацией между приложениями. В среде MS-DOS подобная задача доступна только квалифицированному программисту, в то время как в Windows 95/98 пользователь свободно может передавать информацию из одного приложения в другое. При этом в большинстве случаев можно не заботиться о форматах данных.

Единый графический интерфейс Графический интерфейс - под этим термином здесь и далее понимается интерфейс поль-зователя, то есть программный модуль, который отвечает за взаимодействие с пользователем. В случае Windows 95/98 графический интерфейс - это попросту картинка на экране, содержащая различные элементы управления, с помощью которых пользователь получает целый набор сервисных услуг, освобождающих его от выполнения рутинных операций.. В Windows 95/98 унифицирован интерфейс всех Windows-приложениий и правила работы с ними. Благодаря этому пользователь, изучив работу одной программы, может без особых усилий осваивать все последующие. Windows 95/98 предлагает пользователям IBM PC самый удобный на сегодня интерфейс, который освобождает от выполнения многих рутинных операций и дает свободу для занятия непосредственными задачами.

5. Контрольная задача

Даны данные: из которых составляется система уравнений вида:

Целевая функция этой системы уравнений стремится в максимум, и имеет вид:

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

В данной системе 3 - уравнения с 3 - неизвестными, принимают за основные X₄, X_5, X₆ - переменных.

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

Вводим добавочные неотрицательные переменные (которые еще называют «неосновные»), и сводим систему неравенств к эквивалентной системе уравнений.

Так как в полученной системе уравнений нет отрицательных свободных членов, то базисное решение является допустимым (0; 0; 0; 60; 100; 36).

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

Х₂: {60/1; 100/1; 36/1} переводим Х₂ в основные переменные: из третьего уравнения, так как 36/1=36 наименьший коэффициент.

Подставим в целевую функцию =>Х₂:

Рассмотрим полученную систему уравнений и целевую функцию:

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

Переходим к новому базисному решению {0; 5; 0; 0; 20; 50}. Из не основных переменных, входящих в линейную форму (уравнения) с положительным коэффициентом выбираем ту, которой соответствует наибольший коэффициент и переводит ступени в основные.

Рассмотрим переменную Х₁ {10; 10; 17}. Выразим из первого уравнения переменную Х₁:

Рассмотрим полученную систему уравнений и целевую функцию:

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

Переходим к новому базисному решению {10; 0; 0; 0; 40; 20}. Из не основных переменных, входящих в линейную форму с положительным коэффициентом выбираем Х₃, которой соответствует наибольший коэффициент (5) и переводит ступени в основные.

Рассмотрим переменную Х₃ {0; 8; 20}. Выразим из второго уравнения переменную Х₃:

Рассмотрим полученную систему уравнений и целевую функцию:

Отыскивается максимум линейной формы, так как в ступени выражений нет основных переменных с положительным знаком - критерий оптимальности выполнен и полученное базисное решение служит оптимальным (задача решена).

То есть при Х₁=10; Х₂=0; X₃=8 максимальное значение функции равно 80 (Lmax=80).

Заключение

В курсовой работе проделана работа по изучению следующих вопросов:

· Рассмотрен и дан алгоритм симплекс метода.

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

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

Программа имеет ограничения: количество рассмотренных уравнений и вводимых элементов уравнения не должно превышать 10.

Программа не рассчитана на неправильный ввод формата вводимых данных.

Литература

1. Б.Я. Советов - «АСУ. Внедрение в специальность» (1989г.)

2. Е.С. Вентцель - «Исследование операций» (1972г.)

3. Конспекты по «АСУ»

4. Конспекты по «Компьютерному моделированию»

5. Г. Жимерин, В.А. Мясников - «Автоматизированные и автоматические системы уравнения» (1975г.)

6. Б.Я. Советов - «АСУ. Внедрение в специальность» (1989г.)

7. Е.С. Венцель - «Исследование операций» (1972г.)

Приложение 1

Листинг программы

unit simplex;

interface

uses

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

Dialogs, StdCtrls, Buttons, ActnMan, ActnColorMaps, Grids, Spin, Menus, shellAPI;

type

Tmainf = class(TForm)

urkol: TSpinEdit;

elkol: TSpinEdit;

celf: TStringGrid;

ogrf: TStringGrid;

XPColorMap1: TXPColorMap;

Label1: TLabel;

Label2: TLabel;

next: TBitBtn;

prev: TBitBtn;

PrOperBOX: TCheckBox;

minmax: TCheckBox;

MainMenu1: TMainMenu;

N1: TMenuItem;

N2: TMenuItem;

N4: TMenuItem;

N5: TMenuItem;

N6: TMenuItem;

N7: TMenuItem;

procedure nextClick(Sender: TObject);

procedure FormCreate(Sender: TObject);

procedure prevClick(Sender: TObject);

procedure N4Click(Sender: TObject);

procedure N6Click(Sender: TObject);

procedure N7Click(Sender: TObject);

procedure FormShow(Sender: TObject);

procedure N5Click(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

TYPE MAS=ARRAY[1..30] OF REAL;

MASB=ARRAY[1..30] OF STRING[3];

MASX=ARRAY[1..30,1..30] OF REAL;

var

mainf: Tmainf;

sostoyanie:Integer;

Fo,FunctPr,B,H,Hnew,C,Cnew,CPr,CPrnew,FX:MAS;

X,Xnew:MASX;

BS,Bvsp,ZNAC:MASB;

MIN,I1,I,J,Kit,NachKell,NachY,K_st:INTEGER;

PriznacY,KLstr,KLst,ErrCode,Dop_X:INTEGER;

P,P1,Mo,F0,Epsilon,Z:REAL;

VSP,S,PrGomory:STRING;

F:TEXT;

DPx,DPy,Fm,Kell,Kstr:INTEGER;

chislo:real;

errcode1,errcode2:integer;

implementation

uses Math,resunit,about,autors,wait,start;

{$R *.dfm}

//функция создания индексов

//-----------------------------------------------------------

FUNCTION SIMVB(V:INTEGER;S:CHAR):STRING;

VAR M,Z:STRING;

BEGIN

STR(V,M);

Z:=S+M;

SIMVB:=Z;

END;

//-----------------------------------------------------------

//Процедура записи в файл

//-----------------------------------------------------------

PROCEDURE SAVE(X1:REAL;K:STRING;Mstr:INTEGER);

VAR V:STRING;

BEGIN

AssignFile(F,'SIMPLEX.DAT');

APPEND(F);

CASE Mstr OF

0:WRITELN(F,'');

1:BEGIN

IF K=' ' THEN STR(X1:1:0,V) ELSE STR(X1:10:4,V);

WRITE(F,V);

WRITE(F,' ');

END;

2:WRITE(F,K);

3:WRITELN(F,K);

END;

CloseFile(F);

END;

//-----------------------------------------------------------

//Определение дополнительных переменных

//-----------------------------------------------------------

PROCEDURE DOP_PER;

BEGIN

IF ZNAC[I1]='=' THEN

BEGIN

Kell:=Kell+1;Bvsp[Kell]:=SIMVB(DPy,'Y');

DPy:=DPy+1;

Xnew[I1,Kell]:=1;

IF Fm=1 THEN FX[Kell]:=-1 ELSE FX[Kell]:=1;

FunctPr[Kell]:=1;

FOR I:=1 TO Kstr DO

IF I<>I1 THEN Xnew[I,Kell]:=0;

END;

IF ZNAC[I1]='>=' THEN

BEGIN

Kell:=Kell+1;Bvsp[Kell]:=SIMVB(DPx,'X');

DPx:=DPx+1;Dop_X:=Dop_X+1;

Xnew[I1,Kell]:=-1;FX[Kell]:=0;

FOR I:=1 TO Kstr DO

IF I<>I1 THEN Xnew[I,Kell]:=0;

Kell:=Kell+1;Bvsp[Kell]:=SIMVB(DPy,'Y');

DPy:=DPy+1;

Xnew[I1,Kell]:=1;

IF Fm=1 THEN FX[Kell]:=-1 ELSE FX[Kell]:=1;

FunctPr[Kell]:=1;

FOR I:=1 TO Kstr DO

IF I<>I1 THEN Xnew[I,Kell]:=0;

END;

IF ZNAC[I1]='<=' THEN

BEGIN

Kell:=Kell+1;Bvsp[Kell]:=SIMVB(DPx,'X');

DPx:=DPx+1;Dop_X:=Dop_X+1;

Xnew[I1,Kell]:=1;FX[Kell]:=0;

FOR I:=1 TO Kstr DO

IF I<>I1 THEN Xnew[I,Kell]:=0;

END;

END;

//-----------------------------------------------------------

//Процедура сокращения Y

//-----------------------------------------------------------

PROCEDURE SOKR;

VAR P:INTEGER;

BEGIN

Kell:=Kell-1;

FOR P:=NachKell+DOP_X TO Kell DO

IF Bvsp[P]=BS[KLstr] THEN BEGIN

FOR J:=P TO Kell DO

Bvsp[J]:=Bvsp[J+1];

FunctPr[J]:=FunctPr[J+1];

Fx[J]:=Fx[J+1];

FOR I:=1 TO Kstr DO

Xnew[I,J]:=Xnew[I,J+1]

END;

END;

//-----------------------------------------------------------

//Процедура, выполняющая метод Гомори

//-----------------------------------------------------------

PROCEDURE GOMORY;

VAR MAX,Z:REAL;

BEGIN

KLstr:=1;

MAX:=H[1]-INT(H[1]);

FOR I1:=2 TO Kstr DO

IF (H[I1]-INT(H[I1]))>=MAX THEN BEGIN MAX:=H[I1]; KLstr:=I1;END;

Kstr:=Kstr+1;

Hnew[Kstr]:=H[KLstr]-INT(H[KLstr]);

FOR I1:=1 TO Kell DO

BEGIN

Z:=INT(X[KLstr,I1]);

IF X[KLstr,I1]<0 THEN Z:=Z-1;

Xnew[Kstr,I1]:=X[KLstr,I1]-Z;

END;

ZNAC[Kstr]:='>=';

END;

//-----------------------------------------------------------

//Процедура, выполняющая симплекс метод

//-----------------------------------------------------------

PROCEDURE SIMPLEXM;

LABEL NACH;

BEGIN

Kit:=0;Dop_X:=0;

AssignFile(F,'SIMPLEX.DAT');

REWRITE(F);

CloseFile(F);

NachKell:=Kell;

DPx:=Kell+1;DPy:=1;

Epsilon:=0.00001;

{ Подготовка индексации X }

FOR J:=1 TO Kell DO

Bvsp[J]:=SIMVB(J,'X');

{ Определение дополнительных переменных }

FOR I1:=1 TO Kstr DO

DOP_PER;

{ Замена оптимальной функции с MAX на MIN при наличии

в базисе Y-ков если идет исследование на минимум }

MIN:=0;

IF (Fm=1) AND (PriznacY=1) THEN

BEGIN

MIN:=Fm;Fm:=2;

FOR J:=1 TO Kell DO

FX[J]:=-FX[J];

END;

{ Сортировка дополнительных переменных по индексу }

FOR I1:=NachKell+1 TO Kell DO

FOR J:=I1+1 TO Kell DO

IF Bvsp[J]<Bvsp[I1] THEN

BEGIN

VSP:=Bvsp[J];Bvsp[J]:=Bvsp[I1];Bvsp[I1]:=VSP;

P:=FX[J];FX[J]:=FX[I1];FX[I1]:=P;

P:=FunctPr[J];FunctPr[J]:=FunctPr[I1];FunctPr[I1]:=P;

FOR I:=1 TO Kstr DO

BEGIN

P:=Xnew[I,I1];Xnew[I,I1]:=Xnew[I,J];Xnew[I,J]:=P;

END;

END;

Kit:=1;

{ Подготовка столбцов C,B,H }

FOR I:=1 TO Kstr DO

BEGIN

Hnew[I]:=B[I];

FOR J:=NachKell+1 TO Kell DO

IF Xnew[I,J]=1 THEN

BEGIN

BS[I]:=Bvsp[J];

Cnew[I]:=FX[J];

CPrnew[I]:=FunctPr[J];

END;

END;

NACH:;

REPEAT

PriznacY:=0;

{ Передача данных в исходные переменные с обнулением чисел,

по модулю меньших чем 0.00001 }

FOR I:=1 TO Kstr DO

BEGIN

IF INT(10000*Hnew[I])=0 THEN H[I]:=+0 ELSE H[I]:=Hnew[I];

C[I]:=Cnew[I];

CPr[I]:=CPrnew[I];

IF BS[I][1]='Y' THEN PriznacY:=1;

FOR J:=1 TO Kell DO

IF INT(10000*Xnew[I,J])=0 THEN X[I,J]:=+0 ELSE X[I,J]:=Xnew[I,J];

END;

{ Обнуление и вывод индексации элементов индексной строки }

SAVE(0,' C B H ',2);

FOR J:=1 TO Kell DO

BEGIN

SAVE(0,Bvsp[J],2);

P1:=LENGTH(Bvsp[J]);

IF P1=2 THEN SAVE(0,' ',2);

SAVE(0,' ',2);

Fo[J]:=0;

END;

SAVE(0,'',0);

{ Вывод симплекс-таблицы }

P1:=0;

FOR I:=1 TO Kstr DO

BEGIN

IF CPr[I]=1 THEN

IF C[I]<0 THEN SAVE(0,'-M ',2)

ELSE SAVE(0,'+M ',2)

ELSE SAVE(C[I],'',1);

SAVE(0,BS[I],2);

P1:=LENGTH(BS[I]); IF P1=2 THEN SAVE(0,' ',2);

SAVE(0,' ',2);SAVE(H[I],'',1);

FOR J:=1 TO Kell DO

SAVE(X[I,J],'',1);

SAVE(0,'',0);

END;

{ Вычисление значений в индексной строке }

F0:=0;

FOR J:=1 TO Kell DO

Fo[J]:=0;

FOR I1:=1 TO Kstr DO

BEGIN

IF PriznacY=1 THEN

IF BS[I1][1]='Y' THEN

BEGIN

F0:=F0+H[I1];

FOR J:=1 TO Kell DO

Fo[J]:=Fo[J]+X[I1,J];

END;

IF PriznacY=0 THEN

BEGIN

F0:=F0+H[I1]*C[I1];

FOR J:=1 TO Kell DO

Fo[J]:=Fo[J]+C[I1]*X[I1,J];

END;

FOR J:=1 TO Kell DO

IF Bvsp[J][1]='Y' THEN Fo[J]:=+0

ELSE IF ABS(Fo[J])<Epsilon THEN Fo[J]:=+0;

END;

{ Вывод значений целевой фынкции }

SAVE(0,' ',2);SAVE(F0,'',1);

FOR J:=1 TO Kell DO

BEGIN

IF PriznacY<>1 THEN Fo[J]:=Fo[J]-FX[J];

SAVE(Fo[J],'',1);

END;

SAVE(0,'',0);

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

P:=0;

FOR J:=1 TO Kell DO

IF Fm=1 THEN IF Fo[J]<-Epsilon THEN

BEGIN

P:=1;

CONTINUE;

END ELSE

ELSE IF Fo[J]>Epsilon THEN

BEGIN

P:=1;

CONTINUE;

END;

IF P<>1 THEN

BEGIN

SAVE(0,'На ',2);SAVE(Kit,' ',1);

SAVE(0,'-й итерации было получено оптимальное решение',3);

SAVE(0,'т.к. при исследовани на ',2);

IF Fm=1 THEN

SAVE(0,'Максимум индексная строка не содержит отрицательных элементов.',3)

ELSE

SAVE(0,'Минимум индексная строка не содержит положительных элементов.',3);

FOR I1:=1 TO Kstr DO

IF BS[I1][1]='Y' THEN

BEGIN

SAVE(0,'Но т.к из базиса не выведены все Y, то ',3);

SAVE(0,'можно сделать вывод, что РЕШЕНИЙ НЕТ ',3);

Exit;

END;

{ Округление значений массива X до целого числа,

если разность округлённого и обычного знчений

по модулю меньше чем 0.00001 }

FOR I:=1 TO Kstr DO

BEGIN

Z:=ROUND(H[I]);

IF ABS(Z-H[I])<Epsilon THEN H[I]:=ROUND(H[I]);

FOR J:=1 TO Kell DO

BEGIN

IF X[I,J]<0 THEN Z:=ROUND(X[I,J]);

IF ABS(Z-X[I,J])<Epsilon THEN X[I,J]:=ROUND(X[I,J]);

END;

END;

{ Проверка целочисленности решения }

P1:=0;

FOR I:=1 TO Kstr DO

BEGIN

IF INT(10000*FRAC(H[I]))<>0 THEN BEGIN P1:=1;CONTINUE; END;

FOR J:=1 TO Kell DO

IF BS[I]=Bvsp[J] THEN

FOR I1:=1 TO Kstr DO

IF ABS(FRAC(X[I1,J]))>=Epsilon THEN BEGIN P1:=1;CONTINUE; END;

END;

{ Составление новой базисной строки для целочисленного решения }

IF (PrGomory='Y') AND (P1=1) THEN

BEGIN

GOMORY;

NachKell:=Kell;

I1:=Kstr;DPy:=1;

DOP_PER;

BS[Kstr]:=Bvsp[Kell];

CPrnew[Kstr]:=FunctPr[Kell];

Cnew[Kstr]:=FX[Kell];

GOTO NACH;

END;

IF P1=0 THEN SAVE(0,'Данное решение целочисленное.',3);

SAVE(0,'При этом:',3);

IF MIN=1 THEN BEGIN F0:=-F0;Fm:=MIN; END;

IF Fm=1 THEN

SAVE(0,'Fmax=',2)

ELSE

SAVE(0,'Fmin=',2);

SAVE(F0,'',1);

SAVE(0,'',0);

FOR I1:=1 TO Kstr DO

BEGIN

SAVE(0,' ',2);

SAVE(0,BS[I1],2);SAVE(0,'=',2);

SAVE(H[I1],'',1);

SAVE(0,'',0);

END;

Exit;

END;

{ Нахождение ключевого столбца  }

KLst:=1;Mo:=0;

FOR J:=1 TO Kell DO

IF Fm=1 THEN

IF Fo[J]<Mo THEN Mo:=Fo[J];

FOR J:=1 TO Kell DO

BEGIN

IF Bvsp[J][1]<>'Y' THEN

IF Fm=1 THEN

BEGIN

IF Fo[J]<0 THEN

IF Fo[J]>=Mo THEN

BEGIN

Mo:=Fo[J]; KLst:=J;

END;

END

ELSE

BEGIN

IF Fo[J]>0 THEN

IF Fo[J]>=Mo THEN

BEGIN

Mo:=Fo[J]; KLst:=J;

END;

END;

END;

SAVE(0,'Ключевой столбец: ',2);SAVE(KLst,' ',1);

{ Нахождение ключевой строки }

P1:=0;K_st:=0;

FOR J:=1 TO Kell DO

IF ABS(Mo-Fo[J])<Epsilon THEN

BEGIN

K_st:=K_st+1;

FOR I:=1 TO Kstr DO

IF X[I,KLst]>0 THEN BEGIN B[I]:=H[I]/X[I,KLst]; P:=B[I];KLstr:=I; END

ELSE BEGIN B[I]:=-1; P1:=P1+1; END;

END;

IF P1=Kstr*K_st THEN

BEGIN

SAVE(0,'',0);

SAVE(0,'РЕШЕНИЙ НЕТ т.к. невозможно определить ключевую строку',3);

Exit;

END;

P1:=0;

FOR J:=1 TO Kell DO

IF ABS(Mo-Fo[J])<Epsilon THEN

FOR I:=1 TO Kstr DO

IF B[I]>=0 THEN BEGIN

IF B[I]<P THEN IF Bvsp[KLst]<>BS[I] THEN BEGIN P:=B[I]; KLstr:=I; END;

IF INT(10000*B[I])=INT(10000*P) THEN

IF (BS[I][1]='Y') AND (BS[KLstr][1]='X') THEN

IF Bvsp[KLst]<>BS[I] THEN BEGIN P:=B[I]; KLstr:=I; END;

END;

SAVE(0,'Ключевая строка : ',2);SAVE(KLstr,' ',1);

SAVE(0,'',0);

FOR I:=1 TO Kstr DO

IF Bvsp[KLst]=BS[I] THEN

BEGIN

SAVE(0,'РЕШЕНИЙ НЕТ т.к. в базисном столбце уже есть ',3);

SAVE(0,'такая переменная.',3);

Exit;

END;

{ Вызов процедуры сокращения Y }

IF CPr[KLstr]=1 THEN SOKR;

{ Построение следующей симплекс-таблицы }

BS[KLstr]:=Bvsp[KLst];

Cnew[KLstr]:=FX[KLst];

CPrnew[KLstr]:=FunctPr[KLst];

FOR I:=1 TO Kstr DO

BEGIN

IF I=KLstr THEN Hnew[I]:=H[I]/X[KLstr,KLst]

ELSE Hnew[I]:=H[I]-(H[KLstr]*X[I,KLst]/X[KLstr,KLst]);

FOR J:=1 TO Kell DO

BEGIN

IF (I=KLstr) AND (J=KLst) THEN Xnew[I,J]:=1;

IF (I=KLstr) AND (J<>KLst) THEN Xnew[I,J]:=X[I,J]/X[KLstr,KLst];

IF (I<>KLstr) AND (J=KLst) THEN Xnew[I,J]:=0;

IF (I<>KLstr) AND (J<>KLst) THEN

Xnew[I,J]:=X[I,J]-(X[KLstr,J]*X[I,KLst]/X[KLstr,KLst]);

END;

END;

KLst:=0;KLstr:=0;

Kit:=Kit+1;

UNTIL (Kit=0);

END;

//-----------------------------------------------------------

procedure Tmainf.nextClick(Sender: TObject);

begin

//---- состояние программы ----

case sostoyanie of

1:begin

if (elkol.Value>10) or (elkol.Value<1) or ( urkol.Value>10) or (urkol.Value<1)

then begin

ShowMessage('Ошибка ввода');

Exit;

end;

celf.ColCount:=elkol.Value+1;

ogrf.RowCount:=urkol.Value+1;

ogrf.ColCount:=elkol.Value+3;

for i:= 1 to elkol.Value do

begin

celf.Cells[i,0]:='X'+IntToStr(i);

ogrf.Cells[i,0]:='X'+IntToStr(i);

end;

celf.Cells[0,1]:='Целевая функция';

for i:=1 to urkol.Value do

ogrf.Cells[0,i]:='Уравнение '+IntToStr(i);

ogrf.Cells[elkol.Value+1,0]:=' знак';

ogrf.Cells[elkol.Value+2,0]:='свободный член';

celf.Visible:=True;

ogrf.Visible:=True;

elkol.Enabled:=False;

urkol.Enabled:=False;

sostoyanie:=sostoyanie+1;

PrOperBOX.Visible:=True;

minmax.Visible:=True;

end;

2:begin

PrOperBOX.Enabled:=True;

minmax.Enabled:=True;

Kstr:=urkol.Value;

Kell:=elkol.Value;

NachKell:=Kell;

DPx:=Kell+1;

DPy:=1;

if minmax.Checked then Fm:=1 else Fm:=2;

If PrOperBOX.Checked then PrGomory:='Y' else PrGomory:='N';

for i:=1 to Kstr do

begin

for j:=1 to Kell do

begin

val(ogrf.Cells[j,i],chislo,ErrCode1);

val(ogrf.Cells[elkol.value+2,i],chislo,ErrCode2);

if (ogrf.Cells[j,i]='') or (ogrf.Cells[elkol.Value+2,i]='')

or (ErrCode1<>0) or (errCode2<>0) then

begin

ShowMessage('Ошибка ввода');

Exit;

end;

Xnew[i,j]:=StrToFloat(ogrf.Cells[j,i]);

end;

ZNAC[i]:=ogrf.Cells[elkol.value+1,1];

if (ZNAC[i]<>'=') and (ZNAC[i]<>'>=') and (ZNAC[i]<>'<=') then

begin

ShowMessage('Ошибка ввода');

Exit;

end;

If (ZNAC[i]='=') or (ZNAC[i]='>=') then PriznacY:=1;

B[i]:=StrToFloat(ogrf.Cells[elkol.value+2,i]);

end;

For j:=1 to elkol.Value do

begin

Val(celf.Cells[j,1],chislo,errcode1);

if (celf.Cells[j,1]='') or (errcode1<>0) then

begin

ShowMessage('Ошибка ввода');

Exit;

end;

FX[j]:=StrToFloat(celf.Cells[j,1]);

end;

celf.Enabled:=False;

ogrf.Enabled:=False;

waitf.Show;

SIMPLEXM;

If waitf.Showing then waitf.Close;

resultf.Memo1.Lines.LoadFromFile('SIMPLEX.DAT');

resultf.ShowModal;

next.Enabled:=False;

sostoyanie:=sostoyanie+1;

end;

end;

//-----------------------------

end;

procedure Tmainf.FormCreate(Sender: TObject);

begin

sostoyanie:=1;

end;

procedure Tmainf.prevClick(Sender: TObject);

begin

case sostoyanie of

3:begin

sostoyanie:=sostoyanie-1;

ogrf.Enabled:=True;

celf.Enabled:=True;

next.Enabled:=True;

For i:= 1 to 30 do

begin

Fo[i]:=0;

FunctPr[i]:=0;

B[i]:=0;

H[i]:=0;

Hnew[i]:=0;

C[i]:=0;

Cnew[i]:=0;

CPr[i]:=0;

CPrnew[i]:=0;

FX[i]:=0;

MIN:=0;

I1:=0;

Kit:=0;

NachKell:=0;

NachY:=0;

K_st:=0;

PriznacY:=0;

KLstr:=0;

KLst:=0;

ErrCode:=0;

Dop_X:=0;

P:=0;

P1:=0;

Mo:=0;

F0:=0;

Epsilon:=0;

Z:=0;

DPx:=0;

DPy:=0;

Fm:=0;

Kell:=0;

Kstr:=0;

BS[i]:='';

Bvsp[i]:='';

ZNAC[i]:='';

for j:=1 to 30 do

begin

X[i,j]:=0;

Xnew[i,j]:=0;

end;

VSP:='';

S:='';

PrGomory:='';

PrOperBOX.Enabled:=True;

minmax.Enabled:=True;

end;

end;

2:begin

sostoyanie:=sostoyanie-1;

urkol.Enabled:=True;

elkol.Enabled:=True;

PrOperBOX.Visible:=True;

celf.Visible:=False;

ogrf.Visible:=False;

PrOperBOX.Visible:=False;

minmax.Visible:=False;

end;

end;

end;

procedure Tmainf.N4Click(Sender: TObject);

begin

Close;

end;

procedure Tmainf.N6Click(Sender: TObject);

begin

aboutf.ShowModal;

end;

procedure Tmainf.N7Click(Sender: TObject);

begin

autorsf.ShowModal

end;

procedure Tmainf.FormShow(Sender: TObject);

begin

startf.ShowModal;

end;

procedure Tmainf.N5Click(Sender: TObject);

begin

ShellExecute(Handle, nil, 'help.chm', nil, nil, SW_SHOW);

end;

end.