Метод единичных векторов

Выше было показано, что основная ЗЛП, ограничения которой имеют степень неопределенности р=2, может быть решена графически. Если же ЗЛП имеет степень неопределенности p>2, то применение для ее решения графического метода становится невозможным, так как в этом случае теряется геометрическая наглядность. Для решения таких ЗЛП применяются аналитические методы, из которых наиболее распространенным является симплекс-метод. Название метода определяется тем, что симплексом называется геометрический многогранник (многоугольник), который определяет область допустимых решений задачи.

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

а) найти все опорные решения;

б) вычислить значения функции цели, соответствующие этим опорным

решениям;

в) среди полученных значений функции цели выбрать наилучшее.

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

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

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

З а д а ч а. Найти решение задачи, состоящей в определении максимального значения функции

при условиях

,

,

,

.

Видим, что задача имеет пять неизвестных и три ограничения, т.е. степень неопределенности р=2. Это означает, что два неизвестных можно принять за свободные, а три – за базисные. В данной задаче на первом шаге итерации удобно, если свободными будут переменные х₄=0, х₅=0. Тогда базисными будут остальные переменные х₁; х₂; х_3. Из ограничений следует, что в таком случае они будут иметь следующие значения:

x₁ = b₁; x₂ = b₂; x₃ = b₃.

Имеем первый опорный план:

,

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

.

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

,

где вектор-столбцы Р_j имеют вид

, , , , , .

Векторы Р₁, Р₂, Р₃ – единичные векторы при переменных х₁, х₂, х₃ соответственно. Именно их в данной задаче мы приняли за базисные и не равные нулю. Векторы Р₄, Р₅ – неединичные и содержат множители при переменных х₄, х₅, которые приняты за свободные и они приравнены нулю (вспомним, что в любой вершине симплекса ряд переменных обязательно равны нулю, их количество равно степени неопределенности задачи). В результате мы приходим к формированию первого опорного плана в представленном выше виде.

Сформулируем следующие правила реализации метода:

1. Задачу линейного программирования записывают в виде основной ЗЛП (F→max, все ограничения – равенства).

2. Оценивают степень неопределенности задачи р (число неизвестных минус число ограничений).

3. Записывают вектор-столбцы Р_j множителей при переменных.

4. Определяют единичные вектор-столбцы. Их количество должно быть не менее количества ограничений.

5. Те переменные, для которых P_j – единичные вектор-столбцы, переводятся в базисные, остальные – в свободные.

6. Базисные переменные приравниваются свободным членам ограничений х_i=b_i, свободные переменные приравниваются нулю. В сумме они образуют первый опорный план.

После такой подготовки приступают к заполнению симплекс-таблицы и решению задачи.

З а д а ч а. Найти максимальное значение функции

при ограничениях

,

,

,

.

Запишем вектор-столбцы в ограничениях

, , , , , .

Предположим, что из приведенных единичными будут векторы Р₃, Р₄, Р₅. Это означает, что коэффициенты а₁₃=а₂₄=а₃₅=1, а коэффициенты а₁₄=а₁₅=а₂₃=а₂₅=а₃₃=а₃₄=0. Тогда переменные х₃, х₄, х₅ становятсябазисными,а переменные х₁, х₂ – свободными. Последние приравниваются нулю, тогда базисные переменные принимают значения х₃=b₁, x₄=b₂, x₅=b₃, т.е. мы имеем первый опорный план Х⁽¹⁾=(0, 0, b₁, b₂, b₃). Теперь необходимо заполнить симплекс-таблицу (табл.2).

Таблица 2

Симплекс-таблица задачи линейного программирования

i	Базис	Cб	Р0	C1	C2	C3	C4	C5
P1	P2	P3	P4	P5
	Р3	с3	b1	а11	а12	а13=1	а14=0	а15=0	b1/a12
	Р4	с4	b2	а21	а22	а23=0	а24=1	а25=0	b2/a22
	Р5	с5	b3	а31	а32	а33=0	а34=0	а35=1	b3/a32
	zj
	∆j			z1-c1	z2-c2	z3-c3=0	z4-c4=0	z5-c5=0

Для данной задачи табл. 2 имеет 10 столбцов и пять строк. В столбец «базис» вписываются индексы векторов-столбцов тех переменных, которые в данный момент являются базисными. В нашем случае это Р₃, Р₄, Р₅. В столбец «С_б» вносятся значения ценовых множителей (со своим знаком), которые содержатся в функции цели при соответствующей базисной переменной. В столбец Р₀ записываются значения базисных переменных для рассматриваемого опорного плана (в первой симплекс-таблице это свободные члены в уравнениях ограничений). В последующие столбцы записываются значения соответствующих вектор-столбцов. Видим, что только по свободным переменным в столбцах Р_j (j=1…5) есть конкретные числа, а по столбцам при базисных переменных – только по одной единице, в остальных клетках – нули.

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

1. По столбцам Р₀ – Р₅ рассчитывается сумма произведений стоящей в соответствующей клетке цифры на ценовой коэффициент с, стоящий при i -ой переменной из базиса (в данном случае i=1…3). Эта сумма обозначена через индекс z_j.

2. По столбцам Р₁ – Р₅ определяют разность между суммами z_j и ценовым коэффициентом c_j по каждой переменной и эта сумма записывается в строке 5 под индексом ∆_j.

3. После выполнения предыдущих операций проводят анализ данного опорного плана. Если в результате расчетов все ∆_j ≥ 0, то данный опорный план является оптимальным. В противном случае следует искать другой опорный план.

4. Если какой-либо ∆_j меньше нуля, то данный столбец называется разрешающим столбцом. Это означает, что переменная при данном вектор-столбце должна из свободной перейти в базисную. Если столбцов с отрицательными ∆_j больше одного, то выбирают тот, в котором абсолютное значение ∆_j максимально (по базисным переменным ∆_j обязательно будут равны нулю).

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

Если в результате первой итерации установлено, что задача может иметь другой опорный план, происходит переход к следующему опорному плану. Он заключается в том, что определяется переменная, которая должна быть переведена из свободной в базисную. Такая переменная определяется по минимальному (с учетом знака) значению ∆_j (см. пункт 4). Если, например, таковой окажется ∆₂ ≤ 0 → min, то это означает, что вторая переменная должна быть переведена из свободных в базисную. Остается установить, взамен какой переменная х₂ должна быть введена в базис.

Для этого надо выполнить дополнительные расчеты фактора t по каждой базисной переменной. Он определяется путем деления значения данной переменной (находится в столбце Р₀)на соответствующий для данной переменной коэффициент а_ij из разрешающего столбца (принимаются во внимание только положительные коэффициенты). Результаты расчетов записываются в столбец 10. Из полученного набора t_i выбирается минимальное значение. Предположим, что t₂=min. Это означает, что переменная х₄ должна быть выведена из базисных и переведена в свободные (т.е. х₄=0), а на ее место необходимо поместить переменную х₂ ≠ 0. Тогда очередной опорный план будем искать в виде Х⁽²⁾=(0, х₂, х₃, 0, х₅).

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

Очередная симплекс-таблица имеет прежнюю форму, но другое содержание. Прежде всего в новой таблице заполняется разрешающая строка, т.е. в данном случае вторая, где будет стоять новый базис. Для этого все элементы старой строки (Р₀ – Р₅) делят на величину разрешающего элемента (в данном случае на а₂₂), при этом в столбец «базис» вписывается обозначение базиса новой переменной (Р₄ заменяется на Р₂), в третий столбец «С_б» вписывается из функции цели величина коэффициента с₂. Элементы остальных строк (по векторам Р₀ – Р₅) в новой таблице вычисляют по правилу треугольника. Оно заключается в следующем (рис.4).

Имеются:

1) две строки - преобразованная с новой базисной переменной (строка нового базиса в новой симплекс-таблице, рис.4), и преобразуемая строка одной из старых базисных переменных (в старой симплекс-таблице);

Рис.4. К обоснованию “правила треугольника”

2) два столбца – столбец (например, j=1), по которому происходит замена элементов, и разрешающий столбец j.

Заменяют элемент а₁₁ в первой строке на новое его содержание А₁₁:

,

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

В новой симплекс-таблице проводят расчеты z_j, ∆_j и делают заключение о новом опорном плане. Если подтверждается его оптимальность, то значения базовых переменных в оптимальном плане будут находиться в столбце “ Р₀ “, а свободные переменные будут иметь нулевое значение. По этим данным рассчитывают значение функции цели, хотя эта цифра будет уже находиться в таблице в ячейке на пересечении столбца “ Р₀ “ и строки z_j. Рассмотрим на примере практическую реализацию описанных выше процедур, а также проясним физический смысл некоторых параметров и процедур.

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

Таблица 3

Технологическая программа производства

На основании вышерассмотренных задач (в частности, задачи 1) составим математическую модель ЗЛП в стандартной форме: найти максимальное значение функции при ограничениях

,

,

.

По своему экономическому содержанию переменные могут принимать только неотрицательные значения:

.

Запишем эту задачу в форме основной ЗЛП. Для этого перейдем от ограничений-неравенств к ограничениям-равенствам. Введем три дополнительные переменные, в результате чего ограничения запишутся в виде системы уравнений:

,

,

.

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

,

где , , , , , , .

Поскольку среди векторов Р_j (j=1…6) при трех ограничениях имеются три единичных вектора, для данной задачи можно непосредственно записать опорный план. Таковым является план . Иначе говоря, х₁=х₂=х₃=0 – свободные переменные, х₄=360, х₅=192, х₆=180 - базисные переменные. Последние образуют базис трехмерного векторного пространства, что делает решение задачи графическим методом невозможным.

Составляем симплекс-таблицу для первой итерации, подсчитываем z_j; ∆_j; t_i и проверяем исходный план на оптимальность.

Таблица 4

Первая симплекс-таблица к задаче 5

Прежде всего определяем разрешающий столбец. Так как в строке ∆_j есть три отрицательных числа, то проверяемый план не будет оптимальным. Минимальным из них является ∆_j = -16, следовательно, разрешающим будет столбец 7. Это означает, что переменную х₃ следует перевести из свободных в базисные. Все элементы вектор-столбца Р₃ положительные, поэтому рассчитываем t_i:

, , .

Минимальное значение фактора t приходится на базис Р₅. Это означает, что переменную х₅ следует перевести из базисных в свободные, а на ее место поместить переменную х₃. Рассмотрим некоторые аспекты содержания таблицы, которые позволяют конкретизировать физический смысл представленных в ней величин.

Как видно из табл.4, значения всех основных переменных х₁, х₂, х₃ равны нулю (в первом опорном плане это свободные переменные), а дополнительные переменные принимают свои значения в соответствии с ограничениями задачи. Такие значения переменных отвечают “плану”, при котором ничего не производится, сырьевые материалы не используются и значение целевой функции будет нулевым (в таблице z=0 по четвертому столбцу), т.е. выручка от производственной деятельности отсутствует. Этот план, конечно, не является оптимальным. Это видно и из строки 5, так как в ней имеется три отрицательных числа: ∆₁ = - 9, ∆₂ = - 10, ∆₃ = - 16. Отрицательные числа не только свидетельствуют о возможности увеличения общей стоимости производимой продукции, но и показывают, насколько увеличится эта сумма при введении в план единицы того или иного вида продукции. Так, число -9 означает, что при включении в план производства одного изделия А произойдет увеличение доходной части на 9 руб. Очевидно, что наиболее целесообразно ввести в план изделие С, так как при этом доходная часть будет увеличиваться наиболее динамично (на 16 руб на каждое изделие). Именно этим объясняется решение ввести в базис ту переменную, для которой │∆j│=max.

Находя значения фактора t, получают частное от деления “ресурс/ед.затраты”, т.е. это количество j-го изделия, которое можно было бы изготовить, если весь объем данного ресурса потратить только на это изделие. Например,

означает, что, если мы введем в план производства изделие С (т.е. в базис вводится переменная х₃), то всего запаса сырьевых материалов первого типа у нас хватит на 30 изделий. Расчет

означает, что по второму ресурсу мы могли бы изготовить изделий типа С уже не 30, а всего 24. Соответственно, используя только третий тип ресурса, можно изготовить уже 60 изделий типа С. Становится ясно, сколько максимум изделий типа С можно позволить выпустить – это 24 изделия. В противном случае у нас не хватит второго ресурса. Следовательно, надо в план включать изделие С и в количестве не более 24, т.е. выводить из плана базисный вектор Р₅ и принадлежащие ему ресурсы передавать изделию С, а это означает: переменная х₃ вводится в базис взамен переменной х₅, выводимой в свободные. В результате имеем следующий опорный план

.

Составим новую симплекс-таблицу, учитывая, что разрешающий столбец – столбец под номером 7, разрешающая строка – строка под номером 2, разрешающий элемент – число 8, лежащее в клетке на пересечении этих строки и столбца.

Таблица 5

Вторая симплекс-таблица к задаче 5

В результате конкретизировали второй опорный план:

,

т.е. из реальных изделий предполагается выпуск только изделия типа С в объеме 24 шт. Очевидно, что и этот план также неоптимален: в строке значений ∆_j есть одно отрицательное значение, а именно ∆₂=-2 (т.е. столбец 6 - разрешающий). Значит, в новом плане надо переменную х₂ перевести в базис. Все элементы старого базиса Р₂ - неотрицательные числа, поэтому по всем строкам (1,2,3) рассчитаны значения фактора t. Минимальное значение t₁=8 означает, что из базиса должна быть удалена переменная х₄ (т.е. строка 1 - разрешающая строка, тогда разрешающий элемент равен 9) и весь освобождающийся объем сырьевого материала первого вида передается на изготовление второго изделия в объеме 8 шт. Тогда на третьем шаге итерации будем искать план в виде:

.

В табл. 6 представлены результаты пересчета симплекс-таблицы на третьем шаге итерации. Так как все ∆_j≥ 0, то мы имеем оптимальный план:

.

Функция цели приняла значение F_max=400 (расположено в ячейке на пересечении четвертой строки и четвертого столбца).

Таблица 6

Третья симплекс-таблица к задаче 5

Результаты показывают, что оптимальный план производства не должен предусматривать изготовление изделия вида А (причина этого рассматривается ниже), изделий вида В надо выпустить в объеме 8 шт, а изделий вида С – в количестве 20 шт. Полученное значение х₆=96 указывает на то, что при анализируемом плане производства будет недоиспользован третий вид сырьевых материалов в объеме 96 ед. Действительно, если подставить значения переменных в первичные ограничения по ресурсам, то получим:

,

,

.

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

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

Таблица 7

Обобщенная симплекс-таблица к задаче 5

З а д а ч а 6. Найти максимум функции при условиях

,

,

,

.

Р е ш е н и е. Систему уравнений задачи запишем в векторной форме:

,

где , , , , , , .

Так как при трех ограничениях имеем три единичных вектора (Р₃, Р₄, Р₆), можем сформировать первый опорный план

,

в котором базисные переменные примут значения: х₃=20, х₄=24, х₆=18. Составим симплекс-таблицу 8 и все дальнейшие расчеты запишем в нее.

На первом шаге итерации видим, что исследуемый опорный план не является оптимальным и он может быть улучшен. Разрешающий столбец (9) и разрешающая строка (2) определяют, что в базис надо ввести х₅ взамен выводимого в свободные х₄ и следующий опорный план будем искать в виде:

Таблица 8

Симплекс-таблица к задаче 6

.

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