Симплексный метод решения злп. Метод Гаусса-Жордана. Примеры решения систем линейных алгебраических уравнений методом Гаусса-Жордана
Приведенные выше преобразования удобно выполнять в специальных таблицах, называемых симплекс-таблицами.
В симплекс-таблице выделяются следующие блоки:
Запишем решение задачи примера из раздела 3.3 в симплекс-таблицах:
Все исходные данные, содержащиеся в математическом условии задачи, переносятся в первую симплексную таблицу. Зануляя свободные переменные, получаем опорный план
В последнюю строку первой симплекс-таблицы заносим критерий в неявной форме
Исключаем из этого критерия базисную переменную x 4 , приводя критерий к виду
Для оптимальности решения все оценки должны быть неотрицательны
Решение не оптимальное, т.к. есть отрицательные оценки.
Оценки могут быть вычислены по формулам. Произведение представляет из себя, текущий вектор матрицы условий, тогда оценку свободной переменной можно вычислить как скалярное произведение вектора коэффициентов при базисных переменных на текущий вектор матрицы условий минус коэффициент целевой функции при этой переменной. Так, для получаем значение
Разрешающим столбцом выбираем тот, где наименьшая по величине оценка (если задача на максимум). А для выбора разрешающей строки нужно среди всех строк найти, выраженная из которой переменная, уменьшаясь, которая быстрее обращается в ноль.
В итоге, мы получаем, что разрешающий столбец - , а разрешающая строка - . Значит из списка базисных выходит переменная и входит переменная.
Решение не оптимальное, т.к. есть отрицательная оценка -2.
Решение оптимальное, т.к. все оценки больше нуля. Очевидно, что увеличить нельзя.
Правила построения симплекс-таблиц
Симплекс-таблица строится для какого-либо опорного решения.
Пусть опорное решение. Симплекс-таблица для этого решения имеет вид
Базисная матрица B = (A 1 , A 2 , … A m)
· при базисных переменных текущая матрица единичная.
- · любой столбец.
- · вектор правых частей ограничений.
- · оценки при свободных переменных не нулевые
· в правой нижней клетке - значение критерия
Этапы симплекс-метода
- 1. Проверка признака оптимальности ()
- 2. Если есть, то решение не оптимальное. Тогда выбираем столбец с минимальной оценкой. Его назовем разрешающим.
- 3. Разрешающая строка выбирается по минимальному отношению свободных членов к положительным коэффициентам разрешающего столбца. Базисная переменная, выражающаяся из этой строки, выходит из списка базисных переменных. Т.е. x k выходит, а x s входит.
- 4. Текущая симплекс-таблица преобразуется по следующему правилу:
- · разрешающая строка делится на разрешающий элемент:
- · разрешающий столбец заменяется единичным.
- · все остальные элементы симплекс-таблицы могут быть пересчитаны по правилу четырехугольника:
Мысленно строится четырехугольник на диагонали, соединяющей искомый элемент с разрешающим. Тогда новое значение элемента равно прежнему значению минус произведение элементов на противоположной диагонали, деленное на разрешающий элемент.
Или новое значение элемента равно произведению элементов на главной диагонали минус произведение элементов на противоположной диагонали, и все это деленное на разрешающий элемент.
Замечание : Если в разрешающей строке был нулевой элемент, значит этот столбец не меняется; если в разрешающем столбце есть нулевой элемент, то соответствующая строка не меняется.
Рассмотрим решение ЗЛП симплекс-методом и изложим ее применительно к задаче максимизации.
1. По условию задачи составляется ее математическая модель.
2. Составленная модель преобразовывается к канонической форме. При этом может выделиться базис с начальным опорным планом.
3. Каноническая модель задачи записывается в форме симплекс-таблицы так, чтобы все свободные члены были неотрицательными. Если начальный опорный план выделен, то переходят к пункту 5.
Симплекс таблица: вписывается система ограничительных уравнений и целевая функция в виде выражений, разрешенных относительно начального базиса. Строку, в которую вписаны коэффициенты целевой функции F, называют F-строкой или строкой целевой функции.
4. Находят начальный опорный план, производя симплексные преобразования с положительными разрешающими элементами, отвечающими минимальным симплексным отношениям, и не принимая во внимание знаки элементов F-строки. Если в ходе преобразований встретится 0-строка, все элементы которой, кроме свободного члена, нули, то система ограничительных уравнений задачи несовместна. Если же встретится 0-строка, в которой, кроме свободного члена, других положительных элементов нет, то система ограничительных уравнений не имеет неотрицательных решений.
Приведение системы (2.55), (2.56) к новому базису будем называть симплексным преобразованием. Если симплексное преобразование рассматривать как формальную алгебраическую операцию, то можно заметить, что в результате этой операции происходит перераспределение ролей между двумя переменными, входящими в некоторую систему линейных функций: одна переменная из зависимых переходит в независимые, а другая наоборот - из независимых в зависимые. Такая операция известна в алгебре под названием шага жорданова исключения.
5. Найденный начальный опорный план исследуется на оптимальность:
а) если в F-строке нет отрицательных элементов (не считая свободного члена), то план оптимален. Если при этом нет и нулевых, то оптимальный план единственный; если же есть хотя бы один нулевой, то оптимальных планов бесконечное множество;
б) если в F-строке есть хотя бы один отрицательный элемент, которому соответствует столбец неположительных элементов, то <
в) если в F-строке есть хотя бы один отрицательный элемент, а в его столбце есть хотя бы один положительный, то можно перейти к новому опорному плану, более близкому к оптимальному. Для этого указанный столбец надо назначить разрешающим, по минимальному симплексному отношению найти разрешающую строку и выполнить симплексное преобразование. Полученный опорный план вновь исследовать на оптимальность. Описанный процесс повторяется до получения оптимального плана либо до установления неразрешимости задачи.
Столбец коэффициентов при переменной, включаемой в базис, называют разрешающим. Таким образом, выбирая переменную, вводимую в базис (или выбирая разрешающий столбец) по отрицательному элементу F-строки, мы обеспечиваем возрастание функции F.
Немного сложней определяется переменная, подлежащая исключению из базиса. Для этого составляют отношения свободных членов к положительным элементам разрешающего столбца (такие отношения называют симплексными) и находят среди них наименьшее, которое и определяет строку (разрешающую), содержащую исключаемую переменную. Выбор переменной, исключаемой из базиса (или выбор разрешающей строки), по минимальному симплексному отношению гарантирует, как уже установлено, положительность базисных компонент в новом опорном плане.
В пункте 3 алгоритма предполагается, что все элементы столбца свободных членов неотрицательны. Это требование не обязательно, но если оно выполнено, то все последующие симплексные преобразования производятся только с положительными разрешающими элементами, что удобно при расчетах. Если в столбце свободных членов есть отрицательные числа, то разрешающий элемент выбирают следующим образом:
1) просматривают строку, отвечающую какому-либо отрицательному свободному члену, например t-строку, и выбирают в ней какой-либо отрицательный элемент, а соответствующий ему столбец принимают за разрешающий (предполагаем, что ограничения задачи совместны);
2) составляют отношения элементов столбца свободных членов к соответствующим элементам разрешающего столбца, имеющим одинаковые знаки (симплексные отношения);
3) из симплексных отношений выбирают наименьшее. Оно и определит разрешающую строку. Пусть ею будет, например, р -строка;
4) на пересечении разрешающих столбца и строки находят разрешающий элемент. Если разрешающим оказался элемент y-строки, то после симплексного преобразования свободный член этой строки станет положительным. В противном случае на следующем шаге вновь обращаются к t-строке. Если задача разрешима, то через некоторое число шагов в столбце свободных членов не останется отрицательных элементов.
Нахождение исходного опорного плана, канонический вид ЗЛП
Идея последовательного улучшения решения легла в основу универсального метода решения задач линейного программирования - симплексного метода или метода последовательного улучшения плана.
Геометрический смысл симплексного метода состоит в последовательном переходе от одной вершины многогранника ограничений (называемой первоначальной) к соседней, в которой линейная функция принимает лучшее (по крайней мере, не худшее) значение по отношению к цели задачи; до тех пор, пока не будет найдено оптимальное решение - вершина, где достигается оптимальное значение функции цели (если задача имеет конечный оптимум).
Впервые симплексный метод был предложен американским ученым Дж. Данцигом в 1949 г., однако еще в 1939 г. идеи метода были разработаны российским ученым Л.В. Канторовичем.
Симплексный метод, позволяющий решить любую задачу линейного программирования, универсален. В настоящее время он используется для компьютерных расчетов, однако несложные примеры с применением симплексного метода можно решать и вручную.
Для реализации симплексного метода - последовательного улучшения решения - необходимо освоить три основных элемента:
Способ определения какого-либо первоначального допустимого базисного решения задачи;
Правило перехода к лучшему (точнее, не худшему) решению;
Критерий проверки оптимальности найденного решения.
Для использования симплексного метода задача линейного программирования должна быть приведена к каноническому виду, т.е. система ограничений должна быть представлена в виде уравнений.
В литературе достаточно подробно описываются: нахождение начального опорного плана (первоначального допустимого базисного решения), тоже - методом искусственного базиса, нахождение оптимального опорного плана, решение задач с помощью симплексных таблиц.
58. Основная теорема симплекс метода.
???????????????????????????????????????????????????????????????????????
59. Альтернативный оптимум в ЗЛП, вырожденность в ЗЛП.
Вырожденность в задачах линейного программирования
Рассматривая симплекс-метод, мы предполагали, что задача линейного программирования является невырожденной, т.е. каждый опорный план содержит ровно m положительных компонент, где m - число ограничений в задаче. В вырожденном опорном плане число положительных компонент оказывается меньше числа ограничений: некоторые базисные переменные, соответствующие данному опорному плану, принимают нулевые значения. Используя геометрическую интерпретацию для простейшего случая, когда n - m = 2 (число небазисных переменных равно 2), легко отличить вырожденную задачу от невырожденной. В вырожденной задаче в одной вершине многогранника условий пересекается более двух прямых, описываемых уравнениями вида xi = 0. Это значит, что одна или несколько сторон многоугольника условий стягиваются в точку. Аналогично при n - m = 3 в вырожденной задаче в одной вершине пересекается более 3-х плоскостей xi = 0. В предположении о невырожденности задачи
находилось только одно значение, по которому определялся индекс выводимого из базиса вектора условий (выводимой из числа базисных переменной). В
вырожденной задаче может достигаться на нескольких индексах сразу (для нескольких строк). В этом случае в находимом опорном плане несколько базисных переменных будут нулевыми. Если задача линейного программирования оказывается вырожденной, то при плохом выборе вектора условий, выводимого из базиса, может возникнуть бесконечное движение по базисам одного и того же опорного плана. Это - так называемое явление зацикливания. Хотя в практических задачах линейного программирования зацикливание явлеется довольно редким, возможность его не исключена. Один из приемов борьбы с вырожденностью состоит в преобразовании задачи путем "незначительного" изменения вектора правых частей системы ограничений на величины таким образом, чтобы задача стала невырожденной, и, в то же время, чтобы это изменение не повлияло реально на оптимальный план задачи. Чаще реализуемые алгоритмы включают в себя некоторые простые правила, снижающие вероятность возникновения зацикливания или его преодоления. Пусть переменную xj необходимо сделать базисной. Рассмотрим
множество индексов E0, состоящее из тех i, для которых достигается. Множество индексов i, для которых выполняется данное условие обозначим через E0,. Если E0, состоит из одного элемента, то из базиса исключается вектор условий Ai (переменная xi делается небазисной). Если E0 состоит более чем из одного элемента, то составляется множество E1, которое состоит из , на которых достигается . Если E1 состоит из одного индекса k, то из базиса выводится переменная xk. В противном случае составляется множество E2 и т.д. Практически правилом надо пользоваться, если зацикливание уже обнаружено.
Альтернативный оптимум в ЗЛП???????????????????????????
60. Метод искусственного базиса. М-задача. Теорема о связи между решениями исходной задачи и М-задачи.
Метод искусственного базиса.
Метод искусственного базиса используется для нахождения допустимого базисного решения задачи линейного программирования, когда в условии присутствуют ограничения типа равенств. Рассмотрим задачу:
max{F(x)=∑cixi|∑ajixi=bj, j=1,m; xi≥0}.
В ограничения и в функцию цели вводят так называемые «искусственные переменные» Rj следующим образом:
∑ajix+Rj=bj, j=1,m;F(x)=∑cixi-M∑Rj
При введении искусственных переменных в методе искусственного базиса в функцию цели им приписывается достаточно большой коэффициент M, который имеет смысл штрафа за введение искусственных переменных. В случае минимизации искусственные переменные прибавляются к функции цели с коэффициентом M. Введение искусственных переменных допустимо в том случае, если в процессе решения задачи они последовательно обращаются в нуль.
Симплекс-таблица, которая составляется в процессе решения, используя метод искусственного базиса, называется расширенной. Она отличается от обычной тем, что содержит две строки для функции цели: одна – для составляющей F = ∑cixi, а другая – для составляющей M ∑Rj Рассмотрим процедуру решения задачи на конкретном примере.
Пример 1. Найти максимум функции F(x) = -x1 + 2x2 - x3 при ограничениях:
x1≥0, x2≥0, x3≥0 .
Применим метод искусственного базиса. Введем искусственные переменные в ограничения задачи
2x1 + 3x2 + x3 + R1 = 3;
x1 + 3x3 + R2 = 2 ;
Функция цели F(x)-M ∑Rj= -x1 + 2x2 - x3 - M(R1+R2).
Выразим сумму R1 + R2 из системы ограничений: R1 + R2 = 5 - 3x1 - 3x2 - 4x3, тогда F(x) = -x1 + 2x2 - x3 - M(5 - 3x1 - 3x2 - 4x3) .
При составлении первой симплекс-таблицы (табл. 1) будем полагать, что исходные переменные x1, x2 , x3 являются небазисными, а введенные искусственные переменные – базисными. В задачах максимизации знак коэффициентов при небазисных переменных в F- и M-строках изменяется на противоположный. Знак постоянной величины в M-строке не изменяется. Оптимизация проводится сначала по M-строке. Выбор ведущих столбца и строки, все симплексные преобразования при испльзовании метода искусственного базиса осуществляются как в обычном симплекс-методе.
Максимальный по абсолютному значению отрицательный коэффициент (-4) определяет ведущий столбец и переменную x3, которая перейдет в базис. Минимальное симплексное отношение (2/3) соответствует второй строке таблицы, следовательно, переменная R2 должна быть из базиса исключена. Ведущий элемент обведен контуром.
В методе искусственного базиса искусственные переменные, исключенные из базиса, в него больше не возвращаются, поэтому столбцы элементов таких переменных опускаются. Табл. 2. сократилась на 1 столбец. Осуществляя пересчет этой таблицы, переходим к табл. 3., в которой строка M обнулилась, ее можно убрать. После исключения из базиса всех искусственных переменных получаем допустимое базисное решение исходной задачи, которое в рассматриваемом примере является оптимальным:
x1=0; x2=7/9; Fmax=8/9.
Если при устранении M-строки решение не является оптимальным, то процедура оптимизации продолжается и выполняется обычным симплекс-методом. Рассмотрим пример, в котором присутствуют ограничения всех типов:≤,=,≥
Условие задачи
Найти оптимальные величины производства продукции видов А, Б и В. Затраты сырья на единицу продукции: А – 5, Б – 2, В – 4. Объем сырья – 2000 единиц. Затраты оборудования на единицу продукции: А – 4, Б – 5, В – 4. Объем оборудования – 1000 единиц. Прибыль от реализации единицы продукции: А – 10, Б – 8, В – 12. Критерий – максимум прибыли предприятия. Производство продукции А должно быть не менее 100 ед. Производство продукции Б должно быть не менее 50 ед.
Решение задачи симплекс М методом
1) Определение оптимального плана производства
Пусть x1, x2, x3 - количество произведенной продукции вида А, Б, В, соответственно. Тогда математическая модель задачи имеет вид:
F = 10·x1 + 8·x2 + 12·x3 –>max
Вводим дополнительные переменные x4 ≥ 0, x5 ≥ 0, x6 ≥ 0, x7 ≥ 0, чтобы неравенства преобразовать в равенства.
Чтобы выбрать начальный базис, вводим искусственные переменные x8 ≥ 0, x9 ≥ 0 и очень большое число M (M –> ∞). Решаем М методом.
F = 10·x1 + 8·x2 + 12·x3 + 0·x4 + 0·x5 + 0·x6 + 0·x7– M·x8– M·x9 –>max
В качестве базиса возьмем x4 = 2000; x5 = 1000; x8 = 100; x9 = 50.
Данные заносим в симплекс таблицу
Симплекс таблица № 1
Целевая функция:
0 · 2000 + 0 · 1000 + (– M) · 100 + (– M) · 50 = – 150M
Вычисляем оценки по формуле:
Δ1 = 0 · 5 + 0 · 4 + (– M) · 1 + (– M) · 0 – 10 = – M – 10
Δ2 = 0 · 2 + 0 · 5 + (– M) · 0 + (– M) · 1 – 8 = – M – 8
Δ3 = 0 · 4 + 0 · 4 + (– M) · 0 + (– M) · 0 – 12 = – 12
Δ4 = 0 · 1 + 0 · 0 + (– M) · 0 + (– M) · 0 – 0 = 0
Δ5 = 0 · 0 + 0 · 1 + (– M) · 0 + (– M) · 0 – 0 = 0
Δ6 = 0 · 0 + 0 · 0 + (– M) · (–1) + (– M) · 0 – 0 = M
Δ7 = 0 · 0 + 0 · 0 + (– M) · 0 + (– M) · (–1) – 0 = M
Δ2 = 0 · 0 + 12 · 0 + 10 · 0 + 8 · 1 – 8 = 0
Δ3 = 0 · 0 + 12 · 1 + 10 · 0 + 8 · 0 – 12 = 0
Δ4 = 0 · 1 + 12 · 0 + 10 · 0 + 8 · 0 – 0 = 0
Δ5 = 0 · (–1) + 12 · 1/4 + 10 · 0 + 8 · 0 – 0 = 3
Δ6 = 0 · 1 + 12 · 1 + 10 · (–1) + 8 · 0 – 0 = 2
Δ7 = 0 · (–3) + 12 · 5/4 + 10 · 0 + 8 · (–1) – 0 = 7
Поскольку отрицательных оценок нет, то план оптимален.
Решение задачи: x1 = 100; x2 = 50; x3 = 175/2 = 87.5; x4 = 1050; x5 = 0; x6 = 0; x7 = 0; Fmax = 2450
Ответ: x1 = 100; x2 = 50; x3 = 175/2 = 87.5; x4 = 1050; x5 = 0; x6 = 0; x7 = 0; Fmax = 2450То есть необходимо произвести x1 = 100 единиц продукции вида А, x2 = 50 единиц продукции вида Б и x3 = 87,5 единиц продукции вида В. Максимальная прибыль при этом составит Fmax = 2450 единиц.
Теорема о связи между решениями исходной задачи и М-задачи.
???????????????????????
Читайте также:
|
Теорема (о выборе разрешающего элемента)
Если в нескольких столбцах 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 |
Рассмотрим подробно, как производится пересчет симплекс-таблиц (на примере одной итерации). Пусть имеется симплекс-таблица представленная на Рис.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 (об этом нам говорит новый разрешающий столбец) и все вычисления повторятся снова.
Если в условии задачи есть ограничения со знаком ≥, то их можно привести к виду ∑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. Графическое решение задачи
