Балашовский филиал

bi0	x1	x2
x3
x4	4,6 –0,2486	0 –0,0418	0,0220 –0,0001	0,0345 –0,0112
x5	4,5 0	0,0426 00 0	0 0
x 6	2485,7 11,2019	417,7 1,8824	221,9 0,0045	112,24 0,5058
x7	9738,5 –7561,2508	1192,5 –1270,6016	675 –3,0419	270 –341,4229
	0 –562,2653	54,3 –94,4837	50,2 – 0,2262	27,0 –25,3887

В таблице 16 в последней строке нет положительных элементов, следовательно, последнее опорное решение (0; 0; 22,1469; 3,8350; 4,5; 0; 3759,0449) является оптимальным.
Таблица 15

	bi0	x1	x6	x3
x4	4,3514 –0,5164	–0,0418 –0,0868	–0,0001 –0,0002	0,0233 –0,0461
x5	4,5 0	0,0426 0	0 0	0 0
x 2	11,2019 22,1469	1,8824 3,7216	0,0045 0,0089	0,5058 1,9771
x7	2177,2492 1581,7957	–78,1016 265,8096	–3,0419 0,6354	–71,4229 141,2078
	–562,2653 –35,6848	–40,1837 –5,9966	–0,2262 –0,0143	1,6113 –3,1856

Таблица 16

	bi0	x1	x6	x2
x4	3,8350	–0,1286	–0,0003	–0,0461
x5	4,5	0,0426	0	0
x3	22,1469	3,7216	0,0089	1,9771
x7	3759,0449	187,7080	–2,4065	141,2078
	–597,9501	–46,1803	–0,2405	–3,1856

Дадим интерпретацию полученным результатам:
— для получения наибольшей выручки глянцевую ткань выпускать не надо;
— для получения наибольшей выручки ткань «Турист» выпускать не надо;
— для получения наибольшей выручки курточную ткань надо выпускать в объеме 22,1469 тыс. м ежемесячно;
— остаток в тыс. станко-часов рабочего времени СГ;
— СТГ не использовались (глянцевая ткань не выпускалась);
— нити израсходованы полностью;
— остаток в кг красителей;
— наибольшая ежемесячная выручка в тыс. руб. за выпущенную продукцию.

4. Реализация алгоритма симплекс-метода
на языке паскаль

Эта часть параграфа, посвященного симплекс-методу, будет полезна тем, кто хочет реализовать его на каком-либо языке программирования. Такая реализация существенно отличается от алгоритма, предложенного выше. Дело в том, что выбор базисных переменных — трудоемкая процедура, требующая в связи с возникающей вычислительной погрешностью весьма тонкого анализа получающихся результатов. Гораздо проще ввести искусственный базис — новые по отношению к КЗЛП переменные, количество которых равно количеству строк и которые заведомо образуют базис. Для простоты рассуждений будем полагать, что в КЗЛП, полученной из ОЗЛП, количество уравнений равно m, а количество пременных (старых и новых вместе) — n. Потребуем, чтобы правые части уравнений системы (1) в КЗЛП были неотрицательными: b_i ≥ 0, i = 1, 2,…, m. Если в каком-либо уравнении это не так, то умножим обе части его на
(–1). Ясно, что такое преобразование никоим образом не изменит решение. Добавим к левой части каждого уравнения системы в КЗЛП еще одну неотрицательную переменную: x_n+1, x_n+2,…, x_n+m. Будем называть их искусственными. Система (1) примет вид:

Ясно, что переменные x_n+1, x_n+2,…, x_n+m всегда образуют базис, так как в новой матрице системы размерами m×(n + m) коэффициенты при них образуют единичную подматрицу размерами m×m. Этот базис и будем называть искусственным. Далее, если мы выразим базисные переменные x_n+1, x_n+2,…, x_n+m через x₁, x₂,…, x_n, и найдем соответствующее базисное решение (0; 0;…; 0; b₁; b₂;…; b_т), то, в силу наложенных на систему (1) требований, оно будет неотрицательным, то есть опорным. Таким образом, автоматически решается вопрос о выборе базисных переменных для начала вычислений по симплекс-методу. Будем называть B-задачей новую КЗЛП, полученную из имеющейся (1)—(3):

(5)

(6)

(7)

здесь целевая функция (3) увеличена на , где B — достаточно большое число.
Имеется тесная связь между решениями задачи (1)—(3) и B-задачи (5)—(7). Во-первых, если существует оптимальное решение B-задачи
X^*= ( ), в котором последние m компонент равны нулю, то вектор ( ), очевидно удовлетворяющий системе ограничений (1), (2), является оптимальным решением задачи (1)—(3). Допустим, что это не так. Тогда существует вектор , удовлетворяющий (1) и (2), и для которого . Но Ясно, что вектор удовлетворяет системе ограничений (5), (6),
а значит, X^* не является оптимальным решением задачи (5)—(7). Получили противоречие. Во-вторых, если существуют сколь угодно большие значения B, такие, что в решении ( ) задачи (5)—(7) хотя бы одна из компонент с номером, большим n, больше нуля ( ), то система ограничений (1)—(2) противоречива. Доказывать этот факт мы не будем, но укажем, что на практике решается
B-задача для одного, достаточно большого B. Обычно его выбирают большим по модулю всех входящих в задачу числовых коэффициентов. В-третьих, если линейная форма (7) не ограничена снизу, то и линейная форма (3) не ограничена снизу, так как слагаемое может только увеличивать значение .
Для составления начальной симплекс-таблицы B-задачи выразим базисные переменные x_n+1, x_n+2,…, x_n+m через x₁, x₂,…, x_n:

(8)

и подставим их в целевую функцию (7). Получим:

О
(9)
бозначим Тогда получим
Для B-задачи с преобразованной целевой функцией модифицируем первоначальную симплекс-таблицу так, чтобы ее обработка легко алгоритмизировалась. Поэтому она немного будет отличатся от аналогичной таблицы, использующейся при расчетах вручную (см. таблицу 17). Номера строк этой модифицированной таблицы с 0-й по m + 1-ю отражены в ее первой графе, а номера столбцов с 0-го по n + m + 1-й — в верхней строке. В памяти ЭВМ будет храниться двумерный массив A величин, обведенных жирной чертой. В программе этот массив задается как матрица со строками от 1 до 20 и столбцами от 0 до 40, вводится реальное количество уравнений M системы (1), количество переменных в ней N, а в дальнейшем обрабатывается его часть с номерами столбцов от 0 до N+M,
и с номерами строк от 1 до M + 1, в нулевом столбце хранятся значения свободных членов, в столбцах с 1-го по n-й хранятся коэффициенты при соответствующих свободных переменных, а в последней, M + 1-й, строке хранятся и в дальнейшем преобразуются вместе со всей симплекс-таблицей коэффициенты целевой функции. При автоматических расчетах коэффициенты при свободных и базисных переменных хранятся в одном массиве: в столбце n + i базисной переменной _xn+i имеется один ненулевой коэффициент — единица в i-ой строке. Номера базисных переменных фиксируются в последнем, n + m + 1-м, столбце симплекс-таблицы 17 (выделен точками), а в программе эти номера хранятся в массиве NOM.
В начале расчетов эти номера совпадают с номерами искусственных переменных. Наша цель — получить решение исходной КЗЛП, если оно имеется, а для этого надо перевести все базисные переменные _xn+1, _xn+2,…, _xn+m в свободные. В нулевой строке таблицы 17 в столбцах от n+1-го по
n + m-й будем ставить метки, указывающие на факт удаления соответствующей искусственной переменной из базиса (выделена пунктиром).
В самом начале все метки — нули. При переводе искусственной базисной п
еременной в свободные метка становится равной 1. В программе эти метки хранятся в массиве MET.

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

не заводить вспомогательного массива для хранения «нижних» значений, в программе используется изящный прием (его можно применять и при вычислениях вручную, но при этом нужно особо внимательно следить за алгоритмом). Сначала все элементы разрешающей строки меняют свое значение на частное от деления, т. е. делятся на разрешающий элемент
и «записываются вверху», что соответствует полным преобразованиям разрешающей строки в жордановых исключениях. Пусть, как и ранее,
k — номер разрешающей строки, а s — номер разрешающего столбца.
В программе описанная процедура выглядит так:
For J:=0 To P Do A[K,J]:=A[K,J]/R;
Здесь P — число столбцов, R — значение разрешающего элемента. Теперь в клетке симплекс-таблицы с номерами i,j надо получить «нижний элемент» по формуле в_kj ∙н_is. Если в этот момент мы вычислим его как
-A[I,S]*A[K,J],
получим требуемый результат, ведь деление на разрешающий элемент, смена знака и «запись внизу» в разрешающем столбце в этой формуле заложены. Таким образом, сложение «верхнего» и «нижнего» значений в клетке симплекс-таблицы с номерами i,j и запись этой суммы «вверху» в программе осуществляется с помощью одного оператора присваивания:
A[I,J]:=A[I,J]-A[I,S]*A[K,J].
Ясно, что в модифицированной таблице перевод свободной переменной в базисные означает превращение разрешающего элемента в 1 и обнуление всех остальных элементов разрешающего s-го столбца, так как эта переменная выражается через свободные и не входит больше ни в одно из уравнений. Так мы и будем делать в программе.
И, наконец, на практике было установлено, что вследствие ошибок округлений результатов арифметических операций в таблице не получается «чистых» нулей. Поэтому при проверке числа на положительность сравнение осуществляется не с нулем, а с величиной «чуть большей» нуля,
с малым числом EPS. Все величины, меньшие либо равные EPS, считаются нулями или отрицательными величинами. Значение EPS устанавливается экспериментально, при отладке программы, и при более высокой точности вычислительной системы может быть уменьшено.

Program SIMPLEX;

{$R+}
uses crt;
Const
B=1E+8;{большое число}
EPS=1E-10;{малое число}
N_STOLBEC=40; {зарезервированное число столбцов}
N_STROKA=20; {зарезервированное число строк}
Type
VEKTOR=Array[0..N_STOLBEC] Of Real;
MATRICA=Array[1..N_STROKA,0..N_STOLBEC] Of Real;
NOMER=Array[1..N_STROKA] Of Byte;
METKA=Array[1..N_STOLBEC] Of Byte;
STROKA=String[40];
Var
F:VEKTOR;{массив коэффициентов целевой функции}
A:MATRICA;{симплекс-таблица}
NOM:NOMER;{массив номеров базисных переменных}
MET:METKA;{массив меток переменных}
SUM,R,C:Real;
M,N,W,M0,P,I,J,R1,K,S:Byte;

Procedure OPTIMALNOE_RESHENIE;

{вывод на экран оптимального решения}
Var X:VEKTOR;
Begin
WriteLn;
WriteLn('О П Т И М А Л Ь Н О Е Р Е Ш Е Н И Е');
FillChar(X,SizeOf(X),0); {обнуление массива X}
For J:=1 To N Do
Begin
{если в номерах базисных переменных есть номер J,
стоящий на K-м месте, то X[J] присваивается
значение свободного члена A[K,0], иначе — 0}
C:=0;
For K:=1 To M Do If NOM[K]=J Then C:=A[K,0];
X[J]:=C
End;
{находится значение целевой функции на векторе X}
{в массиве F сохранены значения коэффициентов
целевой функции исходной КЗЛП}
SUM:=F[0];
For J:=1 To N Do
Begin
WriteLn('X[',J,']=',X[J]);
SUM:=SUM+F[J]*X[J]
End;
WriteLn;
WriteLn('Целевая функция = ',SUM)
End;
{$V-}
Procedure Stop(S:Stroka);
{выводится строка S и программа завершается}
Begin
WriteLn(S);
Halt
End;

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

BEGIN
ClrScr;
FillChar(A,SizeOf(A),0);{обнуление массива A}
FillChar(F,SizeOf(F),0);{обнуление массива F}
FillChar(NOM,SizeOf(NOM),0);{обнуление массива NOM}
FillChar(MET,SizeOf(MET),0);{обнуление массива MET}
{ввод данных с клавиатуры и создание массива А}
Write('Сколько РАВЕНСТВ в системе ограничений?');
ReadLn(M);
Write('Сколько ПЕРЕМЕННЫХ в системе ограничений?');
ReadLn(N);
WriteLn;
WriteLn('Ведите по строкам матрицу коэффициентов');
WriteLn('и правые части системы ограничений');
WriteLn;
For I:=1 To M Do
Begin
WriteLn(I,' строка:');
For J:=1 To N Do
Begin
Write('Коэффициент при X',J,'?');
ReadLn(A[I,J])
End;
Write('Правая часть = ');ReadLn(A[I,0]);
{если правая часть отрицательная, то вся строка
меняет знак}
If A[I,0]<0 Then
For J:=0 To N Do A[I,J]:=-A[I,J]
End;
WriteLn;
WriteLn('Введите коэффициенты целевой функции');
WriteLn;
Write('Свободный член = ');ReadLn(A[M+1,0]);
For J:=1 To N Do
Begin
Write('Коэффициент при X',J,' ? ' );
ReadLn(A[M+1,J])
End;
WriteLn;
{коэффициенты целевой функции дублируются в массив
F, так в процессе решения они будут меняться}
F[0]:=A[M+1,0];
For J:=1 To N Do F[J]:=A[M+1,J];
A[M+1,0]:=-A[M+1,0];{для коррек-го вычисления γ_0}

{дальнейшее построение симплекс-таблицы В-задачи}

P:=N+M;{максимальный номер базисной переменной}
M0:=M+1;{переобозначение строки М+1 для удобства}
{заполняются столбцы с n+1-го по n+m-й}
For I:=1 To M Do
Begin
A[I,N+I]:=1;
{запоминаются номера базисных переменных}
Nom[I]:=N+I
End;
{вычисляются коэффициенты γ_J целевой функции в (9)}
For J:=0 To N Do
Begin
Sum:=0;
For I:=1 To M Do Sum:=Sum+A[I,J];
A[M0,J]:=B*Sum-A[M0,J]
End;
{формирование таблицы в массиве А завершено}
W:=0;{количество повторений жордановых исключений}
{пока среди базисных переменных есть искусственные,
повторяются жордановы исключения}
While P>=N Do
Begin
{поиск разрешающего столбца S}
S:=0;{начальный номер разрешающего столбца}
K:=0;{признак наличия положительного элемента}
{перебираются все столбцы с 1 по Р-й}
J:=1;
While J<=P Do
Begin
{если в последней строке есть положительный
элемент и соответствующая переменная — свободная}
If (A[M0,J]>Eps) And (Met[J]<>1)
Then
Begin
S:=J;{запоминается номер столбца}
I:=1;{в этом столбце перебираются все строки}
While I<=M Do
Begin
{если встретился положительный элемент, то
перебор в строке и поиск столбца надо закончить}
If A[I,J]>Eps
Then
Begin
{выход из цикла по J; закончен поиск столбца}
J:=P+1;
K:=I;{запоминается номер строки}
{выход из цикла по I; закончен перебор строк}
I:=M+1
End;
I:=I+1;
End
End;
J:=J+1;
End;
If S=0 {разрешающий столбец не найден}
Then
Begin
{если В-задача имеет оптимальное решение, в котором
компонента с номером, большим N, больше нуля}
If P>N
Then Stop('Система ограничений противоречива')
{все искусственные пер-е переведены в свободные}
Else
Begin
OPTIMALNOE_RESHENIE;
Halt{конец}
End
End
Else{разрешающий столбец найден}
Begin
If K=0{но положительных элементов в нем нет}
Then
Begin
If P>N{если среди базисных есть искусственные}
Then Stop('Система ограничений противоречива')
Else Stop('Форма не ограничена снизу')
End
End;
{поиск разрешающей строки K}
R:=B;{начальное значение минимума}
K:=0;{начальный номер строки с минимумом}
For I:=1 To M Do
Begin
If A[I,S]>EPS{если I,S-й элемент положительный}
Then
Begin
C:=A[I,0]/A[I,S];
If CThen
Begin R:=C;K:=I End
End
End;
{шаг жордановых исключений}
R:=A[K,S];{запоминается разрешающий элемент}
{разрешающая строка делится на разрешающий элемент,
и результат сразу «записывается вверху»}
For J:=0 To P Do A[K,J]:=A[K,J]/R;
{в остальных клетках таблицы, исключая разрешающую
строку и столбец, вычисления идут по формулам (10)}
For I:=1 To M0 Do
Begin
If I<>K
Then
Begin
For J:=0 To P Do
If J<>S Then A[I,J]:=A[I,J]-A[I,S]*A[K,J]
End
End;
{зануляются все элементы S-го столбца, кроме K-го}
For I:=1 To M0 Do If I<>K Then A[I,S]:=0;
R1:=NOM[K];{номер старой базисной пер-й}
NOM[K]:=S;{номер новой базисной переменной}
If R1>N
Then
Begin
{отмечается, что она стала свободной переменной}
MET[R1]:=1;
{количество повторений жордановых исключений
увеличивается на 1}
W:=Succ(W)
End;
{если количество повторений жордановых исключений
больше либо равно М — количеству базисных пер-х}
If W>=P-N Then P:=N{завершение симплекс-метода}
End
END.