Двойственный симплекс-метод

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

при условиях

и среди чисел имеются отрицательные.

В данном случае есть решение системы линейных уравнений (55). Однако это решение не является планом задачи (54) - (56), так как среди его компонент имеются отрицательные числа.

Поскольку векторы - единичные, каждый из векторов можно представить в виде линейной комбинации данных векторов, причем коэффициентами разложения векторов по векторам служат числа

Таким образом, можно найти:

На основе исходных данных составляют симплекс-таблицу, в которой некоторые элементы столбца вектора являются отрицательными числами. Если таких чисел нет, то в симплекс-таблице записан оптимальный план задачи (54) - (56), поскольку, по предположению, все. Поэтому для определения оптимального плана задачи при условии, что он существует, следует произвести упорядоченный переход от одной симплекс-таблицы к другой до тех пор, пока из столбца вектора P0 не будут исключены отрицательные элементы. При этом все время должны оставаться неотрицательными все элементы (т +1)-й строки, т.е. для любого

Таким образом, после составления симплекс-таблицы проверяют, имеются ли в столбце вектора Po отрицательные числа. Если их нет, то найден оптимальный план исходной задачи. Если же они имеются (что мы и предполагаем), то выбирают наибольшее по абсолютной величине отрицательное число. В том случае, когда таких чисел несколько, берут какое-нибудь одно из них: пусть это число b l . Выбор этого числа определяет вектор, исключаемый из базиса, т. е. в данном случае из базиса выводится вектор P l . Чтобы определить, какой вектор следует ввести в базис, находим

Пусть это минимальное значение принимается при j=r, тогда в базис вводят вектор Р r . Число является разрешающим элементов. Переход к новой симплекс-таблице производят по обычным правилам симплексного метода. Итерационный процесс продолжают до тех пор, пока в столбце вектора Р 0 не будет больше отрицательных чисел. При этом находят оптимальный план исходной задачи, а следовательно, и двойственной. Если на некотором шаге окажется, что в i -й строке симплекс-таблицы в столбце вектора Р 0 стоит отрицательное число b i , а среди остальных элементов этой строки нет отрицательных, то исходная задача не имеет решения.

Таким образом, отыскание решения задачи двойственным симплекс-методом включает следующие этапы:

• 1. Находят псевдоплан задачи.
• 2. Проверяют этот псевдоплан на оптимальность. Если псевдоплан оптимален, то найдено решение задачи. В противном случае либо устанавливают неразрешимость задачи, либо переходят к новому псевдоплану.
• 3. Выбирают разрешающую строку с помощью определения наибольшего по абсолютной величине отрицательного числа столбца вектора Р 0 и разрешающий столбец с помощью нахождения наименьшего по абсолютной величине отношения элементов (m +1)-и строки к соответствующим отрицательным элементам разрешающей строки.
• 4. Находят новый псевдоплан и повторяют все действия начиная с этапа 2.

Найти максимальное значение функции

при условиях :

Решение . Запишем исходную задачу линейного программирования в форме основной задачи: найти максимум функции при условиях

Составим для последней задачи двойственную задачу. Такой является задача, в результате решения которой требуется найти минимальное значение функции

Строим симплекс таблицу:

Итерация 0:

Условие допустимости выполняется, так как в графе «Решение» все значения положительные, но не выполняется условие оптимальности, так как -строка содержит отрицательный коэффициент.Продолжаем наши действия

Итерация 1:

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

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

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

Решение задач симплекс-методом: примеры онлайн

Задача 1. Компания производит полки для ванных комнат двух размеров — А и В. Агенты по продаже считают, что в неделю на рынке может быть реализовано до 550 полок. Для каждой полки типа А требуется 2 м2 материала, а для полки типа В — 3 м2 материала. Компания может получить до 1200 м2 материала в неделю. Для изготовления одной полки типа А требуется 12 мин машинного времени, а для изготовления одной полки типа В — 30 мин; машину можно использовать 160 час в неделю. Если прибыль от продажи полок типа А составляет 3 денежных единицы, а от полок типа В — 4 ден. ед., то сколько полок каждого типа следует выпускать в неделю?

Составление математической модели и решение ЗЛП симплекс-методом (pdf, 33 Кб)

Задача 2. Решить задачу линейного программирования симплекс-методом.

Решение симплекс-методом с искусственным базисом (pdf, 45 Кб)

Задача 3. Предприятие производит 3 вида продукции: А1, А2, А3, используя сырьё двух типов. Известны затраты сырья каждого типа на единицу продукции, запасы сырья на планируемый период, а также прибыль от единицы продукции каждого вида.

1. Сколько изделий каждого вида необходимо произвести, чтобы получить максимум прибыли?
2. Определить статус каждого вида сырья и его удельную ценность.
3. Определить максимальный интервал изменения запасов каждого вида сырья, в пределах которого структура оптимального плана, т.е. номенклатура выпуска, не изменится.
4. Определить количество выпускаемой продукции и прибыль от выпуска при увеличении запаса одного из дефицитных видов сырья до максимально возможной (в пределах данной номенклатуры выпуска) величины.
5. Определить интервалы изменения прибыли от единицы продукции каждого вида, при которых полученный оптимальный план не изменится.

Решение задачи линейного программирования с экономическим анализом (pdf, 163 Кб)

Задача 4. Решить задачу линейного программирования симплексным методом:

Решение табличным симплекс-методом с поиском опорного плана (pdf, 44 Кб)

Задача 5. Решить задачу линейного программирования симплекс-методом:

Решение табличным симплекс-методом (pdf, 47 Кб)

Задача 6. Решить задачу симплекс-методом, рассматривая в качестве начального опорного плана, план, приведенный в условии:

Решение ручным симплекс-методом (pdf, 60 Кб)

Задача 7. Решить задачу модифицированным симплекс-методом.
Для производства двух видов изделий А и Б используется три типа технологического оборудования. На производство единицы изделия А оборудование первого типа используется а1=4 часов, оборудование второго типа а2=8 часов, а оборудование третьего типа а3=9 часов. На производство единицы изделия Б оборудование первого типа используется б1=7 часов, оборудование второго типа б2=3 часов, а оборудование третьего типа б3=5 часов.
На изготовление этих изделий оборудование первого типа может работать не более чем t1=49 часов, оборудование второго типа не более чем t2=51 часов, оборудование третьего типа не более чем t3=45 часов.
Прибыль от реализации единицы готового изделия А составляет АЛЬФА=6 рублей, а изделия Б – БЕТТА=5 рублей.
Составить план производства изделий А и Б, обеспечивающий максимальную прибыль от их реализации.

Решение модифицированным симплекс-методом (pdf, 67 Кб)

Задача 8. Найти оптимальное решение двойственным симплекс-методом

Решение двойственным симплекс-методом (pdf, 43 Кб)

Примеры решений задач по линейному программированию

Методы решения задачи линейного программирования

Опорные решения задачи линейного программирования

Пусть дана задача линейного программирования в канонической форме записи

при условиях

Будем обозначать через множество решений системы (2) – (3). Предположим, что , где – ранг матрицы , – количество уравнений в системе (2).

Из системы векторов-столбцов матрицы выберем некоторую линейно независимую подсистему из векторов . Она существует, так как . Эта система образует базис в . Обозначим через , . Назовем множеством базисных значений индекса , – базиснойподматрицей матрицы . Координаты вектора будем называть базисными , если , и небазисными в противном случае.

Запишем систему (2) в виде . Разобьем слагаемые левой части на базисные и небазисные, то есть

Определим частное решение этой системы следующим образом. Положим в (4) все небазисные переменные равными нулю . Тогда система (4) примет вид

Назовем (5) базисной подсистемой системы уравнений (2). Обозначим через вектор, составленный из базисных координат вектора . Тогда систему (2) можно переписать в векторно-матричном виде

Так как подматрица является базисной, она

невырождена. Поэтому система (6) имеет единственное решение . Полученное таким образом частное решение системы (2) назовем опорным решением прямой задачи линейного программирования, соответствующим базису . (Иногда опорное решение также называют базисным ). Как видим, базису соответствует единственное опорное решение. Очевидно, что число опорных решений конечно.

Для данного базиса определим также и опорное решение двойственной задачи линейного программирования. Напомним, что задача двойственная к канонической имеет вид

при условиях

Запишем систему (8) в виде

Напомним, что множество решений системы (8) обозначается через .

Определим вектор двойственных переменных из условия выполнения базисных ограничений в системе (9) как равенств. Получим следующую систему линейных уравнений:

Обозначим через вектор, составленный из ба-

зисных координат вектора . Тогда систему (10) можно переписать в векторно-матричном виде

Система (11) также имеет единственное решение .

Назовем его опорным (базисным ) решением двойственной задачи линейного программирования, соответствующим базису . Это опорное решение также определяется однозначно.

Итак, любому базису соответствуют два вектора – два опорных решения и прямой и двойственной задач линейного программирования, соответственно.

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

Если опорное решение удовлетворяет всем ограничениям (9) двойственной задачи, то базис, которому соответствует это опорное решение, называется двойственно допустимым . В этом случае вектор называется опорным планом двойственной задачи линейного программирования, а соответствующее тому же базису опорное реше-

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

Для двойственной допустимости базиса достаточно выполнения только небазисных неравенств . Заметим, что опорный план является допустимым вектором двойственной задачи линейного программирования ().

Разности левых и правых частей неравенств (9) обозначим через , . Тогда двойственную допустимость базиса можно устанавливать, проверяя неотрицательность всех . Заметим, что, как следует непосредственно из определения, все базисные невязки равны нулю ().

Пример решения прямой и двойственной задачи симплекс методом

Поэтому достаточно убедиться в выполнении неравенств для всех .

Теорема 1. Пусть и – опорные решения задачи линейного программирования, соответствующие некоторому базису , тогда имеет место равенство .

Доказательство . Из определений опорных решений легко получить равенства

откуда и следует справедливость теоремы.

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

Доказательство. Справедливость этого утверждения следует из теории двойственности в линейном программировании и теоремы 1.

Теорема 3. Допустимое решение задачи (1) – (3) является опорным планом задачи тогда и только тогда, когда оно является вершиной выпуклого многогранного множества .

Доказательство. Пусть – опорный план задачи (1) – (3). Докажем, что – вершина множества . По определению опорный план – допустимое опорное решение, соответствующее некоторому базису , то есть – решениесистемы линейных уравнений относительно переменных

Легко увидеть, что эта система имеет единственное решение. Значит, несущая плоскость грани, содержащей точку , имеет размерность 0. Следовательно, – вершина множества .

Обратно. Пусть – вершина множества . Докажем, что – опорный план задачи (1) – (3). Так как – вершина, то она является гранью множества , размерность которой равна нулю. Следовательно, у вектора найдется не менее нулевых компонент, множество номеров которых обозначим . Таким образом, – единственное решение системы

где . Поэтому осталось доказать, что система векторов линейно независима. Предположим противное. Тогда существуют числа не все равные нулю, такие что . Поэтому

Это означает, что система (12) имеет решение, отличное от , что противоречит единственности ее решения. Таким образом, – базис, а вектор – соответствующий ему опорный план задачи (1) – (3). Что и требовалось.

Заметим, что допустимое решение задачи (7), (8) (двойственной задаче (1) – (3)) также является опорным планом тогда и только тогда, когда оно является вершиной допустимого множества .

Дата публикования: 2015-01-10; Прочитано: 695 | Нарушение авторского права страницы

Studopedia.org — Студопедия.Орг — 2014-2018 год.(0.005 с)…

Для определенности считаем, что решается задача на отыскание минимума.

1. Задачу линейного программирования привести к каноническому виду.

После введения добавочных переменных систему уравнений и линейную функцию записываем в виде, который называется расширенной системой:

Предполагаем, что все добавочные переменные имеют тот же знак, что и свободные члены; в противном случае используем так называемый М – метод, который будет рассмотрен ниже.

2. Определить базисные и свободные переменные.

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

4. Определить возможность решения задачи по значениям согласно теоремам 6.7,…, 6.9.

5. Выбрать разрешающий (опорный) элемент .

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

Если критерий оптимальности не выполнен (не выполнены условия теоремы 6.7 или 6.8), то наибольший по модулю отрицательный коэффициент в последней строке определяет разрешающий (опорный) столбец .

Составляем оценочные отношения каждой строки по следующим правилам:

1 0) , если все и имеют разные знаки;

2 0) , если все и ;

3 0) , если ;

4 0) 0, если и ;

5 0) , если и имеют одинаковые знаки.

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

6 0) Переход к следующей таблице по правилам:

а) в левом столбце записываем новый базис: вместо основной переменной – переменную , т.е. поменяем местами переменные и ;

б) на место опорного элемента поставить 1;

в) на остальных местах опорной строки в новой таблице оставить элементы исходной таблицы;

г) на остальные места в опорном столбце поставить соответствующие элементы исходной таблицы, умноженные на –1;

д) на оставшиеся свободные места элементов , , в новой таблице записать числа , , , которые находятся следующим образом:

Для упрощения вычислений по этим формулам их можно сформулировать в виде «правила прямоугольника» (рис. 6.8): элементы на диагоналях прямоугольника с вершинами (или , , , , или , , , ) перемножаются (произведение, не содержащее опорного элемента , берется со знаком минус) и полученные произведения складываются;

е) все полученные элементы новой таблицы разделить на опорный элемент .

7 0) По значению элемента определить, найдено ли оптимальное значение целевой функции. В случае отрицательного ответа продолжить решение (возврат к пункту 6).

Рис. 6.8. Правило прямоугольника для определения чисел:

а − , б − , в − .

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

Пример 6.8. Решить задачу, приведенную в примере 6.7, симплекс методом.

⇐ Предыдущая45678910111213Следующая ⇒

Дата публикования: 2015-01-23; Прочитано: 174 | Нарушение авторского права страницы

Studopedia.org — Студопедия.Орг — 2014-2018 год.(0.002 с)…

Главная >> Пример №3. Симплекс метод. Нахождение наибольшего значения функции (искусственный базис)

Симплекс метод

Среди коэффициентов выделенной строки нет положительных. Следовательно, найдено наибольшее значение функции F.

Ответ:

x 1 = 3 x 2 = 4

F max = 13

Перейти к решению своей задачи

© 2010-2018, по всем вопросам пишите по адресу [email protected]

Условие задачи

Для реализации трех групп товаров коммерческое предприятие располагает тремя видами ограниченных материально-денежных ресурсов в количестве b 1 = 240, b 2 = 200, b 3 = 160 единиц. При этом для продажи 1 группы товаров на 1 тыс. руб. товарооборота расходуется ресурса первого вида в количестве a 11 = 2 единицы, ресурса второго вида в количестве a 21 = 4 единицы, ресурса третьего вида в количестве a 31 = 4 единицы. Для продажи 2 и 3 групп товаров на 1 тыс. руб. товарооборота расходуется соответственно ресурса первого вида в количестве a 12 = 3, a 13 = 6 единицы, ресурса второго вида в количестве a 22 = 2, a 23 = 4 единицы, ресурса третьего вида в количестве a 32 = 6, a 33 = 8 единиц. Прибыль от продажи трех групп товаров на 1 тыс.

Симплексный метод решения ЗЛП

руб. товарооборота составляет соответственно c 1 = 4, c 2 = 5, c 3 = 4 (тыс. руб.). Определить плановый объем и структуру товарооборота так, чтобы прибыль торгового предприятия была максимальной.

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

Решение задачи симплекс методом

Пусть x 1 , x 2 , x 3 — количество реализованных товаров, в тыс. руб., 1, 2, 3 — ей групп, соответственно. Тогда математическая модель задачи имеет вид:

F = 4·x 1 + 5·x 2 + 4·x 3 ->max

Решаем симплекс методом.

Вводим дополнительные переменные x 4 ≥ 0, x 5 ≥ 0, x 6 ≥ 0, чтобы неравенства преобразовать в равенства.

В качестве базиса возьмем x 4 = 240; x 5 = 200; x 6 = 160.

Данные заносим в симплекс таблицу

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

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

0 · 240 + 0 · 200 + 0 · 160 = 0

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

Δ 1 = 0 · 2 + 0 · 4 + 0 · 4 - 4 = - 4
Δ 2 = 0 · 3 + 0 · 2 + 0 · 6 - 5 = - 5
Δ 3 = 0 · 6 + 0 · 4 + 0 · 8 - 4 = - 4
Δ 4 = 0 · 1 + 0 · 0 + 0 · 0 - 0 = 0
Δ 5 = 0 · 0 + 0 · 1 + 0 · 0 - 0 = 0
Δ 6 = 0 · 0 + 0 · 0 + 0 · 1 - 0 = 0

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

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

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

= 26.667

Наименьшее неотрицательное: Q 3 = 26.667. Выводим переменную x 6 из базиса

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

Вычисляем:

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

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

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

0 · 160 + 0 · 440/3 + 5 · 80/3 = 400/3

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

Δ 1 = 0 · 0 + 0 · 8/3 + 5 · 2/3 - 4 = - 2/3
Δ 2 = 0 · 0 + 0 · 0 + 5 · 1 - 5 = 0
Δ 3 = 0 · 2 + 0 · 4/3 + 5 · 4/3 - 4 = 8/3
Δ 4 = 0 · 1 + 0 · 0 + 5 · 0 - 0 = 0
Δ 5 = 0 · 0 + 0 · 1 + 5 · 0 - 0 = 0
Δ 6 = 0 · (-1)/2 + 0 · (-1)/3 + 5 · 1/6 - 0 = 5/6

Поскольку есть отрицательная оценка Δ 1 = - 2/3, то план не оптимален.

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

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

Наименьшее неотрицательное: Q 3 = 40. Выводим переменную x 2 из базиса

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

Вычисляем:

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

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

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

0 · 160 + 0 · 40 + 4 · 40 = 160

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

Δ 1 = 0 · 0 + 0 · 0 + 4 · 1 - 4 = 0
Δ 2 = 0 · 0 + 0 · (-4) + 4 · 3/2 - 5 = 1
Δ 3 = 0 · 2 + 0 · (-4) + 4 · 2 - 4 = 4
Δ 4 = 0 · 1 + 0 · 0 + 4 · 0 - 0 = 0
Δ 5 = 0 · 0 + 0 · 1 + 4 · 0 - 0 = 0
Δ 6 = 0 · (-1)/2 + 0 · (-1) + 4 · 1/4 - 0 = 1

Поскольку отрицательных оценок нет, то план оптимален.

Решение задачи:

Ответ

x 1 = 40; x 2 = 0; x 3 = 0; x 4 = 160; x 5 = 40; x 6 = 0; F max = 160

То есть необходимо реализовать товар первого вида в объеме 40 тыс.

руб. Товар 2-го и 3-го видов реализовывать не надо. При этом максимальная прибыль составит F max = 160 тыс. руб.

Решение двойственной задачи

Двойственная задача имеет вид:

Z = 240·y 1 + 200·y 2 + 160·y 3 ->min

Вводим дополнительные переменные y 4 ≥ 0, y 5 ≥ 0, y 6 ≥ 0, чтобы неравенства преобразовать в равенства.

Сопряженные пары переменных прямой и двойственной задач имеют вид:

Из последней симплекс таблицы № 3 прямой задачи, находим решение двойственной задачи:

Z min = F max = 160;
y 1 = Δ 4 = 0; y 2 = Δ 5 = 0; y 3 = Δ 6 = 1; y 4 = Δ 1 = 0; y 5 = Δ 2 = 1; y 6 = Δ 3 = 4;

Ответ

y 1 = 0; y 2 = 0; y 3 = 1; Z min = 160;

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

Базисным решением является одно из допустимых решений, находящихся в вершинах области допустимых значений. Проверяя на оптимальность вершину за вершиной симплекса, приходят к искомому оптимуму. На этом принципе основан симплекс-метод.

Симплекс – это выпуклый многоугольник в n-мерном пространстве с n+1 вершинами, не лежащими в одной гиперплоскости (гиперплоскость делит пространство на два полупространства).

Например, линия бюджетных ограничений делит блага на доступные и недоступные.

Доказано, что если оптимальное решение существует, то оно обязательно будет найдено через конечное число итераций (шагов), кроме случаев «зацикливания».

Алгоритм симплексного метода состоит из ряда этапов.

Первый этап. Строится исходная оптимизационная модель. Далее исходная матрица условий преобразуется в приведенную каноническую форму, которая среди всех других канонических форм выделяется тем, что:

а) правые части условий (свободные члены bi) являются величинами неотрицательными;

б) сами условия являются равенствами;

в) матрица условий содержит полную единичную подматрицу.

Если свободные члены отрицательные, то обе части неравенства умножаются на — 1, а знак неравенства меняется на противоположный. Для преобразования неравенств в равенства вводятся дополнительные переменные, которые, обычно, обозначают объем недоиспользованных ресурсов. В этом их экономический смысл.

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

В оптимальном решении задачи все искусственные переменные (ИП) должны быть равными нулю. Для этого вводят искусственные переменные в целевую функцию задачи с большими отрицательными коэффициентами (-М) при решении задачи на max, и с большими положительными коэффициентами (+М), когда задача решается на min. В этом случае даже незначительное ненулевое значение искусственной переменной будет резко уменьшать (увеличивать) значение целевой функции. Обычно М в 1000 раз должно быть больше, чем значения коэффициентов при основных переменных.

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

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

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

Столбец симплексной таблицы с этим номером на данной итерации называется генеральным столбцом.

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

Элемент симплексной таблицы, находящийся на пересечении генеральных столбца и строки, называется генеральным элементом.

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

Значения новых базисных переменных получим в соответствующих ячейках столбца свободных членов.

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

Симплекс метод

Пример решения оптимизационных задач линейного программирования симплексным методом

Пусть необходимо найти оптимальный план производства двух видов продукции (х1 и х2).

Исходные данные:

Построим оптимизационную модель

– ограничение по ресурсу А;

– ограничение по ресурсу В.

Приведем задачу к приведенной канонической форме. Для этого достаточно ввести дополнительные переменные Х3 и Х4. В результате неравенства преобразуются в строгие равенства.

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

1-я итерация. Находим генеральный столбец и генеральную строку:

Генеральный элемент равняется 5.

2-я итерация. Найденное базисное решение не является оптимальным, т.к. cтрока оценок (Fj-Cj) содержит один положительный элемент. Находим генеральный столбец и генеральную строку:

max (0,0.3,-1.4,0) = 0.2

Найденное решение оптимально, так как все специальные оценки целевой функции Fj – Cj равны нулю или отрицательны. F(x)=29 x1=2; x2=5.

.
Приведем систему ограничений к системе неравенств смысла ≤, умножив соответствующие строки на (-1).
Определим минимальное значение целевой функции F(X) = x 1 + x 2 при следующих условиях-ограничений.
- 5x 1 - 6x 2 ≤-1
- 15x 1 ≤-1
- 7x 1 - 12x 2 ≤-1
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме ).
В 1-м неравенстве смысла (≤) вводим базисную переменную x 3 . В 2-м неравенстве смысла (≤) вводим базисную переменную x 4 . В 3-м неравенстве смысла (≤) вводим базисную переменную x 5 .
-5x 1 -6x 2 + 1x 3 + 0x 4 + 0x 5 = -1
-15x 1 + 0x 2 + 0x 3 + 1x 4 + 0x 5 = -1
-7x 1 -12x 2 + 0x 3 + 0x 4 + 1x 5 = -1
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

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

Инструкция для решения задач двойственным симплекс-методом . Выберите количество переменных и количество строк (количество ограничений), нажмите Далее. Полученное решение сохраняется в файле Word (см. пример решения двойственным симплекс-методом).

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

Задачи динамического программирования
Распределить 5 однородных партий товара между тремя рынками так, чтобы получить максимальный доход от их продажи. Доход от продажи на каждом рынке G(X) зависит от количества реализованных партий товара Х и представлен в таблице.

В P-методе оптимальный план получается в результате движения по псевдопланам. Псевдоплан - план, в котором условия оптимальности удовлетворяются, а среди значений базисных переменных x i имеются отрицательные числа. Алгоритм двойственного симплекс-метода включает следующие этапы:

1. Составление псевдоплана . Систему ограничений исходной задачи приводят к системе неравенств смысла «≤».
2. Проверка плана на оптимальность . Если в полученном опорном плане не выполняется условие оптимальности, то задача решается симплексным методом .
3. Выбор ведущих строки и столбца . Среди отрицательных значений базисных переменных выбираются наибольшие по абсолютной величине. Строка, соответствующая этому значению, является ведущей.
4. Расчет нового опорного плана . Новый план получается в результате пересчета симплексной таблицы методом Жордана-Гаусса . Далее переход к этапу 2.

Пример . Предприятию необходимо выпустить по плану продукции А1 единиц, А2 единиц, А3 единиц. Каждый вид изделия может производиться на двух машинах.
Как распределить работу машин, чтобы общие затраты времени на выполнение плана были минимальны? Дана матрица затрат и ресурс времени каждой машины. Записать модель исследуемой операции в форме, допускающей использование P–метода.

Известно, что содержание n питательных веществ A, B и С в рационе должно быть не менее m1, m2, m3 единиц соответственно. Указанные питательные вещества содержат три вида продуктов. Содержание единиц питательных веществ в одном килограмме каждого из видов продукта приведено в таблице. определите дневной рацион, обеспечивающий получение необходимого количества питательных веществ при минимальных денежных затратах.

Задание : Решить задачу, используя алгоритм двойственного симплекс-метода.
Приведем систему ограничений к системе неравенств смысла ≤, умножив соответствующие строки на (-1).
Определим минимальное значение целевой функции F(X) = 4x 1 + 2x 2 + x 3 при следующих условиях-ограничений.
- x 1 - x 2 ≤-10
2x 1 + x 2 - x 3 ≤8
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
В первом неравенстве смысла (≤) вводим базисную переменную x 4 . Во втором неравенстве смысла (≤) вводим базисную переменную x 5 .
-1x 1 -1x 2 + 0x 3 + 1x 4 + 0x 5 = -10
2x 1 + 1x 2 -1x 3 + 0x 4 + 1x 5 = 8
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

Итерация №1

План 0 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.


Ведущей будет первая строка, а переменную x 4 следует вывести из базиса.
3. Определение новой базисной переменной. Минимальное значение θ соответствует 2-му столбцу, т.е. переменную x 2 необходимо ввести в базис.

Итерация №2
1. Проверка критерия оптимальности.
План 1 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.
2. Определение новой свободной переменной.
Среди отрицательных значений базисных переменных выбираем наибольший по модулю.
Ведущей будет вторая строка, а переменную x 5 следует вывести из базиса.
3. Определение новой базисной переменной. Минимальное значение θ соответствует третьему столбцу, т.е. переменную x 3 необходимо ввести в базис.
На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (-1).

Итерация №3
1. Проверка критерия оптимальности.
Среди значений индексной строки нет положительных. Поэтому эта таблица определяет оптимальный план задачи.

Краткая теория

Для решения задач линейного программирования предложено немало различных методов. Однако наиболее эффективным и универсальным среди них оказался симплекс-метод. При этом следует отметить, что при решении некоторых задач могут оказаться более эффективными другие методы. Например, при ЗЛП с двумя переменными оптимальным является , а при решении - метод потенциалов. Симплекс-метод является основным и применимым к любой ЗПЛ в канонической форме.

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

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

1. умение находить начальный опорный план;
2. наличие признака оптимальности опорного плана;
3. умение переходить к нехудшему опорному плану.

Пример решения задачи

Условие задачи

Для реализации трех групп товаров коммерческое предприятие располагает тремя видами ограниченных материально-денежных ресурсов в количестве , , , единиц. При этом для продажи 1 группы товаров на 1 тыс. руб. товарооборота расходуется ресурса первого вида в количестве единиц, ресурса второго вида в количестве единиц, ресурса третьего вида в количестве единиц. Для продажи 2 и 3 групп товаров на 1 тыс. руб. товарооборота расходуется соответственно ресурса первого вида в количестве , единиц, ресурсов второго вида в количестве , единиц, ресурсов третьего вида в количестве , единиц. Прибыль от продажи трех групп товаров на 1 тыс. руб. товарооборота составляет соответственно , , тыс. руб.

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

Если ваш допуск к сессии зависит от решения блока задач, а у вас нет ни времени, ни желания садиться за расчёты – используйте возможности сайта сайт. Заказ задач – дело нескольких минут. Подробно (как оставить заявку, цены, сроки, способы оплаты) можно почитать на странице Купить решение задач по линейному программированию...

Решение задачи

Построение модели

Через обозначим товарооборот 1-го, 2-го и третьего вида товаров соответственно.

Тогда целевая функция, выражающая получаемую прибыль:

Ограничения по материально-денежным ресурсам:

Кроме того, по смыслу задачи

Получаем следующую задачу линейного программирования:

Приведение к каноническому виду ЗЛП

Приведем задачу к каноническому виду. Для преобразования неравенств в равенства введем дополнительные переменные . Переменные входят в ограничения с коэффициентом 1. В целевую функцию все дополнительные переменные введем с коэффициентом, равным нулю.

Ограничение имеет предпочтительный вид, если при неотрицательности правой части левая часть имеет переменную, входящую с коэффициентом, равным единице, а остальные ограничения-равенства - с коэффициентом, равным нулю. В нашем случае 1-е, 2-е, 3-е ограничения имеют предпочтительный вид с соответствующими базисными переменными .

Решение симплекс-методом

Заполняем симплексную таблицу 0-й итерации.

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

Переход к следующей итерации осуществляем следующим образом:

Ведущий столбец соответствует .

Ключевая строка определяется по минимуму соотношений свободных членов и членов ведущего столбца (симплексных отношений):

На пересечении ключевого столбца и ключевой строки находим разрешающий элемент, т.е.7.

Теперь приступаем к составлению 1-й итерации. Вместо единичного вектора вводим вектор .

В новой таблице на месте разрешающего элемента пишем 1, все остальные элементы ключевого столбца –нули. Элементы ключевой строки делятся на разрешающий элемент. Все остальные элементы таблицы вычисляются по правилу прямоугольника.

Получаем таблицу 1-й итерации:

Ключевой столбец для 1-й итерации соответствует .

Находим ключевую строку, для этого определяем:

На пересечении ключевого столбца и ключевой строки находим разрешающий элемент, т.е. 31/7.

Вектор выводим из базиса и вводим вектор .

Получаем таблицу 2-й итерации:

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

Таким образом, необходимо продавать 7,1 тыс.р. товара 1-го вида и 45,2 тыс.р. товара 3-го вида. Товар 2-го вида продавать невыгодно. При этом прибыль будет максимальна и составит 237,4 тыс.р. При реализации оптимального плана остаток ресурса 3-го вида составит 701 ед.

Двойственная задача ЛП

Запишем модель двойственной задачи.

Для построения двойственной задачи необходимо пользоваться следующими правилами:

1) если прямая задача решается на максимум, то двойственная - на минимум, и наоборот;

2) в задаче на максимум ограничения-неравенства имеют смысл ≤, а в задаче минимизации - смысл ≥;

3) каждому ограничению прямой задачи соответствует переменная двойственной задачи, и наоборот, каждому ограничению двойственной задачи соответствует переменная прямой задачи;

4) матрица системы ограничений двойственной задачи получается из матрицы системы ограничений исходной задачи транспонированием;

5) свободные члены системы ограничений прямой задачи являются коэффициентами при соответствующих переменных целевой функции двойственной задачи, и наоборот;

6) если на переменную прямой задачи наложено условие неотрицательности, то соответствующее ограничение двойственной задачи записывается как ограничение-неравенство, если же нет, то как ограничение-равенство;

7) если какое-либо ограничение прямой задачи записано как равенство, то на соответствующую переменную двойственной задачи условие неотрицательности не налагается.

Транспонируем матрицу исходной задачи:

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

Решение двойственной задачи ЛП

Соответствие между переменными исходной и двойственной задачи:

На основании симплексной таблицы получено следующее решение двойственной задачи линейного программирования (выписываем из нижней строки):

Таким образом, наиболее дефицитным является ресурс первого вида. Его оценка максимальна и равна . Ресурс третьего вида является избыточным -его двойственная оценка равна нулю . Каждая дополнительно проданная единица товара 2-й группы будет снижать оптимальную прибыль на
Рассмотрен графический метод решения задачи линейного программирования (ЗЛП) с двумя переменными. На примере задачи приведено подробное описание построения чертежа и нахождения решения.

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

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