Практика математического программирования

Оглавление

Введение

1. Основная часть

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

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

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

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

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

1.2.1Пример решения задачи с использованием симплекс-метода

1.2.2Текст программы на языке программирования Turbo Pascal

1.2.3Текст программы на языке программирования Borland Delphi 7

2.Тестовые примеры

Заключение

Литература

Введение

Первым исследованием по линейному программированию является работа Л. В. Кантфовича “Математические методы организации и планирования производства”, опубликованная в 1939 г. В нем дана постановка задач линейного программирования, разработан метод разрешающих множителей решения задач линейного программирования и дано его теоретическое обоснование.

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

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

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

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

1.Основная часть

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

· x_j на y_i;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

	СЧ	x1	x2	x3
y1	3	2	1	2
y2	1	2	3	-1
y3	2	1	-1	0
y4	1	0	-1	0

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

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

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

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

В данной системе 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).

1.2.1Текст программы на языке программирования Turbo Pascal.

PROGRAM SIMPLEX_METOD;

USES CRT;

LABEL ZN,ST,ELL,_END;

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

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

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

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

X,Xnew:MASX;

BS,Bvsp,ZNAC:MASB;

MIN,I1,I,J,Kx,Ky,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;

{ Функция создания индексов :) AS }

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

ASSIGN(F,'SIMPLEX.TXT');

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;

CLOSE(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 SIMPLEX;

LABEL POVZNAC,NACH;

BEGIN

{ Подготовка к вводу данных }

NachKell:=Kell;

DPx:=Kell+1;

DPy:=1;

Kx:=1;

Ky:=4;

Epsilon:=0.00001;

CLRSCR;

WRITELN(' Введите систему уравнений: ');

WRITELN(' (коэффициенты при всех X, знак и свободные члены) ');

{ Ввод данных }

FOR I:=1 TO Kstr DO

BEGIN

POVZNAC:

WRITELN(' Введите ',I,'-е уравнение: ');

{ Ввод коэффициентов при Х в I-том уравнении }

FOR J:=1 TO Kell DO

BEGIN

GOTOXY(Kx,Ky);

Kx:=Kx+6;

READLN(Xnew[I,J]);

END;

{ Ввод знака в I-том уравнении }

Kx:=Kx+6;GOTOXY(Kx,Ky);READLN(ZNAC[I]);

{ Проверка введенного знака на правильность }

IF (ZNAC[I]<>'>=') AND (ZNAC[I]<>'=') AND (ZNAC[I]<>'<=')

THEN BEGIN

WRITELN(' неправильно задан знак ');

Ky:=Ky+3;Kx:=1;

GOTO POVZNAC;

END;

IF (ZNAC[I]='=') OR (ZNAC[I]='>=') THEN PriznacY:=1;

{ Ввод свободного члена в I-том уравнении }

Kx:=Kx+6;

GOTOXY(Kx,Ky);

READ(B[I]);

Kx:=1;

Ky:=Ky+2;

END;

WRITELN(' Введите коэффициенты при Х в целевой функции: ');

{ Ввод коэффициентов при Х в целевой функции }

FOR J:=1 TO Kell DO

BEGIN

GOTOXY(Kx,Ky);Kx:=Kx+6;

READ(FX[J]);

END;

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

FOR J:=1 TO Kell DO

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

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

FOR I1:=1 TO Kstr DO

DOP_PER;

{ Замена оптимальной функции с МАХ на 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;

CLRSCR;

{ Подготовка столбцов 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 Б H ',2);

FOR J:=1 TO Kell DO

BEGIN

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

P1:=LENGTH(Bvsp[J]);

F 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

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

HALT;

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;

HALT;

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

HALT;

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

HALT;

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;

{ Основная программа }

BEGIN

CLRSCR;

Kit:=0;

Dop_X:=0;

ASSIGN(F,'SIMPLEX.TXT');

REWRITE(F);

CLOSE(F);

ST:;

WRITE(' Введите кол-во строк: ');READLN(Kstr);

IF Kstr>10 THEN

BEGIN

WRITELN('Программа не расчитана на введеное кол-во строк!');

GOTO ST;

END;

ELL:

WRITE('Введите кол-во элементов: ');READLN(Kell);

IF Kell>10 THEN

BEGIN

WRITELN('Программа не расчитана на введеное кол-во элементов!');

GOTO ELL;

END;

ZN:

WRITE('Исследуем на Максимум(1) или на Минимум (2):');READLN(Fm);

IF (Fm<>1) AND (Fm<>2) THEN

BEGIN

WRITELN('Введите снова');GOTO ZN;

END;

WRITE(' Целочисленное решение (Y/N): ');READLN(PrGomory);

IF (PrGomory='Y') OR (PrGomory='y') THEN PrGomory:='Y' ELSE PrGomory:='N';

{ Вызов процедуры SIMPLEX}

SIMPLEX;

END.

1.2.3Текст программы на языке программирования Borland Delphi 7

unit Unit1;

interface

uses

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

Dialogs, StdCtrls, Grids, jpeg, ExtCtrls;

type

Tproga = class(TForm)

KolvoElem: TComboBox;

Label1: TLabel;

StringGrid1: TStringGrid;

Button1: TButton;

KolvoStrok: TComboBox;

Label2: TLabel;

GroupBox1: TGroupBox;

Label3: TLabel;

Issled: TComboBox;

Label4: TLabel;

CelechResh: TComboBox;

Er: TLabel;

Button2: TButton;

Label5: TLabel;

Image1: TImage;

SaveDialog1: TSaveDialog;

MainMenu1: TMainMenu;

N1: TMenuItem;

N2: TMenuItem;

N3: TMenuItem;

N4: TMenuItem;

procedure KolvoElemChange(Sender: TObject);

procedure Button1Click(Sender: TObject);

procedure KolvoStrokChange(Sender: TObject);

procedure IssledChange(Sender: TObject);

procedure CelechReshChange(Sender: TObject);

procedure Button2Click(Sender: TObject);

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

procedure N2Click(Sender: TObject);

procedure N4Click(Sender: TObject);

procedure N3Click(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

Form1: TForm1;

er_1, er_2, er_3, er_4, xm, ym:integer;

Fo,FunctPr,B,H,Hnew,C,Cnew,CPr,CPrnew,FX:ARRAY[1..30] OF REAL;

X,Xnew:ARRAY[1..30,1..30] OF REAL;

BS,Bvsp,ZNAC:ARRAY[1..30] OF STRING[3];

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

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

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

fil_e,VSP,S,PrGomory:STRING;

F:TEXT;

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

implementation

{$R *.dfm}

procedure TForm1.KolvoElemChange(Sender: TObject);

begin

case KolvoElem.ItemIndex of

0: xm:=2;

1: xm:=3;

2: xm:=4;

3: xm:=5;

4: xm:=6;

5: xm:=7;

6: xm:=8;

7: xm:=9;

8: xm:=10;

end;

end;

procedure TForm1.KolvoStrokChange(Sender: TObject);

begin

case KolvoStrok.ItemIndex of

0: ym:=2;

1: ym:=3;

2: ym:=4;

3: ym:=5;

4: ym:=6;

5: ym:=7;

6: ym:=8;

7: ym:=9;

8: ym:=10;

end;

end;

procedure TForm1.IssledChange(Sender: TObject);

begin

case Issled.ItemIndex of

0: Fm:=1;

1: Fm:=2;

end;

end;

procedure TForm1.CelechReshChange(Sender: TObject);

begin

case CelechResh.ItemIndex of

0: PrGomory:='Y';

1: PrGomory:='N';

end;

end;

procedure TForm1.Button1Click(Sender: TObject);

var

ii:integer;

begin

if ym=0 then ym:=2;

if xm=0 then xm:=2;

if PrGomory='' then PrGomory:='Y';

if Fm=0 then Fm:=1;

Kell:=xm;

Kstr:=ym;

StringGrid1.ColCount:=xm+3;

StringGrid1.RowCount:=ym+2;

for ii:=1 to ym do

StringGrid1.Cells[0,ii]:='Y'+IntToStr(ii)+'=';

for ii:=1 to xm do

StringGrid1.Cells[ii,0]:='X'+IntToStr(ii);

StringGrid1.ColCount:=xm+3;

StringGrid1.RowCount:=ym+2;

StringGrid1.Cells[0,0]:='Урав\Коэф';

StringGrid1.Cells[0,ym+1]:='F=';

StringGrid1.Cells[xm+1,0]:='знак*';

StringGrid1.Cells[xm+2,0]:='своб.член';

er2:=1;

end;

{ Функция создания индексов :) AS }

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

VAR

M,Z:STRING;

BEGIN

M:=IntToStr(V);

Z:=S+M;

SIMVB:=Z;

END;

{ Процедура записи данных в файл }

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

VAR

V:STRING;

BEGIN

ASSIGNfile(F, fil_e);

APPEND(F);

CASE Mstr OF

0:WRITELN(F,'');

1:BEGIN

IF K=' ' THEN V:=FloatToStrF(X1, ffFixed, 1, 0)

ELSE V:=' '+FloatToStrF(X1, ffFixed, 10, 2)+' ';

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+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 TForm1.Button2Click(Sender: TObject);

label

NACH,Kon;

begin

Er.Caption:='';

{ Подготовка к вводу данных }

NachKell:=Kell;

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

Kx:=1;Ky:=4;

Epsilon:=0.00001; { Ввод данных }

FOR I:=1 TO Kstr DO

BEGIN

{ Ввод коэффициентов при Х в I-том уравнении }

FOR J:=1 TO Kell DO

val(StringGrid1.Cells[j,i],Xnew[I,J],er_1);

{ Ввод знака в I-том уравнении }

ZNAC[I]:=StringGrid1.Cells[xm+1,i];

{ Ввод свободного члена в I-том уравнении }

val(StringGrid1.Cells[xm+2,i],B[I],er_2);

{ Проверка введенного знака на правильность }

IF (ZNAC[I]<>'>=') AND (ZNAC[I]<>'=') AND (ZNAC[I]<>'<=')

THEN er_3:=1;

IF (ZNAC[I]='=') OR (ZNAC[I]='>=') THEN PriznacY:=1;

end;

{ Ввод коэффициентов при Х в целевой функции }

FOR J:=1 TO Kell DO

val(StringGrid1.Cells[j,ym+1],FX[J],er_4);

Er.Caption:='';

if (er_1<>0) or (er_2<>0) or (er_3<>0) or (er_4<>0)

then Er.Caption:='Неверно введено: ';

if er_1<>0 then Er.Caption:=Er.Caption+' "число"';

if er_2<>0 then Er.Caption:=Er.Caption+' "свободный член"';

if er_3<>0 then Er.Caption:=Er.Caption+' "знак" ';

if er_4<>0 then Er.Caption:=Er.Caption+' "коэффициен при Х в целевой функции"';

er_1:=0;

er_2:=0;

er_3:=0;

er_4:=0;

if (Er.Caption<>'') then

begin

MessageDlg (Er.Caption,mtError, [mbOk], 0);

goto Kon;

end;

SaveDialog1.Filter:='Текстовый файл (*.txt) |*.txt';

SaveDialog1.Title:='Сохранение результата';

SaveDialog1.FilterIndex:=2;

if SaveDialog1.Execute then

begin

if SaveDialog1.fileName='' then goto kon;

fil_e:=SaveDialog1.fileName+'.txt';

ASSIGNfile(F,fil_e);

REWRITE(F);

CLOSEfile(F);

end;

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

FOR J:=1 TO Kell DO

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

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

FOR I1:=1 TO Kstr DO

DOP_PER;

{ Замена оптимальной функции с МАХ на 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 Б 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);

goto Kon;{HALT; }

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;

goto kon;{HALT;}

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

goto Kon;{HALT; }

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

goto Kon;{ HALT; }

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

Kon:

end;

PROCEDURE Tproga.Formclose(Sender: Tobject; Var Action: Tcloseaction);

BEGIN

HALT;

END;

PROCEDURE Tproga.N2click(Sender: Tobject);

BEGIN

proga.visible:=false;

title.visible:=true;

END;

PROCEDURE Tproga.N4click(Sender: Tobject);

BEGIN

CLOSE;

END;

PROCEDURE Tproga.N3click(Sender: Tobject);

BEGIN

Info.visible:=true;

END;

BEGIN

ER2:=0;

KIT:=0;

DOP_X:=0;

END.

2.Тестовые примеры

Пример №1.

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

Программа выводит данные:

В 4-й итерации было получено оптимальное решение.

Результат решения:

Fmax=80

X₁=10

X₃=8

X₆=12

Пример №2.

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



Программа выводит данные:

В 6-й итерации было получено оптимальное решение.

Результат решения:

Fmin=75

X₃=10

X₂=9

X₅=45

Заключение

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

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

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

· Инструкции пользователю не нужны, так как данные программы просты и практически не требует времени на освоение.

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

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

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

Внешний вид первый программы на Turbo Pascal:

Литература

1. Г. Жимерин, В. А. Мясников - Автоматизированные и автоматические системы уравнения. М.: Энергия, 1975г. - 680с.

2. Е. С. Венцель - Исследование операций. М.: Сов. наука, 1972г. - 552с.

3. С. Бобровский - Delphi 6 и Kylix: библиотека программиста. СПб.: Питер, 2002г. - 560с.

4. Всемирная сеть - Интернет