Двойственный симплекс метод онлайн с подробным решением. Двойственный симплексный метод

Рассмотрим симплекс -метод для решения задач линейного программирования (ЛП). Он основан на переходе от одного опорного плана к другому, при котором значение целевой функции возрастает.

Алгоритм симплекс-метода следующий:

1. Исходную задачу переводим в канонический вид путем введения дополнительных переменных. Для неравенства вида ≤ дополнительные переменные вводят со знаком (+ ), если же вида ≥ то со знаком (— ). В целевую функцию дополнительные переменные вводят с соответствующими знаками с коэффициентом, равным 0 , т.к. целевая функция не должна при этом менять свой экономический смысл.
2. Выписываются вектора P i из коэффициентов при переменных и столбца свободных членов. Этим действием определяется количество единичных векторов. Правило – единичных векторов должно быть столько, сколько неравенств в системе ограничений.
3. После этого исходные данные вводятся в симплекс-таблицу. В базис вносятся единичные вектора, и исключая их из базиса, находят оптимальное решение . Коэффициенты целевой функции записывают с противоположным знаком.
4. Признак оптимальности для задачи ЛП – решение оптимально, если в f – строке все коэффициенты положительны. Правило нахождения разрешающего столбца – просматривается f – строка и среди ее отрицательных элементов выбирается наименьшее. Вектор P i его содержащий становится разрешающим. Правило выбора разрешающего элемента – составляются отношения положительных элементов разрешающего столбца к элементам вектора Р 0 и то число, которое дает наименьшее отношение становится разрешающим элементом, относительно которого будет произведен пересчет симплекс-таблицы. Строка, содержащая этот элемент называется разрешающей строкой. Если в разрешающем столбце нет положительных элементов, то задача не имеет решения. После определения разрешающего элемента переходят к пересчету новой симплекс – таблицы.
5. Правила заполнения новой симплекс – таблицы. На месте разрешающего элемента проставляют единицу, а другие элементы полагают равными 0 . Разрешающий вектор вносят в базис, из которого исключают соответствующий нулевой вектор, а остальные базисные вектора записывают без изменений. Элементы разрешающей строки делят на разрешающий элемент, а остальные элементы пересчитывают по правилу прямоугольников.
6. Так поступают до тех пор, пока в f – строке все элементы не станут положительными.

Рассмотрим решение задачи с использованием рассмотренного выше алгоритма.
Дано:

Приводим задачу к каноническому виду:

Составляем вектора:

Заполняем симплекс – таблицу:

:
Пересчитаем первый элемент вектора Р 0 , для чего составляем прямоугольник из чисел: и получаем: .

Аналогичные расчеты выполним для всех остальных элементов симплекс – таблицы:

В полученном плане f – строка содержит один отрицательный элемент – (-5/3), вектора P 1 . Он содержит в своем столбце единственный положительный элемент, который и будет разрешающим элементом. Сделаем пересчет таблицы относительно этого элемента:

Отсутствие отрицательных элементов в f – строке означает, что найден оптимальный план :
F* = 36/5, Х = (12/5, 14/5, 8, 0, 0).

• Ашманов С. А. Линейное программирование, М: Наука, 1998г.,
• Вентцель Е.С. Исследование операций, М: Советское радио, 2001г.,
• Кузнецов Ю.Н., Кузубов В.И., Волошенко А.Б. Математическое программирование, М: Высшая школа, 1986г.

Решение линейного программирования на заказ

Заказать любые задания по этой дисциплине можно у нас на сайте. Прикрепить файлы и указать сроки можно на

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

(54)

при условиях

(55)

(56)

где

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

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

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

Определение 14.

Решение системы линейных уравнений (55), определяемое базисом , называется псевдопланом задачи (54) – (56), если для любого

Теорема 11.

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

Теорема 12.

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

Сформулированные теоремы дают основание для построения алгоритма двойственного симплекс-метода.

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

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

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

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

1. Находят псевдоплан задачи.

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

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

4. Находят новый псевдоплан и повторяют все действия начиная с этапа 2.

Таблица 15

Пример 17.

Найти максимальное значение функции при условиях

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

Умножим второе и третье уравнения системы ограничений последней задачи на –1 и перейдем к следующей задаче: найти максимум функции

(57)

при условиях

(58)

(59)

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

(60)

при условиях

(61)

(62)

Выбрав в качестве базиса векторы и , составим симплексную таблицу (табл. 16) для исходной задачи (57) – (59).

Таблица 16

i	Базис	С б	Р 0
				P 1	P 2	P 3	p 4	p 5
	p 3 P 4 p 5		–4 –6	–1 –1	–2

Из этой таблицы видим, что планом двойственной задачи (57) – (59) является . При этом плане Т ак как в столбце вектора Р 0 таблица 16 имеются два отрицательных числа (–4 и –6), а в 4–й строке отрицательных чисел нет, то в соответствии с алгоритмом двойственного симплекс–метода переходим к новой симплекс–таблице. (В данном случае это можно сделать, так как в строках векторов Р 4 и Р 5 имеются отрицательные числа. Если бы они отсутствовали, то задача была бы неразрешима. Вектор, исключаемый из базиса, определяется наибольшим по абсолютной величине отрицательным числом, стоящим в столбце вектора Р 0 . В данном случае это число –6. Следовательно, из базиса исключаем вектор Р 5 . Чтобы определить, какой вектор необходимо ввести в базис, находим где Имеем

Значит, в базис вводим вектор P 2 . Переходим к новой симп екс–таблице (табл. 17).

Таблица 17

i	Базис	С б	Р 0
				P 1	P 2	P 3	p 4	p 5
	p 3 P 4 p 2		–7	–3/2				–1/2

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

Так как в столбце вектора Р 0 таблицы 17 стоит отрицательное число –7, то рассмотрим элементы 2–й строки. Среди этих чисел есть одно отрицательное –3/2. Если бы такое число отсутствовало, то исходная задача была бы неразрешима. В данном случае переходим к новой симплекс-таблице (табл. 18).

Таблица 18

i	Базис	С б	Р 0
				P 1	P 2	P 3	p 4	p 5
	p 3 P 1 p 2		14/3 32/3				–2/3	–1/3 –1/3

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

Пример 18.

Найти максимальное значение функции при условиях

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

Взяв в качестве базиса векторы Р 3 , Р 4 и Р 5 , составляем симплекс-таблицу (табл. 19).

Таблица 19

i	Базис	С б	Р 0
				P 1	P 2	P 3	p 4	p 5
	p 3 P 4 p 5		–12 –18	–3	–1

В 4-й строке таблице 19 нет отрицательных чисел. Следовательно, если бы в столбце вектора Р 0 не было отрицательных чисел, то в таблице 19 был бы записан оптимальный план. Поскольку в указанном столбце отрицательные числа имеются и такие же числа содержатся в соответствующих строках, переходим к новой симплекс–таблице (таблица 20). Для этого исключим из базиса вектор Р 5 и введем в базис вектор Р 1 . В результате получим псевдоплан X=(6;0;-24;4)

Таблица 20

i	Базис	С б	Р 0
				P 1	P 2	P 3	p 4	p 5
	p 3 P 4 p 1		–24		–2/3			–1/3

Так как в строке вектора Р 3 нет отрицательных чисел, то исходная задача не имеет решения.

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

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

1) выбирают разрешающую строку по наибольшему по абсолютной величине отрицательному элементу столбца свободных членов;
2) выбирают разрешающий столбец по наименьшему по абсолютной величине отношению элементов L строки к отрицательным элементам разрешающей строки;
3) пересчитывают симплексную таблицу по правилам обычного симплекс-метода;
4) решение проверяют на оптимальность. Признаком получения допустимого оптимального решения является отсутствие в столбце свободных членов отрицательных элементов.
Замечания
1. Если в разрешающей строке нет ни одного отрицательного элемента, задача неразрешима.
2. Если ограничения задачи заданы неравенствами типа «≥», двойственный симплекс-метод позволяет избавиться от необходимости введения искусственных переменных.

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

L = x 1 + 4x 2 → min

Составляем исходную симплексную таблицу.

Баз.	x 1	x 2	x 3	x 4	x 5	x 6	x 7	Св.
x 4	-2	-3		1	0	0	0	-20
x 5	-5	1	-2	0	1	0	0	-12
x 6	1	2	-1	0	0	1	0	2
x 7	-1	4	-2	0	0	0	1	1
L	-1	-4	-1	0	0	0	0	0

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

Баз.	х 1	х 2	х 3	х 4	х 5	х 6	х 7	Св.
х 3			1		0	0	0	5
х 5			0		1	0	0	-2
х 6			0		0	1	0	7
х 7	0		0		0	0	1	11
L			0		0	0	0	5

Аналогично рассуждая, получим еще одну таблицу

Баз.	х 1	х 2	х 3	х 4	х 5	х 6	х 7	Св.
х 3	0		1			0	0
х 1	1		0			0	0
х 6	0		0			1	0
х 7	0		0		0	0	1	11
L	0		0			0	0

Отсутствие в столбце свободных членов отрицательных элементов свидетельствует о том, что получено оптимальное решение , .
Замечание . Если решение ЗЛП и недопустимо и неоптимально, то сначала получаем допустимое решение, используя алгоритм двойственного симплекс-метода, а затем по правилам обычного симплекс-метода получаем оптимальное решение.
Пример .
L = 5x 1 – x 2 – x 3 → max
или

Составляем исходную симплекс-таблицу

	x 1	x 2	x 3	x 4	x 5	x 6	x 7	Св.
x 4	0		-2	1	0	0	0	-9
x 5	1	-1	0	0	1	0	0	-1
x 6	-1	-1	3	0	0	1	0	-8
x 7	1	0	-1	0	0	0	1	4
L	-5	1	4	0	0	0	0	0

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

Баз.	x 1	x 2	x 3	x 4	x 5	x 6	x 7	Св.
x 2	0	1	2	-1	0	0	0	9
x 5	1	0	2	-1	1	0	0	8
x 6	-1	0	5	-1	0	1	0	1
x 7		0	-1	0	0	0	1	4
L	-5	0	2	1	0	0	0	-9

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

Баз.	x 1	x 2	x 3	x 4	x 5	x 6	x 7	Св.
x 2	0	1	2	-1	0	0	0	9
х 5	0	0	3	-1	1	0	-1	4
х 6	0	0		-1	0	1	1	5
x 1	1	0	-1	0	0	0	1	4
L	0	0	-3	1	0	0	5	11

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

БП

Симплексные отношения

8

6

4

0

0

0

0

520

16

18

9

1

0

0

65/2

0

140

7

7

2

0

1

0

20

0

810

9

2

1

0

0

1

90

0

-8

-6

-4

0

0

0

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

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

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

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

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

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

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

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

БП

Симплексные отношения

8

6

4

0

0

0

0

200

0

2

31/7

1

-16/7

0

1400/31

8

20

1

1

2/7

0

1/7

0

70

0

630

0

-7

-11/7

0

-9/7

1

-

160

0

2

-12/7

0

8/7

0

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

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

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

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

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

БП

Симплексные отношения

8

6

4

0

0

0

4

1400/31

0

14/31

1

7/31

-16/31

0

8

220/31

1

27/31

0

-2/31

9/31

0

0

21730/31

0

-195/31

0

11/31

-65/31

1

7360/31

0

86/31

0

12/31

8/31

0

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Так как есть три единичных вектора, то
можно сразу записать опорный план
Х=(0,0,0,360,192,180).
Составим нулевую симплекс-таблицу

Полученный опорный план проверяем
на оптимальность.
Вычисляем значение целевой функции и
симплекс-разности.
F0 c P0 0 360 0 192 0 180 0,
1 z1 c1 c P1 c1 9,
2 z2 c2 cP2 c2 10,...

Как видно из 0-й таблицы отличными от нуля
являются переменные x4 , x5 , x6 , а x , x , x
1
2
3
равны нулю, т.к. они небазисные, а свободные.
Дополнительные же переменные x4 , x5 , x6
принимают свои значения в соответствии с
ограничениями.
Эти значения переменных отвечают такому
«плану», при котором ничего не производится, сырье
не используется и значение целевой функции равно
нулю, т. е. стоимость произведенной продукции
отсутствует.
Такой план, конечно, не является оптимальным.
Это видно и из 4-й строки таблицы, в которой
имеется три отрицательных оценки -9, -16 и -10.

10.

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

11.

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

12.

Найдем число Q .
360 192 180
Q min
;
;
min 30; 24;60
3
12 8
Введем его в последний столбец таблицы.
Число 24 соответствует вектору P5 .
192/8=24 с экономической точки зрения
означает, какое количество изделий С
предприятие может изготовлять с учетом
норм расхода и имеющихся объемов сырья
каждого вида.

13.

Так как сырья каждого вида имеется
соответственно 360, 192 и 180 кг, а на одно
изделие С требуется затратить сырья каждого
вида 12, 8 и 3 кг, то максимальное число
изделий С, которое может быть изготовлено
предприятием равно
min{360/12,192/8,180/3}=192/8=24, т.е.
ограничивающим фактором для производства
изделий С является имеющийся объем сырья
2-го вида. С учетом его предприятие может
производить 24 изделия С.При этом сырье 2го вида будет полностью использовано и,
значит, вектор подлежит исключению из
P5
базиса.

14.

Составляем следующую таблицу. В ней
разрешающей является вторая строка,
а разрешающим столбцом –третий. На
их пересечении стоит элемент 8.
Разделим вторую строку на 8, а затем
обнулим по методу Жордана- Гаусса
или по формулам треугольника третий
столбец.

15.

16.

Подсчитаем симплекс-разности и заполним 4ю строку таблицы.
При данном плане производства
изготовляется 24 изделия С и остается
неиспользованным 72 кг сырья 1-го и 108 кг
сырья 3-го вида. 2-й вид сырья использован
полностью. Стоимость всей продукции при
этом плане составляет 384 д.е. Указанные
числа записаны в столбце План. Это опять
параметры задачи, но они претерпели
изменения. Изменились и данные других
столбцов. Их экономическое содержание
стало еще более сложным.

17.

Имеется одна отрицательная оценка -2.
План можно улучшить. Введем в базис
вектор P2 . Вычислим
72 24 108
Q min ;
;
min 8; 48;72 8.
9 1/ 2 3 / 2
.
Выводим из базиса P4 .

18.

Разрешающими будут 1-я строка и 2-й
столбец. Разрешающий элемент 9.
Разделим на 9 1-ю строку, заполним
1-ю строку новой таблицы, затем
обнулим 2-й столбец. Для этого
умножим 1-ю строку на (-1/2) и
прибавим ко 2-й, а затем умножим 1-ю
строку на (-3/2) и прибавим к 3-й строке.
Заполним таблицу 2.

19.

20.

В этом мы убеждаемся,
вычисляя симплекс-разности
1 cP1 c1 10 1 16 0.25 9 5,
2 cP2 c2 10 1 16 0 10 0,
3 cP3 c3 10 0 16 1 0 0 16 0,
4 cP4 c4 10 1/ 9 16 1/ 8 0 (1/ 6) 2 / 9,
5 cP5 -c5 =10 (-1/6)+16 5/24+0(-1/2)=5/3,
6 0.

21.

Оптимальным планом производства не
предусмотрен выпуск изделий А. Введение в
план выпуска продукции вида А привело бы к
уменьшению указанной общей стоимости.
Это видно из 4-й строки столбца, где число 5
показывает, что при данном плане включение
в него выпуска единицы изделия А приводит
лишь к уменьшению общей величины
стоимости на 5 д.е.
Итак, план предусматривает выпуск 8 изделий
В и 20 изделий С. Сырье видов 1 и 2
используется целиком, а вида 3неиспользованным остается 96 кг.

22. ДВОЙСТВЕННЫЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Каждой ЗЛП можно поставить в соответствие
задачу, называемую двойственной к исходной
задаче.
Рассмотрим задачу об использовании
ресурсов. Предположим, что предприятие А
производит n видов продукции, величина
выпуска которых определяется переменными
x1 , x2 , ..., xn
.
В производстве используются m различных
видов ресурсов, объем которых ограничен
величинами b1 , b2 , ..., bn .

23.

Известны нормы затрат каждого ресурса на единицу
каждого вида продукции, образующие матрицу,
a11
a21
A
...
am1
a12
a22
...
am 2
... a1n
... a2 n
... ...
... amn
а также стоимость единицы продукции каждого вида
c1 , c2 , ..., cn
Требуется организовать производство так, чтобы
предприятию А была обеспечена максимальная
прибыль.

24.

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

25.

В математической форме задача
записывается следующем виде:
F c1 x1 c2 x2 ... c j x j ... cn xn max
при условиях
a11 x1 a12 x2 ... a1 j x j ... a1n xn b1 ,
a21 x2 a22 x2 ... a2 j x j ... a2 n xn b2 ,
.
...............................................................,
a x a x ... a x ... a x b
mj j
mn n
m
m1 1 m 2 2
x j 0, j 1, n.

26.

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

27.

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

28.

т.е.какова должна быть оценка единицы
каждого из ресурсов y1 , y2 , ..., yn ,
чтобы при заданных объемах
имеющихся ресурсов bi , при заданных
стоимостях c j (j 1, n) единицы
продукции и нормах расходов aij
минимизировать общую оценку затрат
на всю продукцию.

29. Мат. модель двойственной задачи

В математической форме задача
записывается в виде:
*
F b1 y1 b2 y2 ... bm ym min
при ограничениях
a11 y1 a21 y2 ... am1 ym c1 ,
a y a y ... a y c ,
m2 m
2
12 1 22 2
..................................................
a y a y ... a y c ,
mn m
n
1n 1 2 n 2
yi 0, i 1, 2,..., m.

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

Переменные yi двойственной задачи в литературе
могут иметь различные названия:учетные, неявные,
теневые, объективно обусловленные оценки,
двойственные оценки или «цены» ресурсов.
Эти две задачи образуют пару взаимно
двойственных задач, любая из которых может
рассматриваться как исходная. Решение одной
задачи дает оптимальный план производства
продукции, а решение другой – оптимальную
систему оценок сырья, используемого для
производства этой продукции.

31.

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

32.

в каждой задаче система ограничений задается в
виде неравенств, причем, в задаче на отыскание
максимума, все неравенства вида «≤», а в задаче на
отыскание минимума, все неравенства вида «≥»;
матрица коэффициентов системы ограничений
получается одна из другой путем транспонирования;
каждому ограничению одной задачи соответствует
переменная другой задачи, номер переменной
совпадает с номером ограничения;
условия не отрицательности переменных
сохраняются в обеих задачах;

33. Решение симметричных двойственных задач

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

34. Экономическое содержание первой теоремы двойственности

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

35. Метод одновременного решения пары двойственных задач

Исходная задача: Двойственная задача:
F c1x1 c2 x2 ... c j x j ... F * b1 y1 b2 y2 ...
cn xn max
a11 x1 a12 x2 ... a1n xn xn 1 b1 ,
a21 x1 a22 x2 ... a2 n xn xn 2 b2 ,
..........................................................
a x a x ... a x x b ,
mn n
n m
m
m1 1 m 2 2
x j 0, j 1, 2,..., n m.
bm ym min,
a11 y1 a21 y2 ... am1 ym ym 1 c1 ,
a y a y ... a y y c ,
m2 m
m 2
2
12 1 22 2
.............................................................
a y a y ... a y y c ,
mn m
m n
n
1n 1 2 n 2
yi 0, i 1, 2,..., m n.

36.

Число переменных в задачах одинаково
и равно m + n. В исходной задаче
базисными переменными являются

переменные xn 1 , xn 2 , ..., xn m
,
а в двойственной задаче –
вспомогательные неотрицательные
переменные yn 1 , yn 2 , ..., yn m .
Базисным переменным одной задачи
соответствуют свободные переменные
другой задачи, и наоборот.

37.

38.

При решении ЗЛП табличным симплексметодом решение двойственной задачи
содержится в последней строке таблицы.
Это j.
Причем основные переменные двойственной

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

39. Пример.

Сформулируем модель задачи, двойственной
к задаче из примера 2 (начало лекции):
Найти максимум функции

40.

41.

Переменные исходной задачи x1 , x2 , x3 это количество изделий А,В и С. Введем
переменные двойственной задачи y1 , y2 , y3
Найти минимум функции
F * 360 y1 192 y2 180 y3 min
при ограничениях
18 y1 6 y2 5 y3 9,
15 y1 4 y2 3 y3 10,
12 y 8 y 3 y 16,
2
3
1
y1 , y2 , y3 0.

42. Рассмотрим последнюю таблицу исходной задачи

43.

Значение y1 в последней строке столбца P4 ,
т.е. y1 2 ;
9y 5
значение 2 3 в последней строке столбца P5,
значение y3 0 в последней строке столбца P6 .
Остальные значения находим в столбцах 1,2,3.
2 5
Y (; ;0;5;0;0)
9 3
При этом
2
5
F 360 192 180 0 0 5 0 0 0 0 400
9
3
*
-это минимальные затраты на всю продукцию.
2/9 и 5/3 –это теневые цены сырья 1-го и 2-го
видов соответственно.