Как определить разрешающий элемент в симплекс таблице. Метод Гаусса-Жордана
Рассмотрим подробно, как производится пересчет симплекс-таблиц (на примере одной итерации). Пусть имеется симплекс-таблица представленная на Рис.1 . Решается задача максимизации целевой функции. Разрешающий столбец соответствует переменной x 2 , а разрешающая строка переменной x 3 (красные числа), на их пересечении находится разрешающий элемент (клетка с серым фоном). Первое, что нам необходимо сделать - это заменить. Разрешающая строка показывает, какая переменная должна быть выведена из базиса (в нашем случае x 3 ), а разрешающий столбец показывает какая переменная должна войти в базис (в нашем случае x 2 ). На Рис.2 факт замены акцентирован синей линией.
Теперь пересчитаем элементы стоящие в разрешающей строке. Для этого просто разделим каждый из них на разрешающий элемент (в нашем примере 4 ). А все элементы разрешающего столбца обнулим, кроме элемента стоящего в разрешающей строке. (Смотри Рис.2 )
Рисунок 1
Остальные ячейки таблицы (кроме столбца "Отношение") пересчитываются по так называемому правилу прямоугольника
, смысл которого
проще всего понять на примере. Пусть нужно пересчитать элемент обведенный на Рис.1
красным контуром. Мысленно проводим от него
вертикальную и горизонтальную линии до пересечения, с разрешающей строкой и разрешающим столбцом. Элементы стоящие в местах пересечения
обведены синими контурами (Смотри Рис.1
). Новое значение "красного" элемента будет равно нынешнему значению элемента минус
произведение "синих" деленное на разрешающий ("серый") элемент (Смотри Рис.1
). То есть:
18 - (64 * -1) / 4 = 34
, здесь знаком "*
" показана операция умножения.
Записываем новое значение на прежнее место (Смотри Рис.2
красный контур).
Рисунок 2
Пользуясь данным правилом, заполняем все пустые элементы таблицы (кроме столбца "Отношение") Смотри Рис.3 . После этого определим новый разрешающий столбец. Для этого проанализируем строку "Q" и так как наша задача на максимум, то найдем в ней максимальный положительный элемент , он и определит разрешающий столбец. В нашем случае это 3/2 . Все элементы разрешающего столбца показаны красным шрифтом (Смотри Рис.3 ). Если после очередной итерации в строке "Q" не окажется положительных элементов - это значит что оптимальное решение достигнуто, итерации прекращаются. Если бы наша задача была на минимум, то разрешающий столбец определялся бы по минимальному отрицательному элементу, и если после очередной итерации в строке "Q" не окажется отрицательных элементов, значит достигнуто оптимальное решение.
Рисунок 3
Теперь заполним столбец "Отношение". Для этого нужно соответствующий (стоящий в той же строке) элемент столбца "Решение" разделить на соответствующий элемент разрешающего столбца (Смотри Рис.3 ). Обратите внимание , что данная операция проводится только для положительных элементов разрешающего столбца и строка "Q" в данной операции не участвует. Если после некоторой итерации в разрешающем столбце не окажется положительных элементов, то данная задача неразрешима ввиду неограниченности целевой функции, итерации прекращаются.
После заполнения столбца "Отношение" определим новую разрешающую строку. Она определяется минимальным элементом из столбца "Отношение". В нашем случае это 32 , все элементы разрешающей строки показаны красным шрифтом (Смотри Рис.3 ). На этом очередная итерация заканчивается, на следующей итерации переменная x 2 будет выведена из базиса (об этом нам говорит новая разрешающая строка), ее место займет переменная x 1 (об этом нам говорит новый разрешающий столбец) и все вычисления повторятся снова.
Читайте также:
|
Теорема (о выборе разрешающего элемента)
Если в нескольких столбцах z-ой строке есть отрицательные элементы, то разрешающим столбцом нужно выбрать тот столбец у которого максимально произведение абсолютного значения коэффициента в z-ой строке и минимально симплексное отношение данном столбце.
Доказательство:
Пусть разрешающим будет элемент . В результате шага модифицированных жордановых исключений свободным членом в z-строке будет число , равное .Поскольку и ,скобка в этом выражении всегда будет положительной. А так как значение функционала всегда равно свободному члену, эта скобка представляет собой тот добавок к функционалу, который получается в результате сделанного шага.
Чем большее приращение будет получать функционал на каждом шаге, тем меньше потребуется шагов (т.е. вычислений) для достижения оптиума. Величина этого приращения зависит от абсолютной величины коэффициента и от величины наименьшего симплексного отношения . То есть разрешающим столбцом будет столбец, у которого максимально это произведение.
Пример: линейное программирование:
Найдем максимум функции
при ограничениях
Решение: составим жорданову таблицу.
Поскольку в ней свободные члены положительны, план является опорным. Однако он не оптимален, так как коэффициенты z-строки отрицательны. Выбираем из них тот, у которого наибольшее произведение абсолютной величины и наименьшее симплексное отношение. Третий столбец считаем разрешающим, так как он имеет наибольшую абсолютную величину 8 и симплексные отношения: соответственно ( , поэтому элемент 1 в третьим столбце будет разрешающим). Делаем шаг модифицированных жордановых исключений и приходим к следующей таблице.
Судя по коэффициентам z-строки, в полученной таблице оптимальное решение не достигнуто. Берём второй столбец с отрицательным коэффициентом в z-строке за разрешающий (разрешающей строкой может быть только первая). С найденным элементом 5 делаем следующий шаг.
В z-строке все коэффициенты положительны, план, получаемый приравниванием верхних переменных нулю, а боковых – свободным членам, оптимален. Выписываем из таблицы значения основных неизвестных: Максимальное значение функционала считаем в последней клетке таблицы:
В окончательной таблице все определители неотрицательны. Это говорит о том, что при значениях неизвестных функционал достигает максимума
Обычно предполагается, что на множестве планов задачи нет точек, в которых знаменатель целевой функции равен нулю. Без ограничения общности, можно считать, что .
В задаче дробно-линейного программирования экстремум целевой функции достигается в вершине многогранника решений. Это сходство с линейным программированием позволяет решать дробно-линейные задачи методом Штифеля.
Вычисления оформляются в виде жордановых таблиц. При этом для функционала отводятся две нижние строки: в первую из них записываем коэффициенты числителя, а во вторую – знаменателя. Исходной задаче соответствует таблица 1:
| –x 1 | –x 2 | … | –x j | … | –x n | ||
| y 1 | a 11 | a 12 | … | a 1 j | … | a 1 n | a 1 |
| … | ……………………………………… | … | |||||
| y i | a i 1 | a i 2 | … | a ij | … | a in | a i |
| … | ……………………………………… | … | |||||
| y m | a m 1 | a m 2 | … | a mj | … | a mn | a m |
| z 1 | –p 1 | –p 2 | … | –p j | … | –p n | |
| z 2 | –q 1 | –q 2 | … | –q j | … | –q n |
Через y i обозначаются разности между правыми и левыми частями системы ограничений:
y i = a i – a i 1 x 1 – a i 2 x 2 – a i 3 x 3 – … – a in x n ³ 0.
Свободными переменными мы будем называть переменные, расположенные в верхней заглавной строке жордановой таблицы. Придавая свободным переменным нулевые значения, мы получим исходное базисное решение: . Данный вектор не может являться опорным планом, т.к. знаменатель целевого функционала на нем равен нулю (z 2 = 0). Поэтому среди свободных членов системы ограничений a 1 ,…, a m обязательно есть отрицательные числа (иначе базисное решение было бы опорным планом).
Шагами модифицированных жордановых исключений, точно так же, как при решении задачи линейного программирования (см. ), отыскиваем первоначальный план задачи. В результате k шагов мы приходим к таблице 2:
| –y 1 | … | –x j | … | –x n | ||
| x 1 | b 11 | … | b 1 j | … | b 1 n | b 1 |
| .… | ……………………………………… | |||||
| y i | b i 1 | … | b ij | … | b in | b i |
| …. | ……………………………………. | |||||
| y m | b m 1 | … | b mj | … | b mn | b m |
| z 1 | f 1 | … | f j | … | f n | F |
| z 2 | g 1 | … | g j | … | g n | G |
В таблице 2 все свободные члены b i неотрицательны, что обеспечивает неотрицательность базисных переменных x 1 ,…, y m . Кроме того (в силу положительности знаменателя целевой функции z 2 на множестве опорных планов). Первоначальным опорным планом является вектор с координатами . Значение целевой функции на первоначальном опорном плане равно .
Заметим, что если на одном из шагов жордановых исключений какой-либо из свободных членов b i окажется отрицательным, а все остальные элементы i -й строки будут неотрицательными, то задача не будет иметь решения из-за отсутствия планов.
Проследим за тем, как меняется целевая функция при переходе от одного опорного плана задачи к другому. Оказывается, знак разности между новым и старым значениями функции совпадает со знаком определителя . Если. Т.к. многогранник решений содержит лишь конечное число опорных планов, то за конечное число шагов мы придем к оптимальному опорному плану.
Этому процессу может помешать только неограниченность многогранника решений. В этом случае целевая функция может иметь так называемый асимптотический экстремум (в данном случае – максимум). Асимптотическим максимумом задачи дробно-линейного программирования называется точная верхняя грань целевой функции на множестве планов, которая не достигается ни на одном из планов. В том случае, когда задача имеет асимптотический максимум, в области планов всегда можно найти такой план (не опорный), на котором целевая функция принимает значение сколь угодно близкое к асимптотическому максимуму.
Метод Штифеля позволяет находить не только максимум, но и асимптотический максимум задачи дробно-линейного программирования. Рассмотрим более подробно переход от плана к плану и выясним. Выбирая разрешающий элемент в j -м столбце, мы должны руководствоваться принципом минимального симплексного отношения. Т.е. разрешающий элемент в j -м столбце должен попасть в ту строку, для которой симплексное отношение положительно и минимально.
Т.к. после нахождения первоначального опорного плана все правые части b i стали неотрицательными, то разрешающим элементом j -го столбца может быть один из его положительных элементов (). Если на каждом шаге этапа поиска оптимального опорного плана в выбранном разрешающем столбце присутствует (хотя бы один) положительный элемент , то такая задача имеет максимум (возможно, что не один).
Однако, если на одном из шагов некоторая оценка меньше нуля, и при этом все элементы j -го столбца . Тогда в данном столбце, руководствуясь принципом минимального симплексного отношения, разрешающий элемент выбирать нельзя. Увеличивая значения свободной переменной x j от 0 и до (см. Табл. 2), мы все время остаемся в области планов. Это связано с тем, что увеличение переменной x j не вызывает изменения знака на минус ни у одной из базисных переменных.
Обозначим через М предел, к которому, монотонно возрастая, стремится целевая функция при : . Это число является асимптотическим максимумом.
| 2 |
Один из методов решения оптимизационных задач (как правило связанных с нахождением минимума или максимума ) линейного программирования называется . Симплекс-метод включает в себя целую группу алгоритмов и способов решения задач линейного программирования. Один из таких способов, предусматривающий запись исходных данных и их пересчет в специальной таблице, носит наименование табличного симплекс-метода .
Рассмотрим алгоритм табличного симплекс-метода на примере решения производственной задачи , которая сводится к нахождению производственного плана обеспечивающего максимальную прибыль.
Исходные данные задачи на симплекс-метод
Предприятие выпускает 4 вида изделий, обрабатывая их на 3-х станках.
Нормы времени (мин./шт.) на обработку изделий на станках, заданы матрицей A:
Фонд времени работы станков (мин.) задан в матрице B:
Прибыль от продажи каждой единицы изделия (руб./шт.) задана матрицей C:
Цель производственной задачи
Составить такой план производства, при котором прибыль предприятия будет максимальной.
Решение задачи табличным симплекс-методом
(1) Обозначим X1, X2, X3, X4 планируемое количество изделий каждого вида. Тогда искомый план: (X1, X2, X3, X4 )
(2) Запишем ограничения плана в виде системы уравнений:
(3) Тогда целевая прибыль:
То есть прибыль от выполнения производственного плана должна быть максимальной.
(4) Для решения получившейся задачи на условный экстремум, заменим систему неравенств системой линейных уравнений путем ввода в нее дополнительных неотрицательных переменных (X5, X6, X7 ).
(5) Примем следующий опорный план :
X1 = 0, X2 = 0, X3 = 0, X4 = 0, X5 = 252, X6 = 144, X7 = 80
(6) Занесем данные в симплекс-таблицу :
В последнюю строку заносим коэффициенты при целевой функции и само ее значение с обратным знаком;
(7) Выбираем в последней строке наибольшее (по модулю ) отрицательное число.
Вычислим b = Н / Элементы_выбранного_столбца
Среди вычисленных значений b выбираем наименьшее .
Пересечение выбранных столбца и строки даст нам разрешающий элемент. Меняем базис на переменную соответствующую разрешающему элементу (X5 на X1 ).
- Сам разрешающий элемент обращается в 1.
- Для элементов разрешающей строки – a ij (*) = a ij / РЭ (то есть каждый элемент делим на значение разрешающего элемента и получаем новые данные ).
- Для элементов разрешающего столбца – они просто обнуляются.
- Остальные элементы таблицы пересчитываем по правилу прямоугольника.
a ij (*) = a ij – (A * B / РЭ)
Как видите, мы берем текущую пересчитываемую ячейку и ячейку с разрешающим элементом. Они образуют противоположные углы прямоугольника. Далее перемножаем значения из ячеек 2-х других углов этого прямоугольника. Это произведение (A * B ) делим на разрешающий элемент (РЭ ). И вычитаем из текущей пересчитываемой ячейки (a ij ) то, что получилось. Получаем новое значение - a ij (*) .
(9) Вновь проверяем последнюю строку (c ) на наличие отрицательных чисел . Если их нет – оптимальный план найден, переходим к последнему этапу решения задачи. Если есть – план еще не оптимален, и симплекс-таблицу вновь нужно пересчитать.
Так как у нас в последней строке снова имеются отрицательные числа, начинаем новую итерацию вычислений.
(10) Так как в последней строке нет отрицательных элементов, это означает, что нами найден оптимальный план производства! А именно: выпускать мы будем те изделия, которые перешли в колонку «Базис» - X1 и X2. Прибыль от производства каждой единицы продукции нам известна (матрица C ). Осталось перемножить найденные объемы выпуска изделий 1 и 2 с прибылью на 1 шт., получим итоговую (максимальную! ) прибыль при данном плане производства.
ОТВЕТ:
X1 = 32 шт., X2 = 20 шт., X3 = 0 шт., X4 = 0 шт.
P = 48 * 32 + 33 * 20 = 2 196 руб.
Галяутдинов Р.Р.
© Копирование материала допустимо только при указании прямой гиперссылки на
При графическом методе решения задач ЛП мы фактически из множества вершин, принадлежащих границе множества решений системы неравенств, выбрали такую вершину, в которой значение целевой функции достигало максимума (минимума). В случае двух переменных этот метод совершенно нагляден и позволяет быстро находить решение задачи.
Если в задаче три и более переменных, а в реальных экономических задачах как раз такая ситуация, трудно представить наглядно область решений системы ограничений. Такие задачи решаются с помощью симплекс-метода или методом последовательных улучшений. Идея метода проста и заключается в следующем.
По определенному правилу находится первоначальный опорный план (некоторая вершина области ограничений). Проверяется, является ли план оптимальным. Если да, то задача решена. Если нет, то переходим к другому улучшенному плану - к другой вершине. значение целевой функции на этом плане (в этой вершине) заведомо лучше, чем в предыдущей. Алгоритм перехода осуществляется с помощью некоторого вычислительного шага, который удобно записывать в виде таблиц, называемых симплекс-таблицами . Так как вершин конечное число, то за конечное число шагов мы приходим к оптимальному решению.
Рассмотрим симплексный метод на конкретном примере задачи о составлении плана.
Еще раз заметим, что симплекс-метод применим для решения канонических задач ЛП, приведенных к специальному виду, т. е. имеющих базис, положительные правые части и целевую функцию, выраженную через небазисные переменные. Если задача не приведена к специальному виду, то нужны дополнительные шаги, о которых мы поговорим позже.
Рассмотрим задачу о плане производства, предварительно построив модель и приведя ее к специальному виду.
Задача.
Для изготовления изделий А и В склад может отпустить сырья не более 80 единиц. Причем на изготовление изделия А расходуется две единицы, а изделия В - одна единица сырья. Требуется спланировать производство так, чтобы была обеспечена наибольшая прибыль, если изделий А требуется изготовить не более 50 шт., а изделий В - не более 40 шт. Причем, прибыль от реализации одного изделия А - 5 руб., а от В - 3 руб.
Построим математическую модель, обозначив за х 1 количество изделий А в плане, за х 2 - количество изделий В . тогда система ограничений будет выглядеть следующим образом:
Приведем задачу к каноническому виду, введя дополнительные переменные:
(3.10)
F = -5x 1 - 3x 2 → min.
Эта задача имеет специальный вид (с базисом, правые части неотрицательны). Ее можно решить симплекс-методом.
I этап. Запись задачи в симплекс-таблицу. Между системой ограничений задачи (3.10) и симплекс-таблицей взаимно-однозначное соответствие. Строчек в таблице столько, сколько равенств в системе ограничений, а столбцов - столько, сколько свободных переменных. Базисные переменные заполняют первый столбец, свободные - верхнюю строку таблицы. Нижняя строка называется индексной, в ней записываются коэффициенты при переменных в целевой функции. В правом нижнем углу первоначально записывается 0, если в функции нет свободного члена; если есть, то записываем его с противоположным знаком. На этом месте (в правом нижнем углу) будет значение целевой функции, которое при переходе от одной таблицы к другой должно увеличиваться по модулю. Итак, нашей системе ограничений соответствует таблица 3.4, и можно переходить ко II этапу решения.
Таблица 3.4
|
базисные |
свободные |
||
II этап . Проверка опорного плана на оптимальность.
Данной таблице 3.4 соответствует следующий опорный план:
(х 1 , х 2 , х 3 , х 4 , х 5) = (0, 0, 50, 40, 80).
Свободные переменные х 1 , х 2 равны 0; х 1 = 0, х 2 = 0. А базисные переменные х 3 , х 4 , х 5 принимают значения х 3 = 50, х 4 = 40, х 5 = 80 - из столбца свободных членов. Значение целевой функции:
-F = - 5х 1 - 3х 2 = -5 · 0 - 3 · 0 = 0.
Наша задача - проверить, является ли данный опорный план оптимальным. для этого необходимо просмотреть индексную строку - строку целевой функции F .
Возможны различные ситуации.
1. В индексной F -строке нет отрицательных элементов. Значит, план оптимален, можно выписать решение задачи. Целевая функция достигла своего оптимального значения, равного числу, стоящему в правом нижнем углу, взятому с противоположным знаком. Переходим к IV этапу.
2. В индексной строке есть хотя бы один отрицательный элемент, в столбце которого нет положительных. Тогда делаем вывод о том, что целевая функция F →∞ неограниченно убывает.
3. В индексной строке есть отрицательный элемент, в столбце которого есть хотя бы один положительный. Тогда переходим к следующему III этапу. пересчитываем таблицу, улучшая опорный план.
III этап . Улучшение опорного плана.
Из отрицательных элементов индексной F -строки выберем наибольший по модулю, назовем соответствующий ему столбец разрешающим и пометим "".
Чтобы выбрать разрешающую строку, необходимо вычислить отношения элементов столбца свободных членов только к положительным элементам разрешающего столбца. Выбрать из полученных отношений минимальное. Соответствующий элемент, на котором достигается минимум, называется разрешающим. Будем выделять его квадратом.
В нашем примере, 
, элемент 2 - разрешающий. Строка, соответствующая этому элементу, тоже называется разрешающей (табл. 3.5).
Таблица 3.5
Выбрав разрешающий элемент, делаем перечет таблицы по правилам:
1. В новой таблице таких же размеров, что и ранее, переменные разрешающей строки и столбца меняются местами, что соответствует переходу к новому базису. В нашем примере: х 1 входит в базис, вместо х 5 , которая выходит из базиса и теперь свободная (табл. 3.6).
Таблица 3.6
|
базисные |
свободные |
||
2. На месте разрешающего элемента 2 записываем обратное ему число .
3. Элементы разрешающей строки делим на разрешающий элемент.
4. Элементы разрешающего столбца делим на разрешающий элемент и записываем с противоположным знаком.
5. Чтобы заполнить оставшиеся элементы таблицы 3.6, осуществляем пересчет по правилу прямоугольника. Пусть мы хотим посчитать элемент, стоящий на месте 50.
Соединяем этот элемент мысленно с разрешающим, находим произведение, вычитаем произведение элементов, находящихся на другой диагонали получившегося прямоугольника. Разность делим на разрешающий элемент.
Итак, . Записываем 10 на место, где было 50. Аналогично:
, 
, , 
.
Таблица 3.7
Имеем новую таблицу 3.7, базисными переменными теперь являются переменные {x 3 ,x 4 ,x 1 }. Значение целевой функции стало равно -200, т. е. уменьшилось. Чтобы проверить данное базисное решение на оптимальность надо перейти опять ко II этапу. Процесс, очевидно, конечен, критерием остановки являются пункт 1 и 2 II этапа.
Доведем решение задачи до конца. Для этого проверим индексную строку и, увидев в ней отрицательный элемент , назовем соответствующий ему столбец разрешающим и, согласно III этапу, пересчитаем таблицу. Составив отношения и выбрав среди них минимальное = 40, определили разрешающий элемент 1. теперь пересчет осуществляем согласно правилам 2-5.
Таблица 3.8
|
базисные |
свободные |
||
|
х 3 = 30, х 2 = 40, х 1 = 20. Свободные переменные равны 0, х 5 = 0, х 4 = 0. Целевая функция принимает значение последнего элемента столбца свободных членов с противоположным знаком: -F = -220 F = 220, в нашем примере функция исследовалась на min, и первоначально F max, поэтому фактически знак поменялся дважды. Итак, х * = (20, 40, 30, 0, 0), F * = 220. Ответ к задаче: Необходимо в план выпуска включить 20 изделий типа А , 40 изделий типа В, при этом прибыль будет максимальной и будет равна 220 руб. В конце этого параграфа приведем блок-схему алгоритма симплекс-метода, которая в точности повторяет этапы, но, возможно, для некоторых читателей будет более удобна в пользовании, т. к. стрелочки указывают четкую направленность действий. Ссылки над прямоугольниками в блок-схеме показывают, к какому этапу или подпункту относится соответствующая группа преобразований. правило нахождения первоначального опорного плана будет сформулировано в пункте 3.7.
Вопросы для самоконтроля 1. Как строится симплекс-таблица? 2. Как отражается смена базиса в таблице? 3. Сформулируйте критерий остановки симплекс-метода. 4. Как организовать пересчет таблицы? 5. С какой строки удобно начинать пересчет таблицы? |
Для разрешения выполнения апплета на вашем компьютере надо сделать следующее - нажать кнопку Пуск>Панельуправления>Программы>Java. В окне Java Control Panel выбираем вкладку Security (Безопастность) нажимаем кнопку Edit Site List, кнопку add и вставляем в свободное поле путь к этой страницы из адресной строки браузера. Далее нажимаем кнопки ОК, после этого перезагружаем компьютер.
Для запуска апплета нажмите на кнопку "Simplex". Если над этой строкой не видна кнопка "Simplex", то на компьютере не установлена Java.
После нажатия на кнопку « Simplex » выводится первое окно для ввода числа переменных и числа ограничений задачи на симплекс-метод.
После нажатия на кнопку « ok » выводится окно для ввода остальных данных задачи на симплекс-метод: режима отображения (десятичные дроби или обыкновенные), тип критерия задачи min или max , ввод коэффициентов целевой функции и коэффициентов системы ограничений со знаками « ≤ », « ≥ » или « = », ограничения вида х i ≥ 0 вводить не надо, их учитывает в своем алгоритме.
После нажатия на кнопку «Решить» выводится окно с результатами решения задачи на . Окно состоит из двух частей, в верхней части находится текстовое поле, содержащее описание приведения исходной задачи к канонической форме, которая используется для составления первой симплекс-таблицы. В нижней части окна в панели со вкладками расположены симплекс-таблицы каждой итерации с небольшим текстовым полем внизу с указанием разрешающего столбца, разрешающей строки и другой информации, что делает программу обучающей. Во вкладке с оптимальной (последней) таблицей в текстовом поле приведено полученное оптимальное решение задачи.
Замеченные ошибки и комментарии по работе апплета присылайте на [email protected] или звоните 8 962 700 77 06, за что мы будем Вам очень благодарны.
Программа М-метод
Программа для решения транспортной задачи
Здесь приведено ручное (не апплетом) решение двух задач симплекс-методом (аналогичным решению апплетом) с подробными объяснениями для того, чтобы понять алгоритм решения задач. Первая задача содержит знаки неравенства только " ≤ " (задача с начальным базисом), вторая может содержить знаки " ≥ ", " ≤ " или " = " (задача с искусственным базисом), они решаются по разному.
Симплекс-метод, решение задачи с начальным базисом
1)Симплекс-метод для задачи с начальным базисом (все знаки неравенств-ограничений " ≤ ").
Запишем задачу в канонической форме, т.е. ограничения-неравенства перепишем в виде равенств, добавляя балансовые переменные:
Эта система является системой с базисом (базис s 1 , s 2 , s 3 , каждая из них входит только в одно уравнение системы с коэффициентом 1), x 1 и x 2 - свободные переменные. Задачи, при решении которых применяется симплекс-метод, должны обладать следующими двумя свойствами:
-система ограничений должна быть системой уравнений с базисом;
-свободные члены всех уравнений в системе должны быть неотрицательны.
Полученная система - система с базисом и ее свободные члены неотрицательны, поэтому можно применить симплекс-метод. Составим первую симплекс-таблицу (Итерация 0), т.е. таблицу коэффициентов целевой функции и системы уравнений при соответствующих переменных. Здесь "БП" означает столбец базисных переменных, «Решение» - столбец правых частей уравнений системы. Решение не является оптимальным, т.к. в z – строке есть отрицательные коэффициенты.
итерация 0
БП |
Решение | Отношение | |||||
Для улучшения решения перейдем к следующей итерации, получим следующую симплекс-таблицу. Для этого надо выбрать разрешающий столбец , т.е. переменную, которая войдет в базис на следующей итерации. Он выбирается по наибольшему по модулю отрицательному коэффициенту в z-строке (в задаче на максимум) – в начальной итерации это столбец x 2 (коэффициент -6).
Затем выбирается разрешающая строка , т.е. переменная, которая выйдет из базиса на следующей итерации. Она выбирается по наименьшему отношению столбца "Решение" к соответствующим положительным элементам разрешающего столбца (столбец «Отношение») – в начальной итерации это строка s 3 (коэффициент 20).
Разрешающий элемент находится на пересечении разрешающего столбца и разрешающей строки, его ячейка выделена цветом, он равен 1. Следовательно, на следующей итерации переменная x 2 заменит в базисе s 3 . Заметим, что в z-строке отношение не ищется, там ставится прочерк " - ". В случае если есть одинаковые минимальные отношения, то выбирается любое из них. Если в разрешающем столбце все коэффициенты меньше или равны 0, то решение задачи бесконечно.
Заполним следующую таблицу «Итерация 1». Её мы получим из таблицы «Итерация 0». Цель дальнейших преобразований - превратить разрешающий столбец х 2 в единичный (с единицей вместо разрешающего элемента и нулями вместо остальных элементов).
1)Вычисление строки х 2 таблицы "Итерация 1". Сначала делим все члены разрешающей строки s 3 таблицы "Итерация 0" на разрешающий элемент (он равен 1 в данном случае) этой таблицы, получим строку x 2 в таблице «Итерации 1». Т.к. разрешающий элемент в данном случае равен 1, то строка s 3 таблицы "Итерация 0" будет совпадать со строкой х 2 таблицы "Итерация 1". Строку x 2 таблицы "Итерации 1" мы получили 0 1 0 0 1 20, остальные строки таблицы "Итерация 1" будут получены из этой строки и строк таблицы "Итерация 0" следующим образом:
2) Вычисление z-строки таблицы "Итерация 1". На месте -6 в первой строке (z-строке) в столбце х 2 таблицы "Итерация 0" должен быть 0 в первой строке таблицы "Итерация 1". Для этого все элементы строки х 2 таблицы "Итерация 1" 0 1 0 0 1 20 умножим на 6, получим 0 6 0 0 6 120 и сложим эту строку с первой строкой (z - строкой) таблицы "Итерация 0" -4 -6 0 0 0 0, получим -4 0 0 0 6 120. В столбце x 2 появился ноль 0 , цель достигнута. Элементы разрешающего столбца х 2 выделены красным цветом.
3) Вычисление строки s 1 таблицы "Итерация 1". На месте 1 в s 1 строке таблицы "Итерация 0" должен быть 0 в таблице "Итерация 1". Для этого все элементы строки х 2 таблицы "Итерация 1" 0 1 0 0 1 20 умножим на -1, получим 0 -1 0 0 -1 -20 и сложим эту строку с s 1 - строкой таблицы "Итерация 0" 2 1 1 0 0 64, получим строку 2 0 1 0 -1 44. В столбце х 2 получен необходимый 0.
4) Вычисление строки s 2 таблицы "Итерация 1". На месте 3 в s 2 строке таблицы "Итерация 0" должен быть 0 в таблице "Итерация 1". Для этого все элементы строки х 2 таблицы "Итерация 1" 0 1 0 0 1 20 умножим на -3, получим 0 -3 0 0 -3 -60 и сложим эту строку с s 2 - строкой таблицы "Итерация 0" 1 3 0 1 0 72, получим строку 1 0 0 1 -3 12. В столбце х 2 получен нужный 0. Столбец х 2 в таблице "Итерация 1" стал единичным, он содержит одну 1 и остальные 0.
Строки таблицы «Итерация 1» получаем по следующему правилу:
Новая строка = Старая строка – (Коэффициент разрешающего столбца старой строки)*(Новая разрешающая строка).
Например для z -строки имеем:
Старая
z-строка (-4 -6
0
0
0
0)
-(-6)*Новая разрешающая строка -(0
-6
0
0
-6
-120)
=Новая z-строка
(-4
0
0
0
6
120)
.
Для следующих таблиц пересчет элементов таблицы делается аналогично, поэтому мы его опускаем.
итерация 1
| Решение | Отношение | ||||||
Разрешающий столбец х 1 , разрешающая строка s 2 , s 2 выходит из базиса, х 1 входит в базис. Совершенно аналогично получим остальные симплекс-таблицы, пока не будет получена таблица со всеми положительными коэффициентами в z-строке. Это признак оптимальной таблицы.
Итерация 2
| Решение | Отношение | ||||||
Разрешающий столбец s 3 , разрешающая строка s 1 , s 1 выходит из базиса, s 3 входит в базис.
Итерация 3
| Решение | Отношение | ||||||
В z-строке все коэффициенты неотрицательны, следовательно, получено оптимальное решение x 1 = 24, x 2 = 16, z max = 192.
Симплекс-метод, решение задачи с искусственным базисом
2) Решим задачу с искусственным базисом (хотя бы один знак неравенств-ограничений " ≥ " или " = ").
Запишем задачу в канонической форме (в виде системы уравнений, что требует симплекс-метод), для этого введем две переменные х 3 ≥ 0 и х 4 ≥ 0 получим:
Система ограничений предлагает только одну допустимую базисную переменную x 4 , только она входит только в одно уравнение в третье с коэффициентом 1, поэтому в первое и второе уравнения добавляем искусственные переменные R 1 ≥ 0 и R 2 ≥ 0 Чтобы можно было примененить симплекс-метод система уравнений-ограничений должна быть системой с базисом, т.е. в каждом уравнении должна быть переменная с коэффициентом 1, которая входит только в одно уравнение системы, в нашем случае это R 1 , R 2 и x 4 . Получили, так называемую, М-задачу:
Данная система является системой с базисом, в которой R 1 , R 2 и x 4 базисные переменные, а x 1 , x 2 и x 3 свободные переменные, свободние члены всех уравнений неотрицательны. Следовательно, для решения задачи можно применить симплекс-метод. Запишем начальную симплекс-таблицу:
итерация 0
| Решение | Отношение | |||||||
| -16 | ||||||||
В таблицу для задач с искусственным базисом добавлена строка «Оценка». Она получается суммированием соответствующих коэффициентов строк с искусственными переменными (R) с обратным знаком. Она будет присутствовать в таблице до тех пор, пока хотя бы одна из искусственных переменных есть в базисе. По наибольшему по модулю отрицательному коэффициенту строки "Оценка" определяется разрешающий столбец пока она есть в таблице. Когда строка "Оценка" выйдет из таблицы (в базисе нет искусственных переменных) разрешающий столбец будет определяться по z-строке, как и в задаче с начальным базисом. В данной таблице разрешающий столбец х 2 , он выбран по наибольшей по модулю отрицательной оценке (-7). Разрешающая строка R 2 выбрана по наименьшему отношению столбца "Решение" к соответствующим положительным элементам разрешающего столбца, как и в задаче без искусственных переменных. Это значит, что на следующей итерации переменная х 2 из свободной перейдет в базисную, а переменная R 2 из базисной – в свободную. Запишем следующую симплекс-таблицу:
Разрешающий столбец х 1 , разрешающая строка R 1 , R 1 выходит из базиса, x 1 входит в базис. После этого в базисе не остается искусственных переменных, поэтому строки «Оценка» в следующей таблице нет:
итерация 2
| Решение | Отношение | |||||||
Далее разрешающий столбец выбирается по z-строке. В z-строке все коэффициенты неотрицательны кроме коэффициента при искусственной переменной R 1 , который не влияет на оптимальность, когда искусственные переменные вышли из базиса. Следовательно, получено оптимальное решение x 1 = 6/5; x 2 = 3/5; z max = 72/5.
Особые случаи применения симплекс-метода
1) Когда прямая (если рассматривается двухмерная задача линейного программирования, а в общем случае гиперплоскость), представляющая целевую функцию параллельна прямой (гиперплоскости), соответствующей одному из неравенств-ограничений (которое в точке оптимума выполняется, как точное равенство) целевая функция принимает одно и тоже оптимальное значение на некотором множестве точек границы области допустимых решений. Эти решения называются альтернативными оптимальными решениями . Наличие альтернативных решений можно определить по оптимальной симплекс-таблице. Если в z-строке оптимальной таблицы есть нулевые коэффициенты небазисных переменных, то есть альтернативные решения.
2) Если в разрешающем столбце симплекс-таблицы все коэффициенты меньше или равны нуль, то нельзя выбрать разрешающую строку, в этом случае решение неограничено.
3) Если ограничения задачи линейного программирования несовместны (т.е. они не могут выполняться одновременно), то задача не имеет допустимых решений. Такая ситуация не может возникнуть, если все неравенства, составляющие систему ограничений, имеют тип " ≤ " с неотрицательными правыми частями, т.к. в этом случае дополнительные переменные могут составить допустимое решение. Для других типов ограничений использются искусственные переменные. Если задача имеет решение, то в оптимальной таблице в базисе нет искусственных переменных (R i). Если они там есть, то задача не имеет решений.