Пусть столбец, который может стать разрешающим, имеет номер j, то есть Это означает, как уже говорилось выше, можно уменьшить значение целевой функции путем увеличения значения xj, оставляя все другие свободные переменные без изменений, то есть равными нулю.
В системе (4), на основе которой построена симплекс-таблица 4, имеем:

Ясно, что увеличивая xj, надо следить за тем, чтобы x1, x2,…, xk оставались неотрицательными. Здесь возможны два случая:

а) Все коэффициенты bij < 0, i = 1,…, k. Тогда значение xj можно увеличивать неограниченно, от этого произведения -bijxj будет только расти, и все переменные x1, x2,…, xk будут неограниченно возрастать, то есть требование их неотрицательности не будет нарушено. Целевая функция при этом (X) = не будет ограничена снизу:

б) Среди bij , i = 1,…, k имеются положительные, и таких чисел может быть несколько. Пусть brj > 0 r = 1 или r = 2, или …, или r = k. Ясно, чтобы выполнялось условие xr = br0 - brjxj ? 0, надо потребовать выполнения равносильного неравенства , то есть переменную xj можно увеличивать, но только до величины . И такие неравенства должны выполнятся для всех строк j-го столбца, в которых brj > 0. Следовательно, надо для таких строк определить величину

Ясно, что xj можно увеличивать, но не более чем до K. Значит, xj надо менять местами с той базисной переменной, в которой строке указанный минимум достигается.

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

В разрешающем столбце j находится строка с номером i, для которой достигается Строка i -- разрешающая строка. Перейти к пункту 6.

Меняются местами переменные xj и xi. Для этого в последней симплекс-таблице надо выполнить жордановы исключения по соответствующему алгоритму. Вернуться к пункту 3.

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

Пример 1. Рассмотрим задачу 4 из п. 6 § 2. Имеем общую задачу:

Путем введения новых неотрицательных переменных приведем ее к каноническому виду:

Определим ранг матрицы коэффициентов системы уравнений.
В нашем случае ясно, что он равен 4, так как коэффициенты при новых переменных образуют единичную подматрицу. Еще более очевидно, что переменные x3, x4, x5, x6 могут одновременно быть выражены через x1 и x2. Таким образом, x3, x4, x5, x6 являются базисными переменными, а x1 и x2 -- свободными. В этом случае система (4) имеет вид:

Составим для полученной системы и целевой функции симплекс-таблицу (таблица 9). X = (0; 0; 322; 70; 180; 100) -- опорный план, с которого мы начинаем движение в сторону уменьшения значения . Для него = 0. Значения x3, x4, x5, x6 считываются из столбца свободных членов bi0, так как именно эти значения получаются, если свободные переменные равны нулю. линейный программирование паскаль модульный

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

Рассмотрим столбец x2. В нем есть положительные коэффициенты в строках при x3, x4 и x6.

Находим, в какой из этих строк достигается Видим, что и достигается в строке при x6. Значит, эта строка будет разрешающей.

Отметим в таблице разрешающую строку, разрешающий столбец, разрешающий элемент и выполним один шаг жордановых исключений, то есть переведем переменную x2 в базисные, а x6 -- в свободные. Преобразования исходной таблицы отражены в таблице 10, а новая симплекс-таблица представлена в верхних треугольниках таблицы 11. В дальнейшем для экономии места в случае, если новая таблица снова подвергается преобразованиям, будем в ней заполнять нижние треугольники, что соответствует следующим жордановым исключениям. Так сделано в таблице 11, судя по которой значение от 0 в начале процесса вычислений уменьшилось до -5 000. Это значение целевой функции на опорном плане X = (0; 50; 122; 20; 180; 0). Значения x3, x4, x5, x2 считываются из столбца свободных членов bi0. Вернемся к пункту 3 алгоритма симплекс-метода.

Видим, что в последней строке таблицы 11 (рассматриваем только верхние треугольники) положительный элемент только один -- в столбце x1.

Этот столбец -- разрешающий, так как в нем в строках при x3, x5 и x2 находятся положительные коэффициенты.

Находим, в какой из этих строк достигается Видим, что , и достигается в строке при x3. Значит, эта строка будет разрешающей.

Отметим в таблице 11 разрешающую строку, разрешающий столбец, разрешающий элемент и выполним один шаг жордановых исключений, то есть переведем переменную x1 в базисные, а x3 -- в свободные. Преобразования исходной таблицы отражены в нижних треугольниках таблицы 11, а новая симплекс-таблица представлена в верхних треугольниках таблицы 12. По таблице 12 находим, что значение от -5 000 на предыдущем шаге симплекс-метода уменьшилось до -7 135. Это -- значение целевой функции на опорном плане X = (61; 34,75; 0; 35,25; 58; 0). Значения x1, x4, x5, x2 считываются из столбца свободных членов bi0. Вернемся к пункту 3 алгоритма симплекс-метода.

Видим, что в последней строке таблицы 12 положительных элементов нет. Это означает, что найденное опорное решение является оптимальным: X*= (61; 34,75; 0; 35,25; 58; 0). Наименьшее значение равно -7?135. Интерпретируем полученные результаты:

-- оптимальный выпуск задвижек в день составляет 61 штуку;

-- оптимальный выпуск тисков в день составляет 34,75 штук;

-- сталь-45 при таком выпуске расходуется полностью;

-- остаток чугуна (кг) на складе за 1 день;

-- остаток бронзы (кг) на складе за 1 день;

-- сталь-3 при таком выпуске расходуется полностью;

-- наибольшая выручка (руб.) за день за выпущенную продукцию.

Получили то же решение, что и в § 1.1.

Если выпускать 34,75 тисков в день нельзя, то этот результат можно интерпретировать так: оптимальным является выпуск 34,75 · 4 = 139 штук тисков за 4 дня. Остальные цифры также должны быть соответственно пересчитаны. Можно поступить и по-другому: оптимальным считать выпуск 34 тисков в день. Но в этом случае необходимо пересчитать выручку, остаток стали-45, чугуна и стали-3.

Заметим, что выбирая разрешающий столбец в таблице 1 (пункт 4), можно было бы остановиться и на столбце переменной x1: в последней строке этого столбца и в других строках есть положительные элементы.
В этом случае решение пошло бы по другому пути. Убедитесь в этом самостоятельно. Порядок жордановых исключений в этом случае таков: x1 меняем с x5, x2 меняем с x3, x5 меняем с x6. Значения целевой функции при этом будут уменьшаться так: 0, -5 400, -6 700, -7 135.

Пример 2. Рассмотрим конкретную экономическую ситуацию. На АООТ «Балтекс» для выпуска глянцевой ткани, ткани «Турист» и курточной ткани используются ткацкие станки двух типов: станки гидравлические и станки ткацкие бесчелночные (коротко: СГ и СТБ) с различной производительностью. Для изготовления указанных видов ткани используются нити и красители. Ресурсы времени работы станков, нитей и красителей ограничены. В таблице 13 указаны ежемесячные ресурсы времени работы станков в тысячах станко-часов, нитей и красителей в килограммах, производительность станков в метрах на час, нормы расхода нитей и красителей в килограммах на тысячу метров каждого вида ткани и цена 1 м ткани. Требуется организовать выпуск продукции так, чтобы ежемесячная выручка предприятия была максимальной.

Составим математическую модель задачи. Пусть x1, x2 и x3 -- количество в тыс. м глянцевой ткани, ткани «Турист» и курточной ткани соответственно, выпускаемой ежемесячно. На выпуск x1 тыс. м глянцевой ткани на СТБ с производительностью 23,5 м/ч будет потрачено тыс. ст.-ч, на выпуск x2 тыс. м ткани «Турист» на СГ с производительностью 45,5 м/ч -- тыс. ст.-ч, на выпуск x3 тыс. м курточной ткани на СГ с производительностью 29 м/ч -- тыс. ст.-ч. Другие соотношения достаточно очевидны. Получим:

Перейдем к КЗЛП, оставив для корректного выполнения алгоритма в дробях 4 знака после запятой:

Ясно, что базис в системе линейных уравнений образуют новые переменные x4, x5, x6, x7. Не проводя подробные рассуждения, как в предыдущем примере, укажем только симлекс-таблицы (таблицы 14--16), отражающие решение. Все величины будем сохранять с 4 знаками после запятой. Здесь в таблице 14, в отличие от предыдущего примера, совмещены исходная и преобразованная по алгоритму жордановых исключений таблица.

Таблица 14

	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 0	0 0	0 0
x6	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
x2	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) в КЗЛП были неотрицательными: bi ? 0, i = 1, 2,…, m. Если в каком-либо уравнении это не так, то умножим обе части его на (-1). Ясно, что такое преобразование никоим образом не изменит решение. Добавим к левой части каждого уравнения системы в КЗЛП еще одну неотрицательную переменную: xn+1, xn+2,…, xn+m. Будем называть их искусственными. Система (1) примет вид:

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

здесь целевая функция (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-задачи выразим базисные переменные xn+1, xn+2,…, xn+m через x1, x2,…, xn:

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



Обозначим

Тогда получим

Для 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 C<R

Then

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.

5. Упражнения

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

4. Решение задачи линейного программирования в Excel

1. Автоматизация решения задачи линейного программирования

Для решения оптимизационных задач можно использовать надстройку «Поиск решения» табличного процессора Excel. В Microsoft Office Excel 2007 надстройка «Поиск решения» доступна на вкладке Данные в группе Анализ. Если она еще не загружена, ее необходимо загрузить. Необходимую инструкцию можно найти в Справке (Рис. 23).

После загрузки надстройка «Поиск решения» появится на вкладке Данные в группе Анализ (Рис. 24).

Рассмотрим решение задачи о выборе оптимального рациона питания со стр. 39 в табличном процессоре Excel с помощью инструмента «Поиск решения»:

L(x) = 7x1 + 9x2 > min (минимизация стоимости рациона), при ограничениях:

x10, x2 0.

При нажатии на кнопку Поиск решения появится диалоговое окно (Рис. 25).

Инструмент «Поиск решения» приложения Microsoft Office Excel использует программу нелинейной оптимизации Generalized Reduced Gradient. Чтобы правильно провести этот диалог, надо подготовить данные задачи в ячейках листа. При этом часть ячеек будет содержать подписи (т. е. текст, подписи обрабатываться не будут, их назначение -- сделать диалог максимально удобным, легко воспринимаемым пользователем), а часть -- расчетные формулы или конкретные числовые значения. Как видим на Рис. 25, во-первых, в диалоге надо сослаться на ячейку листа, в которой хранится значение целевой функции: Установить целевую ячейку, и выбрать радиокнопку в соответствии с условием оптимизации. Во-вторых, на листе надо выбрать ячейки, в которых будут храниться текущие значения переменных, входящих в задачу: Изменяя ячейки. Для этого в ячейках А1 и А2 разместим подписи «х1» и «х2» соответственно, а под ними, в ячейках В1 и В2 -- первоначальные значения этих переменных, например, числа 100 и 100 соответственно. В-третьих, необходимо указать ограничения в окне Ограничения. Для этого в ячейках А4:А6 разместим подписи «28x1+32x2=», «47x1 + 83x2=», «x1=» соответственно, а в ячейках справа от них -- В4:В6 -- формулы со ссылками на ячейки А2 и В2, в которых хранятся значения x1 и x2: «=28*A2 + 32*B2», «=47*A2+83*B2», «=A2». При этом в ячейках В4:В6 появятся соответствующие начальным значениям переменных числа -- значения рассчитываемых величин белков, углеводов и смеси № 5.

Далее в ячейке А8 поместим подпись целевой функции, а в ячейке справа от нее -- расчетную формулу. Чтобы увидеть все формулы одновременно, надо на вкладке Формулы в группе Зависимости формул нажать кнопку Показать формулы (Рис. 27).

При этом текст формул в ячейках выравнивается по левому краю.

После того, как необходимая подготовка листа выполнена, вызывается инструмент «Поиск решения», в окне Установить целевую ячейку указывается ссылка на ячейку $B$8 (в то время, как указатель находится в окне, достаточно щелкнуть по этой ячейке и перейти в другое окно диалога), выбирается радиокнопка минимальному значению. В окне Изменяя ячейки необходимо протащить мышь по ячейкам значений x1 и x2: $A$2:$B$2. Примерный вид экрана после этих действий изображен на Рис.

Рис.. Проведение диалога в окне Поиск решения

Подробно опишем добавление ограничения по белкам. В окне Ссылка на ячейку сошлемся на ячейку, в которой хранится рассчитанное по формуле текущее значение количества белков, т. е. на $B$4. В среднем окне из списка выберем тип ограничения: >=. В окне Ограничение укажем конкретное значение 14

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

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

Рис. Оптимальное решение задачи о рационе питания

Полученное решение совпадает с решением, найденным ранее с помощью графического метода. При этом ограничения по белкам и углеводам являются активными, так как их оптимальные значения в ячейках В4 и В5 в точности равны правым частям соответствующих неравенств. Далее можно провести эксперимент с данным сценарием, задавая различные начальные значения переменных в ячейках А2 и В2, в том числе и отрицательные. Легко убедиться в том, что независимо от начальных значений x1 и x2, встроенный алгоритм поиска оптимального решения задачи линейного программирования будет давать один и тот же результат. Такое свойство алгоритма называется устойчивостью по начальным данным.

Предложенный вариант оформления листа книги Excel для применения инструмента «Поиск решения» не является оптимальным. Например, для того, чтобы решить эту же задачу при других коэффициентах в ограничениях и целевой функции, надо в ячейке с соответствующей формулой вручную изменить такие коэффициенты. А при изменении правых частей ограничений необходимо вызвать диалоговое окно Поиск решения и поменять правые части в ограничениях в соответствующем окне. Можно предложить другой, более универсальный, способ расположения данных задачи и оформления ссылок.

В этом случае во всех ячейках находятся конкретные числа, в ячейке D7 и лежащих ниже -- формулы. Причем, если в D7 поместить формулу «=B7*$B$3+C7*$C$3», то ее можно скопировать вниз в ячейки D8, D9, D12, и необходимые формулы в них появятся автоматически. Значительно упрощается при этом и организация диалога в окне Поиск решения.

Рис. 34. Организация диалога в окне Поиск решения

Для решения одной конкретной задачи можно использовать любой из предложенных подходов, но если требуется провести экономический анализ, то второй, несомненно, будет предпочтительнее. Ведь в этом случае нет необходимости менять сценарий, вносить поправки в окне Поиск решения, достаточно менять числа на листе книги Excel. Например, выясним, при какой минимальной стоимости в рублях килограмма В-риса ограничение по смеси № 5 становится активным при неизменной стоимости смеси № 5. Будем менять в сторону увеличения цену 1 кг В-риса с шагом 1, каждый раз возвращая начальные значения 100 и 100 в ячейки В2 и С2 и запуская инструмент «Поиск решения». Тогда при цене 13 руб./кг В-риса получим, что активными станут ограничения по углеводам и смеси № 5.



Рис. Результат экономического анализа по изменению целевой функции

Приведем еще несколько примеров использования инструмента «Поиск Решения».

Рассмотрим пример со с. 13, так называемую транспортную задачу (ТЗ). Ее графическое решение представлено на с. 34--36. Исходную ситуацию в ТЗ удобно представить в специальной таблице -- макете, в которой отражены запасы у поставщиков Аi, потребности (заявки) потребителей Bj и тарифы перевозок Cij. На Рис. 36 такая таблица обведена утолщенной рамкой, а собственно тарифы В3:D4 выделены имеющими яркие границы ячейками. Остальные данные ясны из подписей в этой таблице. Особенность подготовки данных ТЗ на листе книги Excel состоит в том, что нет возможности подписать переменные: они имеют табличную структуру и характеризуются двумя индексами. Ниже таблицы тарифов создадим точно такую же таблицу начальных значений переменных В8:D9, не подписывая их. Ясно, что формулы суммирования по строкам или по столбцам можно автоматически набирать с помощью кнопки автосуммы и дальнейшего копирования. Для удобства формирования целевой функции создадим ниже таблицу произведений тарифов на перевозки В13:D14, набрав формулу «=B3*B8» в ячейке В13 и скопировав ее по горизонтали, а затем всю строку -- по вертикали.



Рис. Подготовка данных транспортной задачи

Тогда в ячейке значения целевой функции можно задать формулу «=СУММ(B13:D14)». Все необходимые формулы показаны на.

Рис. Формулы при подготовке данных транспортной задачи

Окно Поиск решения должно содержать требование неотрицательности, наложенное на все переменные.

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

Результат работы инструмента «Поиск решения» представлен на рис. 41.



Рис. Оптимальное решение транспортной задачи

2. Графическое решение задачи линейного программирования в Excel

Рассмотрим пример со с. 46 (Задача 4. Лист, подготовленный к применению инструмента «Поиск решения» выглядит как на.

Рис. Перечень формул в задаче об оптимальном использовании сырья

Покажем, как можно с помощью Excel графически построить МДР, найти оптимальное значение целевой функции, провести экономический анализ. Самое трудное, выбрать точки для построения прямых -- границ ограничений -- на диаграмме Excel. Поскольку границей каждого ограничения является прямая, заданная в виде «в отрезках» , то можно выбрать точки пересечения таких прямых с осями координат: (0; c/b) и (c/a; 0). Но такой подход возможен, если граница не параллельна ни одной из осей координат, то есть в случае, когда ни один из коэффициентов при переменных в уравнении прямой не обращается в 0. В случае же задания границы в виде прямую будем задавать точками (c/a; c/a) и (c/a; 0), а в случае -- точками (0; c/b) и (c/b; c/b). В дальнейшем покажем, как точку с ненулевыми координатами можно уточнить, добиваясь наиболее привлекательного вида ОДР. Для рассмотренной задачи введем формулы координат необходимых точек прямых в части листа после заголовка «Точки графиков».

Рис. Задание точек пересечения с осями

Здесь в ячейках В16 и С16 хранятся координаты точки пересечения границы ограничения по стали-45 с осью Oy, а в ячейках В17 и С17 -- с осью Ох. Граница ограничения по чугуну параллельна оси Ох, поэтому в соответствии с изложенным выше соглашением в ячейки В18 и С18 поместим координаты 0 и c/b соответственно, а в В19 и С19 -- c/b и c/b. Аналогично задаем точки для построения границ ограничений по бронзе, стали-3 и прямой, отражающей положение целевой функции для текущих значений переменных, которые, напоминаем, задаются произвольно. Далее построим диаграмму, содержащую единственную прямую -- границу первого ограничения по стали-45: выделив ячейки В16:С17, вызовем Вставка -- Точечная -- Точечная с прямыми отрезками.

Рис. Вставка диаграммы ограничения по стали-45

Рис. Диаграмма ограничения по стали-45

Замечаем, что автоматика неправильно интерпретировала данные: вместо нужных нам точек (0; 80,5) и (107,33; 0) на диаграмме использованы точки (0; 107,33) и (80,5; 0). Для изменения диаграммы и смены подписи «Ряд 1» на «Сталь-45» щелкнем правой кнопкой мыши в области диаграммы и из появившегося контекстного меню выберем пункт Выбрать данные.



Рис. Изменение ряда данных

Далее в появившемся диалоговом окне Выбор источника данных при выделенной строке «Ряд 1» нажмем кнопку Изменить. В открывшемся новом диалоговом окне, таком, как на.

Рис. 48. Изменение ряда и подписи ряда

для задания имени ряда в окне Имя ряда щелкнем по ячейке с подписью «Сталь-45», удалим значения в окне Значения Х и протащим мышь по ячейкам с первыми координатами точек построения -- В16:В17, удалим значения в окне Значения Y и протащим мышь по ячейкам со вторыми координатами точек построения -- С16:С17, нажмем кнопки ОК, закрывая все диалоговые окна. На диаграмме вместо слов «Ряд 1» появится «Сталь-45», а прямая изменит наклон. Заметим, что данная задача решается на листе Лист3 книги Excel, поэтому указание на этот лист будет предшествовать ссылкам на ячейки. Остальные прямые будем добавлять последовательно в виде новых рядов данных. Описанным выше способом вызовем диалоговое окно Выбор источника данных, и в нем нажмем кнопку Добавить. В строке Имя ряда щелкнем по ячейке с подписью «Чугун», в строке Значения Х протащим мышь по ячейкам с первыми координатами точек для построения прямой В18:В19, в строке Значения Y -- по ячейкам со вторыми координатами С18:С19. После нажатия на кнопку ОК на диаграмме появится новая прямая с нужной подписью. В диалоговом окне Выбор источника данных снова нажмем кнопку Добавить и аналогично последовательно добавим данные по бронзе, стали-3 и целевой функции. Окончательный вид диаграммы показан на.

Рис. Диаграмма ограничений по 4 видам сырья

Она, очевидно, имеет ряд недостатков. В ней единичные отрезки по осям имеют разную длину, ограничение по чугуну хочется вытянуть горизонтально до пересечения с другими прямыми. Щелкнем по области построения диаграммы и опытным путем изменим ее размеры так, чтобы единичные отрезки по осям были примерно одинаковыми, не меняя при этом размеры области диаграммы. Чтобы изменить расположение ограничения по чугуну, заменим формулу в ячейке В19 на конкретное подходящее число, например, на 100. Улучшенная диаграмма будет выглядеть примерно так, как на Рис. 51. Зная, что в задаче с ограничениями по ресурсам в качестве решения любого из ограничений выбирается полуплоскость, содержащая начало координат («нижняя» полуплоскость), легко получаем МДР. К тому же, понимая, что из себя представляет МДР, можно увидеть и точку, в которой целевая функция достигает оптимального значения.

Рис. Окончательный вид диаграммы

Далее на основе данных этой задачи с помощью инструмента «Поиск решения» можно провести поиск оптимального решения. При этом изменится положение целевой функции на диаграмме: она займет оптимальное положение.

Рис. Оптимальное положение целевой функции

И по диаграмме и по текущим значениям правых частей ограничений в таблице видно, что активными являются ограничения по стали-3 и стали-45, а пассивными -- по чугуну и бронзе. Суточные запасы чугуна можно снизить до 34,75 кг, а бронзы -- до 122 кг.

Рис. Оптимальное решение задачи в Excel

Покажем, как можно провести экономический анализ активных ограничений. Будем, например, увеличивать суточные запасы стали-45 в ячейке Е7, каждый раз после изменения заново запуская инструмент «Поиск решения».

При значении 380 кг видим, что активными стали ограничения по бронзе, стали-45 и стали-3 (Рис. 54), а границы соответствующих неравенств пересекаются в одной точке, которая и является оптимальным решением. Дальнейшее увеличение ограничения по стали-45 делает это ограничение пассивным.

Рис. Три активных ограничения

Рассмотрим более сложный пример оптимального решения и экономического анализа задачи линейного программирования с ограничением по ресурсам. Эта задача была предложена на II очном туре Всероссийской междисциплинарной олимпиады «Информационные технологии в сложных системах» по профилю «Сложные социально-экономические системы» в октябре 2010 года.

Задача. Предположим, Вы являетесь владельцем пекарни, которая специализируется на производстве сдобного печенья и бисквитов. Данные о ценах, затратах соответствующих ресурсов на 1 кг продукции
и доступных объемах запасов ресурсов приведены в таблице 18.

Таблица 18

Ресурсы	Сдоб. печ.	Бисквиты	Запасы
Мука, кг	0,58	0,3	750
Масло, кг	0,25	0,05	500
Яичный порошок, кг	0,18	0,8	700
Сахар, кг	0,1	0,5	200
Крахмал, кг	0	0,07	100
Труд, чел./дн.	0,08	0,09	120
Оборудование 1, маш./смен.	0,02	0,07	100
Оборудование 2, маш./смен.	0,07	0,08	100
Цена за 1 кг продукции, руб.	31	29

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

Решение. Подготовим данные на листе Excel, как это было описано на с. 87, и запустим инструмент «Поиск решения». Получим оптимальное значение целевой функции и активные ограничения по муке и сахару (Рис. 56). Теперь будем увеличивать запасы сахара, например:

10 и выполнять поиск решения до тех пор, пока ограничение по сахару не станет пассивным. Обнаружим, что при запасах сахара в 230 кг ограничение по сахару становится пассивным, а активными будут ограничения по муке и оборудованию 2. Текущее значение сахара при этом равно 226,378 кг. Ведем это значение в ячейку Е10 и снова запустим «Поиск решения». Видим, что сразу три ограничения становятся активными: по муке, сахару и оборудованию 2 (Рис. 57). Значит, дальнейшее увеличение запасов сахара не влияет на оптимальное значение целевой функции. Ожидаемая величина прироста выручки будет вычисляться как разность между оптимальным значением целевой функции при запасах сахара 226,378 кг и 200 кг, из которой надо вычесть сумму, потраченную на покупку дополнительного сахара:

Заметим, что по смыслу задачи значения переменных должны быть целыми. Для этого в окне Поиск решения необходимо ввести дополнительное ограничение целочисленности на значения ячеек $B$3:$C$3 (Рис. 58).



В этом случае оптимальное решение почти не будет отличаться от полученного выше, но оптимальные значения переменных в ячейках $B$3:$C$3 будут выражаться целыми числами (Рис. 59), а текущие значения ограничений по муке и по сахару будут более других близки к граничным. Этот факт говорит об активности данных ограничений.

Рис. Целочисленное оптимальное решение

Путем увеличения правой части ограничения по сахару обнаружим, что при запасах в 226,5 кг сахара активными станут три ограничения: по муке, сахару и оборудованию 2. Соответствующее решение предлагается получить самостоятельно. Значение целевой функции при этом составит 42 873 руб. Следовательно, ожидаемая величина прироста выручки будет

Итак, решение указанной задачи выглядит так: необходимо докупить 26,5 кг сахара; при этом прирост выручки составит 408 руб.

В процессе решения этой задачи удалось обойтись без графического представления данных. Но целесообразно рассмотреть и его. Построим границы МДР и целевую функцию так, как было описано на с. 93--99. Видим, что диаграмма получилась крайне неудачной; большое количество ограничений и сильно отличающиеся координаты точек пересечения с осями их границ делают ее практически не читаемой. Но в то же время, благодаря легенде (и данным в таблице как на с. 103), видим, что ограничения по маслу, крахмалу, оборудованию 1 не участвуют в ограничении МДР. Их границы можно выделить непосредственно на диаграмме и удалить клавишей Del. На диаграмме автоматически изменятся максимальные значения по осям.

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

Рис. Изменение максимальных значений по осям

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



Рис. Оптимальное решение с активными ограничениями по муке, сахару и оборудованию 2

Зная, что нужное число 226,5, введем его в ячейку Е10, запустим «Поиск решения». Оптимальное положение целевой функции с тремя активными ограничениями показано на рис. 63. На этом примере показано, как удалять с диаграммы мешающие пассивные ограничения, делать диаграмму с МДР более информативной.

5. Многокритериальная оптимизация

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

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

1. Формулировка многокритериальной задачи

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

Требуется найти значения действительных переменных x1,…, xn, при которых целевые функции

(X),…,(X)

принимают экстремальные значения при ограничениях:

,

где X -- n-мерный вектор независимых переменных x1,…, xn, -- система ограничений.

Если цели находятся в противоречии друг с другом, то не существует оптимального решения, которое удовлетворяло бы всем критериям эффективности. В этом случае вводится понятие «эффективное решение». Оно означает, что невозможно улучшить значение любой из целевых функций без ухудшения значений одной или нескольких целевых функций. Уточним введенное понятие для задачи максимизации: решение X* называется эффективным, если не существует допустимого решения , такого, что ()(X*), , и () >(X*) по крайней мере, для одного индекса j. Множество всех эффективных решений в непрерывном случае известно как эффективная граница. Эффективное решение называют также недоминируемым решением, неулучшаемым решением или решением по Парето Вильфредо Парето (1848--1923) -- итальянский социолог и экономист. (Парето-оптимальным решением).

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

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

2. Множество Парето

Напомним некоторые определения. Пусть на плоскости (или в пространстве) дано некоторое множество точек M. Точка называется внутренней точкой множества М, если существует такая окрестность этой точки, которая целиком состоит из точек данного множества. Если же в любой окрестности точки имеются точки, как принадлежащие, так и не принадлежащие множеству М, то точка называется граничной точкой множества М. Совокупность всех граничных точек данного множества М называется его границей. Иллюстрацией служит рис. 64.

Если множество М не содержит ни одной своей граничной точки, то оно называется открытым (то есть любая точка открытого множества является внутренней). Если множество М содержит все свои граничные точки, то оно называется замкнутым. В дальнейшем будут рассматриваться только замкнутые множества.