Лекция: Алгоритм симплекс-метода.

Рассмотрим решение ЗЛП симплекс-методом и изложим ее применительно к задаче максимизации.

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 при ограничениях:

2x1+3x2+x3=3,

x1+3x3=2,

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

Δ8 = 0 · 0 + 0 · 0 + (– M) · 1 + (– M) · 0 – (– M) = 0

Δ9 = 0 · 0 + 0 · 0 + (– M) · 0 + (– M) · 1 – (– M) = 0

Поскольку есть отрицательные оценки, то план не оптимален. Наименьшая оценка:

Δ1 = – M – 10

Вводим переменную x1 в базис.

Определяем переменную, выходящую из базиса. Для этого находим наименьшее неотрицательное отношение

для столбца x1.

Наименьшее неотрицательное: Q4 = 50. Выводим переменную x9 из базиса и удаляем искусственные переменные. Выполняем линейные преобразования.

Из 1-й строки вычитаем 4-ю строку, умноженную на 2Из 2-й строки вычитаем 4-ю строку, умноженную на 5

Получаем новую таблицу:

Симплекс таблица № 3

Целевая функция:

0 · 1400 + 0 · 350 + 10 · 100 + 8 · 50 = 1400

 

Вычисляем оценки по формуле:

Δ1 = 0 · 0 + 0 · 0 + 10 · 1 + 8 · 0 – 10 = 0

Δ2 = 0 · 0 + 0 · 0 + 10 · 0 + 8 · 1 – 8 = 0

Δ3 = 0 · 4 + 0 · 4 + 10 · 0 + 8 · 0 – 12 = – 12

Δ4 = 0 · 1 + 0 · 0 + 10 · 0 + 8 · 0 – 0 = 0

Δ5 = 0 · 0 + 0 · 1 + 10 · 0 + 8 · 0 – 0 = 0

Δ6 = 0 · 5 + 0 · 4 + 10 · (–1) + 8 · 0 – 0 = – 10

Δ7 = 0 · 2 + 0 · 5 + 10 · 0 + 8 · (–1) – 0 = – 8

Поскольку есть отрицательные оценки, то план не оптимален. Наименьшая оценка:

Δ3 = – 12

Вводим переменную x3 в базис.

Определяем переменную, выходящую из базиса. Для этого находим наименьшее неотрицательное

отношение

для столбца x3.

Наименьшее неотрицательное: Q2 = 87.5. Выводим переменную x5 из базиса

2-ю строку делим на 4.Из 1-й строки вычитаем 2-ю строку, умноженную на 4

Вычисляем:

Получаем новую таблицу:

Симплекс таблица № 4

Целевая функция:

0 · 1050 + 12 · 175/2 + 10 · 100 + 8 · 50 = 2450

Вычисляем оценки по формуле:

Δ1 = 0 · 0 + 12 · 0 + 10 · 1 + 8 · 0 – 10 = 0

Δ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 единиц.

Теорема о связи между решениями исходной задачи и М-задачи.

???????????????????????

еще рефераты
Еще работы по информатике