Меню

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



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

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

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

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

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

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

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

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

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

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

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

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

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

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

Источник

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

Назначение сервиса . Сервис предназначен для онлайн решения задач линейного программирования (ЗЛП) симплекс-методом в следующих формах записи:

  • в виде симплексной таблицы (метод жордановых преобразований); базовой форме записи;
  • модифицированным симплекс-методом; в столбцовой форме; в строчечной форме.
  • Шаг №1
  • Шаг №2
  • Видеоинструкция
  • Оформление Word
  • Также решают

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

Объем товара Х (в партиях) Доход G(X)
1 2 3
1 28 30 32
2 41 42 45
3 50 55 48
4 62 64 60
5 76 76 72

Алгоритм симплекс-метода включает следующие этапы:

  1. Составление первого опорного плана. Переход к канонической форме задачи линейного программирования путем введения неотрицательных дополнительных балансовых переменных.
  2. Проверка плана на оптимальность. Если найдется хотя бы один коэффициент индексной строки меньше нуля, то план не оптимальный, и его необходимо улучшить.
  3. Определение ведущих столбца и строки. Из отрицательных коэффициентов индексной строки выбирается наибольший по абсолютной величине. Затем элементы столбца свободных членов симплексной таблицы делит на элементы того же знака ведущего столбца.
  4. Построение нового опорного плана. Переход к новому плану осуществляется в результате пересчета симплексной таблицы методом Жордана—Гаусса.
Базис B x1 x2 x3 x4 min
x3 20 5 2 1 20:5=4
x4 6 1 1 1 6:1=6
F(X1) -8 -5

Если необходимо найти экстремум целевой функции, то речь идет о поиске минимального значения ( F(x) → min , см. пример решения минимизации функции) и максимального значения ( F(x) → max , см. пример решения максимизации функции)

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

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

Суть симплекс-метода. Движение к точке оптимума осуществляется путем перехода от одной угловой точки к соседней, которая ближе и быстрее приближает к Xопт. Такую схему перебора точек, называемую симплекс-метод, предложил Р. Данцигом.
Угловые точки характеризуются m базисными переменными, поэтому переход от одной угловой точки к соседней возможно осуществить сменой в базисе только одной базисной переменной на переменную из небазиса.
Реализация симплекс-метода в силу различных особенностей и постановок задач ЛП имеет различные модификации.

Построение симплекс-таблиц продолжается до тех пор, пока не будет получено оптимальное решение.

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

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

Замечание 2 . Пусть в некоторой крайней точке все симплексные разности неотрицательные Dk³ 0 (k = 1..n+m),т.е. получено оптимальное решение и существует такой Аk – небазисный вектор, у которого Dk = 0. Тогда максимум достигается по крайней мере в двух точках, т.е. имеет место альтернативный оптимум. Если ввести в базис эту переменную xk, значение целевой функции не изменится.

Замечание 3 . Решение двойственной задачи находится в последней симплексной таблице. Последние m компонент вектора симплексных разностей( в столбцах балансовых переменных) – оптимальное решение двойственной задачи. Значение целевых функций прямой и двойственной задачи в оптимальных точках совпадают.

Замечание 4 . При решении задачи минимизации в базис вводится вектор с наибольшей положительной симплексной разностью. Далее применяется тот же алгоритм, что и для задачи максимизации.

Если задано условие «Необходимо, чтобы сырье III вида было израсходовано полностью», то соответствующее условие представляет собой равенство.

Аналитическое введение в симплекс-метод

Итак, если мы решаем ЗЛП в канонической форме, то система ограничений — это обычная система линейных уравнений. При решении задач ЛП получаются системы линейных уравнений, имеющие, как правило, бесконечно много решений.

Например, пусть дана система

Здесь число уравнений равно 2, а неизвестных — 3, уравнений меньше. Выразим x1 и x2 через x3 :

Это общее решение системы. если переменной x3 придавать произвольные числовые значения, то будем находить частные решения системы. Например, x3=1 → x1=1 → x2=6. Имеем (1, 6, 1) — частное решение. Пусть x3=2 → x1=-3, x2= 1, (-3, 1, 2) — другое частное решение. Таких частных решений бесконечно много.

Читайте также:  Html таблица текст стили

Переменные x1 и x2 называются базисными, а переменная x3не базисная, свободная.

Совокупность переменных x1 и x2 образует базис: Б (x1, x2). Если x3 = 0, то полученное частное решение (5, 11, 0) называется базисным решением, соответствующим базису Б (x1, x2).

Базисным называется решение, соответствующее нулевым значениям свободных переменных.
В качестве базисных можно было взять и другие переменные: (x1, x3) или (x2, x3).
Как переходить от одного базиса Б(x1, x2) к другому базису Б(x1, x3)?
Для этого надо переменную x3 перевести в базисные, а x2 — в небазисные т. е. в уравнениях надо x3 выразить через x2 и подставить в 1-е:

Базисное решение, соответствующее базису Б (x1, x3), таково: (-19/5; 0; 11/5).

Если теперь от базиса Б (x1, x3) нам захочется перейти к базису Б (x2, x3), то

Базисное решение, соответствующее базису Б (x2, x3): (0;19/4; 7/8).
Из трех найденных базисных решений решение, соответствующее базису Б (x1, x3) — отрицательное x1 Пример . Решить задачу ЛП.

Функцию F= x2x1 → min необходимо минимизировать при заданной системе ограничений:
-2x1 + x2 + x3 = 2
x1 + x2 + x5 = 5
x1 — 2x2 + x4 = 12
xi ≥ 0, i = 1, 5

Эти ограничения могут рассматриваться как произошедшие из неравенств, а переменные x3, x5, x4 — как дополнительные.
Запишем ограничения, выбрав базис из переменных Б< x3, , x4, x5>:

Этому базису соответствует базисное неотрицательное решение
x1 = 0, x2 = 0, x3 = 2, x4 = 2, x5 = 5 или (0, 0, 2, 2, 5).
Теперь нужно выразить F через небазисные переменные, в нашем случае это уже сделано: F= x2x1.
Проверим, достигла ли функция F своего минимального значения. Для этого базисного решения F= 0 — 0 = 0 — значение функции равно 0. Но его можно уменьшить, если x1 будет возрастать, т. к. коэффициент в функции при x1 отрицателен. Однако при увеличении x1 значения переменных x4, x5 уменьшаются (смотрите второе и третье равенство системы ограничений). Переменная x1 не может быть увеличена больше чем до 2, иначе x4 станет отрицательной (ввиду равенства 2), и не больше, чем до 5, иначе x5 — отрицателен. Итак, из анализа равенств следует, что переменную x1 можно увеличить до 2, при этом значение функции уменьшится.
Перейдем к новому базису Б2, введя переменную x1 в базис вместо x4.
Б2<x1, x3, x5>.
Выразим эти базисные переменные через небазисные. Для этого сначала выразим x1 из второго уравнения и подставим в остальные, в том числе и в функцию.

Имеем:

F = -2 — x2 + x4.
Базисное решение, соответствующее базису Б2<x1, x3, x5>, имеет вид (2, 0, 6, 0, 3), и функция принимает значение F= -2 в этом базисе.
Значение функции можно и дальше уменьшать, увеличивая x2. Однако, глядя на систему, x2 можно увеличивать лишь до 1, т. к. иначе из последнего равенства x5 = 3 — 3x2 + x4 следует, что при x2 > 1 x5 станет отрицательной. А у нас все переменные в ЗЛП предполагаются неотрицательными. Остальные уравнения системы не дают ограничений на x2. Поэтому увеличим x2 до 1, введя его в базис вместо x5: Б3<x1, x2, x3>.
Выразим x2 через x5 и подставим во все уравнения:

Базисное решение, соответствующее базису Б3<х1, х2, х3>, выписывается (4, 1, 9, 0, 0), и функция принимает значение F= -3. Заметим, что значение F уменьшилось, т. е. улучшилось по сравнению с предыдущим базисом.
Посмотрев на вид целевой функции , заметим, что улучшить, т. е. уменьшить значение F нельзя и только при x4 = 0, x5 = 0 значение F= -3. как только x4, x5 станут положительными, значение F только увеличится, т. к. коэффициенты при x4, x5 положительны. Значит, функция F достигла своего оптимального значения F* = -3. Итак, наименьшее значение F, равное -3, достигается при x1* = 4, x2* = 1, x3* = 9, x4* = 0, x5* = 0.

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

Источник

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

Пролог

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

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

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

Определение: Линейное программирование – математическая дисциплина, посвященная теории и методам решения экстремальных задач на множествах n- мерного пространства, задаваемых системами линейными уравнений и неравенств.

Общая задача линейного программирования (далее – ЛП) имеет вид:

image

§2. Каноническая форма задачи ЛП

Каноническая форма задачи ЛП:

image

Замечание: Любая задача ЛП сводится к канонической.

Алгоритм перехода от произвольной задачи ЛП к канонической форме:

  1. Неравенства с отрицательными $b_i$умножаем на (-1).
  2. Если неравенство вида (≤), то к левой части добавляем $s_i$– добавочную переменную, и получаем равенство.
  3. Если неравенство вида (≥), то из левой части вычитаем $s_i$, и получаем равенство.
  4. Делаем замену переменных:

  • Если $x_i ≤ 0$, то $x_i
  • Если $x_i$— любой, то $x_i= x_i, где $x_i

Замечание: Будем нумеровать $s_i$по номеру неравенства, в которое мы его добавили.

Замечание: $s_i$≥0.

§3. Угловые точки. Базисные/свободные переменные. Базисные решения

Определение: Точка $Х ∈ D$называется угловой точкой, если представление