Решение производственной задачи табличным симплекс-методом. Решение систем линейных уравнений методом жордана-гаусса
Читайте также:
|
Теорема (о выборе разрешающего элемента)
Если в нескольких столбцах 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 |
При графическом методе решения задач ЛП мы фактически из множества вершин, принадлежащих границе множества решений системы неравенств, выбрали такую вершину, в которой значение целевой функции достигало максимума (минимума). В случае двух переменных этот метод совершенно нагляден и позволяет быстро находить решение задачи.
Если в задаче три и более переменных, а в реальных экономических задачах как раз такая ситуация, трудно представить наглядно область решений системы ограничений. Такие задачи решаются с помощью симплекс-метода или методом последовательных улучшений. Идея метода проста и заключается в следующем.
По определенному правилу находится первоначальный опорный план (некоторая вершина области ограничений). Проверяется, является ли план оптимальным. Если да, то задача решена. Если нет, то переходим к другому улучшенному плану - к другой вершине. значение целевой функции на этом плане (в этой вершине) заведомо лучше, чем в предыдущей. Алгоритм перехода осуществляется с помощью некоторого вычислительного шага, который удобно записывать в виде таблиц, называемых симплекс-таблицами . Так как вершин конечное число, то за конечное число шагов мы приходим к оптимальному решению.
Рассмотрим симплексный метод на конкретном примере задачи о составлении плана.
Еще раз заметим, что симплекс-метод применим для решения канонических задач ЛП, приведенных к специальному виду, т. е. имеющих базис, положительные правые части и целевую функцию, выраженную через небазисные переменные. Если задача не приведена к специальному виду, то нужны дополнительные шаги, о которых мы поговорим позже.
Рассмотрим задачу о плане производства, предварительно построив модель и приведя ее к специальному виду.
Задача.
Для изготовления изделий А и В склад может отпустить сырья не более 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. С какой строки удобно начинать пересчет таблицы? |
Если в условии задачи есть ограничения со знаком ≥, то их можно привести к виду ∑a ji b j , умножив обе части неравенства на -1. Введем m дополнительных переменных x n+j ≥0(j =1,m ) и преобразуем ограничения к виду равенств
(2)
Предположим, что все исходные переменные задачи x 1 , x 2 ,..., x n – небазисные. Тогда дополнительные переменные будут базисными, и частное решение системы ограничений имеет вид
x 1 = x 2 = ... = x n = 0, x n+ j = b j , j =1,m . (3)
Так как при этом значение функции цели F 0 = 0 , можно представить F(x) следующим образом:
F(x)=∑c i x i +F 0 =0 (4)
Начальная симплекс-таблица (симплекс-табл. 1) составляется на основании уравнений (2) и (4). Если перед дополнительными переменными x n+j стоит знак «+», как в (2), то все коэффициенты перед переменными x i и свободный член b j заносятся в симплекс-таблицу без изменения. Коэффициенты функции цели при ее максимизации заносятся в нижнюю строку симплекс-таблицы с противоположными знаками. Свободные члены в симплекс-таблице определяют решение задачи.
Алгоритм решения задачи следующий:
1-й шаг. Просматриваются элементы столбца свободных членов. Если все они положительные, то допустимое базисное решение найдено и следует перейти к шагу 5 алгоритма, соответствующему нахождению оптимального решения. Если в начальной симплекс-таблице есть отрицательные свободные члены, то решение не является допустимым и следует перейти к шагу 2.
2-й шаг. Для нахождения допустимого решения осуществляется , при этом нужно решать, какую из небазисных переменных включить в базис и какую переменную вывести из базиса.
Таблица 1.
| базисные переменные | Свободные члены в ограничениях | Небазисные переменные | |||||
| x 1 | x 2 | ... | x l | ... | x n|||
| x n+1 | b 1 | a 11 | a 12 | ... | a 1l | ... | a 1n |
| x n+2 | b 2 | a 21 | a 22 | ... | a 2l | ... | a 2n |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| x n+r | b2 | a r1 | a r2 | ... | a rl | ... | a rn |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| x n+m | b m | a m1 | a m2 | ... | a ml | ... | a mn |
| F(x) max | F 0 | -c 1 | -c 2 | ... | -c 1 | ... | -c n |
Для этого выбирают любой из отрицательных элементов столбца свободных членов (пусть это будет b 2 ведущим, или разрешающим. Если в строке с отрицательным свободным членом нет отрицательных элементов, то система ограничений несовместна и задача не имеет решения.
Одновременно из БП исключается та переменная, которая первой изменит знак при увеличении выбранной НП x l . Это будет x n+r , индекс r которой определяется из условия
т.е. та переменная, которой соответствует наименьшее отношение свободного члена к элементу выбранного ведущего столбца. Это отношение называется симплексным отношением. Следует рассматривать только положительные симплексные отношения.
Строка, соответствующая переменной x n+r , называется ведущей, или разрешающей. Элемент симплекс-таблицы a rl , стоящий на пересечении ведущей строки и ведущего столбца, называется ведущим, или разрешающим элементом. Нахождением ведущего элемента заканчивается работа с каждой очередной симплекс-таблицей.
3-й шаг. Рассчитывается новая симплекс-таблица, элементы которой пересчитываются из элементов симплекс-таблицы предыдущего шага и помечаются штрихом, т.е. b" j , a" ji , c" i , F" 0 . Пересчет элементов производится по следующим формулам:
Сначала в новой симплекс-таблице заполнятся строка и столбец, которые в предыдущей симплекс-таблице были ведущими. Выражение (5) означает, что элемент a" rl на месте ведущего равен обратной величине элемента предыдущей симплекс-таблицы. Элементы строки a ri делятся на ведущий элемент, а элементы столбца a jl также делятся на ведущий элемент, но берутся с противоположным знаком. Элементы b" r и c" l рассчитываются по тому же принципу.
Остальные формулы легко записать с помощью .
Прямоугольник строится по старой симплекс-таблице таким образом, что одну из его диагоналей образует пересчитываемый (a ji) и ведущий (a rl) элементы (рис. 1). Вторая диагональ определяется однозначно. Для нахождения нового элемента a" ji из элемента a ji вычитается (на это указывает знак « – » у клетки) произведение элементов противоположной диагонали, деленное на ведущий элемент. Аналогично пересчитываются элементы b" j , (j≠r) и c" i , (i≠l).
4-й шаг. Анализ новой симплекс-таблицы начинается с 1-го шага алгоритма. Действие продолжается, пока не будет найдено допустимое базисное решение, т.е. все элементы столбца свободных членов должны быть положительными.
5-й шаг. Считаем, что допустимое базисное решение найдено. Просматриваем коэффициенты строки функции цели F(x) . Признаком оптимальности симплекс-таблицы является неотрицательность коэффициентов при небазисных переменных в F-строке.
Рис. 1. Правило прямоугольника
Если среди коэффициентов F-строки имеются отрицательные (за исключением свободного члена), то нужно переходить к другому базисному решению. При максимизации функции цели в базис включается та из небазисных переменных (например x l), столбцу которой соответствует максимальное абсолютное значение отрицательного коэффициента c l в нижней строке симплекс-таблицы. Это позволяет выбрать ту переменную, увеличение которой приводит к улучшению функции цели. Столбец, соответствующий переменной x l , называется ведущим. Одновременно из базиса исключается та переменная x n+r , индекс r которой определяется минимальным симплексным отношением:
Строка, соответствующая x n+r , называется ведущей , а элемент симплекс-таблицы a rl , стоящий на пересечении ведущей строки и ведущего столбца, называется ведущим элементом.
6-й шаг. по правилам, изложенным на 3-м шаге. Процедура продолжается до тех пор, пока не будет найдено оптимальное решение или сделан вывод, что оно не существует.
Если в процессе оптимизации решения в ведущем столбце все элементы неположительные, то ведущую строку выбрать невозможно. В этом случае функция в области допустимых решений задачи не ограничена сверху и F max ->&∞.
Если же на очередном шаге поиска экстремума одна из базисных переменных становится равной нулю, то соответствующее базисное решение называется вырожденным. При этом возникает так называемое зацикливание, характеризующееся тем, что с определенной частотой начинает повторяться одинаковая комбинация БП (значение функции F при этом сохраняется) и невозможно перейти к новому допустимому базисному решению. Зацикливание является одним из основных недостатков симплекс-метода, но встречается сравнительно редко. На практике в таких случаях обычно отказываются от ввода в базис той переменной, столбцу которой соответствует максимальное абсолютное значение отрицательного коэффициента в функции цели, и производят случайный выбор нового базисного решения.
Пример 1. Решить задачу
max{F(x) = -2x 1 + 5x 2 | 2x 1 + x 2 ≤7; x 1 + 4x 2 ≥8; x 2 ≤4; x 1,2 ≥0}
Симплексным методом и дать геометрическую интерпретацию процесса решения.
Графическая интерпретация решения задачи представлена на рис. 2. Максимальное значение функции цели достигается в вершине ОДЗП с координатами . Решим задачу с помощью симплекс-таблиц. Умножим второе ограничение на (-1) и введём дополнительные переменные, чтобы неравенства привести к виду равенств, тогда
Исходные переменные x 1 и x 2 принимаем в качестве небазисных, а дополнительные x 3 , x 4 и x 5 считаем базисными и составляем симплекс-таблицу(симплекс-табл. 2). Решение, соответствующее симплекс-табл. 2, не является допустимым; ведущий элемент обведен контуром и выбран в соответствии с шагом 2 приведенного ранее алгоритма. Следующая симплекс-табл. 3 определяет допустимое базисное решение, ему соответствует вершина ОДЗП на рис. 2 Ведущий элемент обведен контуром и выбран в соответствии с 5-м шагом алгоритма решения задачи. Табл. 4 соответствует оптимальному решению задачи, следовательно: x 1 = x 5 = 0; x 2 = 4; x 3 = 3; x 4 = 8; F max = 20.
Рис. 2. Графическое решение задачи
Основные теоремы линейного программирования
Для обоснования методов решения задач линейного программирования сформулируем ряд важнейших теорем, опуская их аналитические доказательства. Уяснить смысл каждой из теорем поможет понятие о геометрической интерпретации решения ЗЛП, данное в предыдущем подразделе.
Однако сначала напомним о некоторых понятиях, важных с точки зрения дальнейшего разговора.
Любые m переменных системы m линейных уравнений с n переменными (m < n) называются основными , если определитель матрицы коэффициентов при них отличен от нуля. Тогда остальные m-n переменных называются неосновными (или свободными) .
Базисным решением системы m линейных уравнений c n переменными (m < n) называется всякое ее решение, в котором все неосновные переменные имеют нулевые значения.
Теорема 1 . Множество всех допустимых решений системы ограничений задачи линейного программирования является выпуклым.
В частном случае, когда в систему ограничений входят только две переменные x 1 и x 2 , это множество можно изобразить на плоскости. Так как речь идет о допустимых решениях (x 1 , x 2 ≥ 0), то соответствующее множество будет располагаться в первой четверти декартовой системы координат. Это множество может быть замкнутым (многоугольник), незамкнутым (неограниченная многогранная область), состоять из единственной точки и, наконец, система ограничений-неравенств может быть противоречивой.
Теорема 2 . Если задача линейного программирования имеет оптимальное решение, то оно совпадает с одной (двумя) из угловых точек множества допустимых решений.
Из теоремы 2 можно сделать вывод о том, что единственность оптимального решения может нарушаться, причем, если решение не единственное, то таких оптимальных решений будет бесчисленное множество (все точки отрезка, соединяющего соответствующие угловые точки).
Теорема 3 . Каждому допустимому базисному решению задачи линейного программирования соответствует угловая точка области допустимых решений, и наоборот.
Следствием из теорем 2 и 3 является утверждение о том, что оптимальное решение (оптимальные решения) задачи линейного программирования, заданной (или приведенной) ограничениями-уравнениями, совпадает с допустимым базисным решением (допустимыми базисными решениями) системы ограничений.
Таким образом, оптимальное решение ЗЛП следует искать среди конечного числа допустимых базисных решений.
Симплекс-метод был разработан и впервые применен для решения задач в 1947 г. американским математиком Дж. Данцигом.
Симплексный метод в отличие от геометрического универсален. С его помощью можно решить любую задачу линейного программирования.
В основу симплексного метода положена идея последовательного улучшения получаемого решения.
Геометрический смысл симплексного метода состоит в последовательном переходе от одной вершины многогранника ограничений к соседней, в которой целевая функция принимает лучшее (или, по крайней мере, не худшее) значение до тех пор, пока не будет найдено оптимальное решение - вершина, где достигается оптимальное значение функции цели (если задача имеет конечный оптимум).
Таким образом, имея систему ограничений, приведенную к канонической форме (все функциональные ограничения имеют вид равенств), находят любое базисное решение этой системы, заботясь только о том, чтобы найти его как можно проще. Если первое же найденное базисное решение оказалось допустимым, то проверяют его на оптимальность. Если оно не оптимально, то осуществляется переход к другому, обязательно допустимому базисному решению. Симплексный метод гарантирует, что при этом новом решении целевая функция, если и не достигнет оптимума, то приблизится к нему (или, по крайней мере, не удалится от него). С новым допустимым базисным решением поступают так же, пока не отыщется решение, которое является оптимальным.
Процесс применения симплексного метода предполагает реализацию трех его основных элементов:
1) способ определения какого-либо первоначального допустимого базисного решения задачи;
2) правило перехода к лучшему (точнее, не худшему) решению;
3) критерий проверки оптимальности найденного решения.
Симплексный метод включает в себя ряд этапов и может быть сформулирован в виде четкого алгоритма (четкого предписания о выполнении последовательных операций). Это позволяет успешно программировать и реализовывать его на ЭВМ. Задачи с небольшим числом переменных и ограничений могут быть решены симплексным методом вручную.
Реализация симплекс-алгоритма включает восемь шагов. Опишем их, параллельно рассматривая пример выполнения каждого шага в применении к задаче о хоккейных клюках и шахматных наборах.
Шаг 1 . Формулировка ЗЛП (формирование целевой функции и системы ограничений).
Рассмотрим подробно, как производится пересчет симплекс-таблиц (на примере одной итерации). Пусть имеется симплекс-таблица представленная на Рис.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 (об этом нам говорит новый разрешающий столбец) и все вычисления повторятся снова.