Симплекс метод выбор разрешающей строки. Симплексный метод решения злп

Один из методов решения оптимизационных задач (как правило связанных с нахождением минимума или максимума ) линейного программирования называется . Симплекс-метод включает в себя целую группу алгоритмов и способов решения задач линейного программирования. Один из таких способов, предусматривающий запись исходных данных и их пересчет в специальной таблице, носит наименование табличного симплекс-метода .

Рассмотрим алгоритм табличного симплекс-метода на примере решения производственной задачи , которая сводится к нахождению производственного плана обеспечивающего максимальную прибыль.

Исходные данные задачи на симплекс-метод

Предприятие выпускает 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 руб.

Галяутдинов Р.Р.

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

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

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

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

Рассмотрим подробно, как производится пересчет симплекс-таблиц (на примере одной итерации). Пусть имеется симплекс-таблица представленная на Рис.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 (об этом нам говорит новый разрешающий столбец) и все вычисления повторятся снова.

При графическом методе решения задач ЛП мы фактически из множества вершин, принадлежащих границе множества решений системы неравенств, выбрали такую вершину, в которой значение целевой функции достигало максимума (минимума). В случае двух переменных этот метод совершенно нагляден и позволяет быстро находить решение задачи.

Если в задаче три и более переменных, а в реальных экономических задачах как раз такая ситуация, трудно представить наглядно область решений системы ограничений. Такие задачи решаются с помощью симплекс-метода или методом последовательных улучшений. Идея метода проста и заключается в следующем.

По определенному правилу находится первоначальный опорный план (некоторая вершина области ограничений). Проверяется, является ли план оптимальным. Если да, то задача решена. Если нет, то переходим к другому улучшенному плану - к другой вершине. значение целевой функции на этом плане (в этой вершине) заведомо лучше, чем в предыдущей. Алгоритм перехода осуществляется с помощью некоторого вычислительного шага, который удобно записывать в виде таблиц, называемых симплекс-таблицами . Так как вершин конечное число, то за конечное число шагов мы приходим к оптимальному решению.

Рассмотрим симплексный метод на конкретном примере задачи о составлении плана.

Еще раз заметим, что симплекс-метод применим для решения канонических задач ЛП, приведенных к специальному виду, т. е. имеющих базис, положительные правые части и целевую функцию, выраженную через небазисные переменные. Если задача не приведена к специальному виду, то нужны дополнительные шаги, о которых мы поговорим позже.

Рассмотрим задачу о плане производства, предварительно построив модель и приведя ее к специальному виду.

Задача.

Для изготовления изделий А и В склад может отпустить сырья не более 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). Если они там есть, то задача не имеет решений.