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

Содержание

Двойственный симплексный метод
Алгоритм двойственного симплекс-метода
Пример решения Р-методом
Алгоритм двойственного симплекс метода

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

Двойственный симплексный метод основан на теории двойственности (см. решение двойственной задачи) и используется для решения задач линейного программирования, свободные члены которых b_i могут принимать любые значения, а система ограничений задана неравенствами смысла «≤», «≥» или равенством «=».

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

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

Экстремум функции двух переменных

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

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

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

Алгоритм двойственного симплекс-метода

Пример решения Р-методом

Условие задачи. Предприятию необходимо выпустить по плану продукции А₁– 500 единиц, А₂– 300 единиц, А₃– 450 единиц. Каждый вид изделия может производиться на двух машинах.
Как распределить работу машин, чтобы общие затраты времени на выполнение плана были минимальны? Дана матрица затрат и ресурс времени каждой машины. Записать модель исследуемой операции в форме, допускающей использование P – метода.

Матрица затрат времени на производство видов продукции g – го вида A=(a_ig)
Машины	Виды продукции			Ресурс времени машин
Машины	А₁	А₂	А₃	Ресурс времени машин
1	2	3	3	1500
2	5	4	1	1000
План выпуска продукции	500	300	450

Составим математическую модель задачи.
2x₁₁+ 3x₁₂+3x₁₃≤ 1500
5x₂₁+ 4x₂₂+x₂₃≤ 1000
x₁₁+ x₂₁≥ 500
x₁₂+ x₂₂≥ 300
x₁₃+ x₂₃≥ 450
Целевая функция:
2x₁₁+ 3x₁₂+3x₁₃+ 5x₂₁+ 4x₂₂+x₂₃→ min
Запишем в виде, решаемом Р-методом.
2x₁₁+ 3x₁₂+3x₁₃≤ 1500
5x₂₁+ 4x₂₂+x₂₃≤ 1000
-x₁₁ -x₂₁≤ -500
-x₁₂-x₂₂≤ -300
-x₁₃-x₂₃≤ -450
Определим минимальное значение целевой функции F(X) = 2x₁+3x₂+3x₃+5x₄+4x₅+x₆при следующих условиях-ограничений.
2x₁+3x₂+3x₃≤1500
5x₄+4x₅+x₆≤1000
-x₁-x₄≤-500
-x₂-x₅≤-300
-x₃-x₆≤-450
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
2x₁+ 3x₂+ 3x₃+ 0x₄+ 0x₅+ 0x₆+ 1x₇+ 0x₈+ 0x₉+ 0x₁₀+ 0x₁₁= 1500
0x₁+ 0x₂+ 0x₃+ 5x₄+ 4x₅+ 1x₆+ 0x₇+ 1x₈+ 0x₉+ 0x₁₀+ 0x₁₁= 1000
-1x₁+ 0x₂+ 0x₃-1x₄+ 0x₅+ 0x₆+ 0x₇+ 0x₈+ 1x₉+ 0x₁₀+ 0x₁₁= -500
0x₁-1x₂+ 0x₃+ 0x₄-1x₅+ 0x₆+ 0x₇+ 0x₈+ 0x₉+ 1x₁₀+ 0x₁₁= -300
0x₁+ 0x₂-1x₃+ 0x₄+ 0x₅-1x₆+ 0x₇+ 0x₈+ 0x₉+ 0x₁₀+ 1x₁₁= -450
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

2	3	3	0	0	0	1	0	0	0	0
0	0	0	5	4	1	0	1	0	0	0
-1	0	0	-1	0	0	0	0	1	0	0
0	-1	0	0	-1	0	0	0	0	1	0
0	0	-1	0	0	-1	0	0	0	0	1

Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Решим систему уравнений относительно базисных переменных:
x₇, x₈, x₉, x₁₀, x₁₁,
Полагая, что свободные переменные равны 0, получим первый опорный план:
X1 = (0,0,0,0,0,0,1500,1000,-500,-300,-450)

План	Базис	В	x₁	x₂	x₃	x₄	x₅	x₆	x₇	x₈	x₉	x₁₀	x₁₁
0	x₇	1500	2	3	3	0	0	0	1	0	0	0	0
	x₈	1000	0	0	0	5	4	1	0	1	0	0	0
	x₉	-500	-1	0	0	-1	0	0	0	0	1	0	0
	x₁₀	-300	0	-1	0	0	-1	0	0	0	0	1	0
	x₁₁	-450	0	0	-1	0	0	-1	0	0	0	0	1
Индексная строка	F(X0)	0	-2	-3	-3	-5	-4	-1	0	0	0	0	0
θ			2			5

Посмотреть все итерации Оптимальный план можно записать так: x₅ = 133.33, x₈ = 16.67, x₁ = 500, x₂ = 166.67, x₆ = 450
F(X) = 2*500 + 3*166.67 + 4*133.33 + 1*450 = 2483.33 Пример №1 . Предприятию необходимо выпустить по плану продукции, не менее, чем: А 1 — 500 единиц, А2 – 300 единиц, А 3 – 450 единиц. Каждый вид изделия может производиться на двух машинах. Как распределить работу машин, чтобы общие затраты времени на выполнение плана были минимальными, если задана матрица затрат. Ресурс времени каждой машины приведен справа от таблицы. Записать модель исследуемой операции в форме, допускающей использование Р-метода. Решить задачу Р-методом. Пример №2 . Из 4 видов кормов необходимо составить рацион, в состав которого должно входить не менее в1 ед. вещества А, в 2 ед. вещества В и в 3 ед. вещества С. Количество единиц вещества, содержащегося в 1 кг корма каждого вида, указано в соответствующей таблице. В ней же приведена цена 1 кг корма каждого вида.
Составить рацион, содержащий не менее нужного количества указанных питательных веществ и имеющий минимальную стоимость.

Источник

Алгоритм двойственного симплекс метода

Шаг 2. Просмотреть столбец свободных членов текущей таблицы (кроме элемента в строке целевой функции).

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

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

Шаг 3. Просмотреть разрешающую строку текущей таблицы (кроме элемента в столбце свободных членов)

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

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

Шаг 4. Выполнить симплексное преобразование текущей таблицы с разрешающим элементом, выбранным на шаге 3б); объявить полученную таблицу и соответствующий базисный план текущими.

Шаг 5. Перейти к шагу 2.

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

Пример 18. Решить задачу ЛП

Решение. Здесь нет «очевидных» начальных базисных переменных для применения обычного симплекс-метода; чтобы найти начальную таблицу, пришлось бы предварительно решить вспомогательную задачу (см. п. 5). Заметим, что выражение F содержит только две переменные, , причем обе сотрицательными коэффициентами, -3 и -2. Выбрав за свободные ( тогда

— базисные), получим симплексную таблицу удовлетворяющую условию оптимальности – элементами строкиF будут положительные числа 3 и 2. Чтобы найти остальные элементы , надо разрешать систему ограничений относительно

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

Выполнив симплексное преобразование , получим таблицу.

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

— единственный оптимальный план ,

Типичными примерами задач с очевидной начальной таблицей для двойствен ного симплекс-метода являются задача о диете (7) – (9) и задача о раскрое.

Пример 19. Листы материала размером надо раскроить так, чтобы получились заготовки двух типов: 800 штук заготовок размероми 400 штук заготовок размеромКак получить необходимое число заготовок с минимальным расходом материала?

Решение. В условиях задачи способ раскроя листа полностью определяется парой чисел гдеколичества получающихся заготовок размеровисоответственно. Для получения необходимого числа заготовок из минимального числа листов можно использовать только «не улучшаемые» способы раскроя, т. е. такие, для которых раскрои виданевозможны. Легко проверяется, что таких способов раскроя имеется всего четыре: (3, 1), (2, 6), (1,9) и (0, 13),

Пусть число листов, раскроенных этими четырьмя способами. Тогдарасход материала (в листах), аи

— количества полученных заготовок размеров иМоделью задачи о раскрое будет следующая задача ЛП:

Каноническая форма этой задачи имеет вид

Таблица с базисными переменнымиудовлетворяет условию оптимальности и применение двойственного симплекс-метода дает цепочку таблиц

число заготовок можно получить из 275 листов, раскроив 250 из них первым способом и 25 – вторым способом.

В заключение выясним экономический смысл оптимальных значений переменных двойственной задачи (31) – (33) в случае, когда прямая задача (14) – (17) рассматривается как модель задачи о ресурсах. Напомним, что в этом случае правые части ограничений прямой задачи (эти же числа – коэффициенты целевой функциидвойственной задачи) представляют собой запасы ресурсов, а величинамаксимально возможный доход от реализации всей произведенной продукции. Предположим, чтоединственный оптимальный план двойственной задачи. Из первой теоремы двойственности следует, что

В примере 21 следующего п.7 будет показано, что остается единственным оптимальным планом задачи, двойственной к задаче о ресурсах с измененными запасами если приращения запасовдостаточно малы. Максимальным значением дохода будет величина

Из последнего равенства видно, что при малые изменения запасаi-го ресурса не меняют величину максимального дохода такие ресурсы называютсянедефицитными. Ресурсы, для которых , называютсядефицитными — увеличение (уменьшение) из запасов увеличивает (уменьшает) доход Числаопределяют скорость возрастанияпри увеличении соответствующего запаса и называютсяценностями или теневыми ценами ресурсов в данных условиях производства; задача, двойственная к задаче о ресурсах, называется задачей о ценности ресурсов.

Используя понятие дефицитности и теневых цен ресурсов, можно дать экономическое истолкование постановке двойственной задачи (31) – (33) и утверждениям теорем двойственности. В частности, вторая группа уравнений теоремы 2 означает, что дефицитные ресурсы в оптимальных планах производства расходуются полностью, а все ресурсы, которые расходуются не полностью, являются недефицитными.

Пример 20. Построить модель задачи о ценности ресурсов для задачи о ресурсах из примера 11. Найти ценности и определить статус (дефицитные, недефицитные) ресурсов, указать самый ценный ресурс.

Решение. Моделью задачи о ценности ресурсов является задача ЛП, двойственная к модели самой задачи о ресурсах. Условие этой задачи записано в примере15. Ценности ресурсов, т. е. компоненты оптимального плана двой-

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