От табличной записи легко перейти к обычной записи уравнений. Для этого надо умножить элементы bkjk-й строки на соответствующие переменные, стоящие в заглавной строке (-xm+i), полученные произведения сложить и сумму приравнять xkТогда
bko*1 + bk1 (—xm+l)+ … +bks{—xm+s)+ ... + bk,n-m(—xn) =xk илиxi = bi0 -∑ bij xm+1 .
4. Критерии оптимальности
Рассмотрим последовательность решения задач линейного программирования симплекс-методом и изложим ее применительно к задаче максимизации.
1. По условию задачи составляется ее математическая модель.
2. Составленная модель преобразовывается к канонической форме. При этом может выделиться базис с начальным опорным планом.
3. Каноническая модель задачи записывается в форме симплекс-таблицы так, чтобы все свободные члены были неотрицательными. Если начальный опорный план выделен, то переходят к пункту 5.
4. Находят начальный опорный план, производя симплексные преобразования с положительными разрешающими элементами, отвечающими минимальным симплексным отношениям, и не принимая во внимание знаки элементов f-строки. Если в ходе преобразований встретится 0-строка, все элементы которой, кроме свободного члена, нули, то система ограничительных уравнений задачи несовместна. Если же встретится 0-строка, в которой, кроме свободного члена, других положительных элементов нет, то система ограничительных уравнений не имеет неотрицательных решений.
5. Найденный начальный опорный план исследуется на оптимальность:
а) если в f-строке нет отрицательных элементов (не считая свободного члена), то план оптимален. Если при этом нет и нулевых, то оптимальный план единственный; если же есть хотя бы один нулевой, то оптимальных планов бесконечное множество;
б) если в f-строке есть хотя бы один отрицательный элемент, которому соответствует столбец неположительных элементов, то f→ ;
в) если в f-строке есть хотя бы один отрицательный элемент, а в его столбце есть хотя бы один положительный, то можно перейти к новому опорному плану, более близкому к оптимальному. Для этого указанный столбец надо назначить разрешающим, по минимальному симплексному отношению найти разрешающую строку и выполнить симплексное преобразование. Полученный опорный план вновь исследовать на оптимальность. Описанный процесс повторяется до получения оптимального плана либо до установления неразрешимости задачи.
Важно заметить, что поскольку minf= — max( —f), задачу минимизации f можно формально заменить задачей максимизации функции (—f). Но можно этого и не делать. Признаком оптимальности опорного плана задачи минимизации является отсутствие положительных элементов в f-строке симплекс-таблицы, содержащей опорный план. В остальном вычислительная процедура не меняется.
В пункте 3 алгоритма предполагается, что все элементы столбца свободных членов неотрицательны. Это требование не обязательно, но если оно выполнено, то все последующие симплексные преобразования производятся только с положительными разрешающими элементами, что удобно при расчетах. Если в столбце свободных членов есть отрицательные числа, то разрешающий элемент выбирают следующим образом:
1) просматривают строку, отвечающую какому-либо отрицательному свободному члену, например t-строку, и выбирают в ней какой-либо отрицательный элемент, а соответствующий ему столбец принимают за разрешающий (предполагая, что ограничения задачи совместны);
2) составляют отношения элементов столбца свободных членов к соответствующим элементам разрешающего столбца, имеющим одинаковые знаки (симплексные отношения);
3) из симплексных отношений выбирают наименьшее. Оно и определит разрешающую строку. Пусть ею будет, например, р -строка;
4) на пересечении разрешающих столбца и строки находят разрешающий элемент. Если разрешающим оказался элемент t-строки, то после симплексного преобразования свободный член этой строки станет положительным. В противном случае на следующем шаге вновь обращаются к t-строке. Если задача разрешима, то через некоторое число шагов в столбце свободных членов не останется отрицательных элементов. Если в форму задачи линейного программирования облечена некоторая реальная производственная ситуация, то дополнительные переменные, которые приходится вводить в модель в процессе преобразования ее к канонической форме, всегда имеют определенный экономический смысл.
4.1 Признак оптимальности опорного плана
Если в симплекс-таблице, содержащей некоторый опорный план, все элементы f-строки (не считая свободного члена) неотрицательны, то этот опорный план является оптимальным.. Пусть в f-строке табл. 2.b0j> (i=1, ..., nm). В опорном плане х0, содержащемся в этой таблице, значения всех свободных переменных xm+jравны нулю и f(х0) =b00. Если же увеличивать какую-либо из свободных переменных xm+j, то, как видно из равенства (2.5), в силу неотрицательности b0jзначение f(х) начнет уменьшаться. Следовательно, при xо функция f(х) достигает наибольшей величины, а значит, х0 действительно является оптимальным опорным планом.
4.2 Возможность переход от одного опорного плана к другому
Как уже говорилось выше, суть симплекс-метода в процессе доказательства следующего признака: если в f-строке симплекс-таблицы, содержащей некоторый опорный план, есть хотя бы один отрицательный элемент (не считая свободного члена), которому соответствует столбец с хотя бы одним положительным элементом, то можно, преобразовав базис, перейти к другому опорному плану с большим значением целевой функции.
Докажем этот признак. Установим правила выбора переменных для такого преобразования начального базиса Бо с опорным планом х0 в новый базис Б1 с опорным планом х1 при котором; значение функции f увеличивается, т. е. f(xi)>f(x0). Тогда по правилу пересчета элементов из симплекс-таблицы преобразуем к новому базису, что позволит найти компоненты нового опорного плана.
Допустим, что в табл. 2.1, например, b0s<0, а среди элементов biss-го столбца есть хотя бы один положительный. Полагая в равенстве (2.5) все свободные переменные хm+j кроме xm+s, равными нулю, получаем f = boo — bosxm+s. Из этого равенства видно, что при увеличении xm+sзначение f тоже возрастает. Таким образом, при указанных в признаке условиях действительно есть возможность увеличить f(x), переходя к планам, в которых xm+s принимает положительные значения, а все остальные компоненты xm+j по-прежнему равны нулю. Покажем, что среди таких планов существует и опорный. Тем самым будет найден путь направленного преобразования базиса Бо в новый базис Б1. В самом деле, если переменная xm+s принимает положительное значение в некотором опорном плане, значит, она является в нем базисной компонентой (в опорном плане xо она была свободной компонентой и равнялась нулю). Поэтому прежний базис следует преобразовать за счет включения в него переменной xm+s. Но здесь предстоит решить два вопроса:
1) какую из переменных следует вывести из прежнего базиса, чтобы освободить место для переменной xm+s;
2) какое значение должна принимать новая базисная переменная xm+s в новом опорном плане.
Для решения поставленных вопросов допустим, что в равенствах (2.4) все xm+j, кроме xm+s, равны нулю. Тогда
xi = bio-bisxm+s (i=l, ..., m)
Из этих равенств видно, что с возрастанием xm+s значения тех базисных переменных хi для которых коэффициенты bis<0, тоже будут расти, оставаясь положительными. Значит, на отрицательные коэффициенты bis можно внимания не обращать, так как они не влияют на знак базисных переменных. Иначе обстоит дело с базисными переменными, у которых bis>0. С увеличением xm+sзначения этих переменных станут уменьшаться, и наступит момент, после которого они будут принимать отрицательные значения и перестанет выполняться условие (2.3). Этого допустить нельзя. Поэтому выясним, до какого предельного значения можно увеличивать xm+s, не нарушая условия неотрицательности базисных переменных. С этой целью выпишем из системы (2.6) те равенства, в которых bis>0. Допустим, что это касается равенств с номерами i=d,…,k,…,p:
xd=bdo— bds xm+s,
…………………..
xk=bk0- bks xm+s,
………………….
xp=bp0 – bps xm+s.
Базисные переменные хd, ..., xk, ..., xp будут оставаться неотрицательными до тех пор, пока xm+s удовлетворяет системе неравенств
bdo - bds xm+s>0, xm+s<bdo/bds