5 М-метод и двухэтапный метод Двойственность в линейном программировании.

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

Два правила выбора вводимых и исключаемых переменных в симплекс-методе называются условием оптимальности и условием допустимости.

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

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

Последовательность действий в симплекс-методе:

Этап 0. Находится начальное допустимое базисное решение.

Этап 1. На основе условия оптимальности определяется вводимая переменная. Если вводимых переменных нет, вычисления заканчиваются.

Этап 2. На основе условия допустимости выбираются исключаемая переменная.

Этап 3. Вычисляется новое базисное решение. Переход к п.1.

 

Искусственное начальное решение.

 

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

 

М-метод.

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

Переменная R, с помощью достаточно большого положительного числа М штрафуется путем введения в целевую функцию выражения –MR₁,в случае максимизации и +MR₁ - в случае минимизации. Вследствие этого штрафа резонно предположить, что процесс оптимизации приведет к нулевому значению R₁.

 

Пример.

Минимизировать z=4x₁+x₂

                              3x₁+x₂=3

                              4x₁+3x₂6

                              x₁+2x₂ 4

                              x₁,x₂0

Приводим к стандартной форме:

z=4x₁+x₂min

3x₁+x₂=3

4x₁+3x₂-x₃=6

x₁+2x₂+x₄= 4

x₁,x₂,x₃,x₄0

Первое и второе уравнения не имеют дополнительных остаточных переменных, которые можно ввести в базисное решение. Поэтому введем в эти уравнения искусственные переменные R₁ и R₂, а в целевую функцию введем штраф MR₁+MR₂.

z=4x₁+x₂+ MR₁+MR₂

3x₁+x₂+R₁ =3

4x₁+3x₂-x₃+R₂=6

x₁+2x₂+x₄= 4

x₁,x₂,x₃,x₄,R₁,R₂0

 

Базис	x1	x2	x3	R1	R2	x4	Решение
z	-4	-1	0	-M	-M	0	0
R1	3	1	0	1	0	0	3
R2	4	3	-1	0	1	0	6
x4	1	2	0	0	0	1	4

 

Прежде чем применять симплекс-метод, надо согласовать Z-строку с остальной частью таблицы. Так Z, соответствующее начальному базисному решению R₁=3,R₂=6 и x₄=4 должно равняться 3М+6М+0=9М, а не 0. Коэффициенты при R₁ и R₂ надо сделать нулевыми. Для этого надо строки R₁ и R₂ (все элементы) умножить на М, а затем сложить эти строки с Z-строкой.

Новая Z-строка = Старая Z-строка + MR₁-строка + MR₂-строка.

 

Базис	x1	x2	x3	R1	R2	x4	Решение
z	-4+7М	-1+4М	-М	0	0	0	9М
R1	3	1	0	1	0	0	3
R2	4	3	-1	0	1	0	6
x4	1	2	0	0	0	1	4

 

Теперь Z=9M, что соответствует базисному решению R₁=3, R₂=6 и x₄=4.

Так как мы решаем задачу минимизации, выбираем наибольший положительный коэффициент в Z-строке. Об этом говорит сайт https://intellect.icu . Он равен -4+7М и соответствует переменной x₁, которая будет вводимой. Условие допустимости указывает, что R₁ – исключаемая.

 

Базис	x1	x2	x3	R1	R2	x4	Решение
z	0	(1+5M)/3	-М	(4-7M)/3	0	0	4+2M
x1	1	1/3	0	1/3	0	0	1
R2	0	5/3	-1	-4/3	1	0	2
x4	0	3/5	0	-1/3	0	1	3

 

Уже первая итерация исключила из базисного решения R₁ – это результат штрафа.

Следующими (вводимой и исключаемой переменной) будут x₂ и R₂ соответственно. И будет получено решение.

При использовании М-метода важны следующие обстоятельства:

1. Использование штрафа М может и не привести к исключению искусственной            переменной. (Например, если система ограничений несовместна).

2. Теоретически применение М-метода требует, чтобы M. Но с точки зрения          компьютерных вычислений М должна быть конечной, но достаточно большой.         Настолько большой, чтобы выполнять роль «штрафа», но не слишком большой,          чтобы не уменьшить точность вычислений.

 

Двухэтапный метод.

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

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

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

Пример (та же задача)

Этап 1. Минимизировать z=R₁+R₂

3x₁+x₂+R₁ =3

4x₁+3x₂-x₃+R₂=6

x₁+2x₂+x₄= 4

x₁,x₂,x₃,x₄,R₁,R₂0

Базис	x1	x2	x3	R1	R2	x4	Решение
r	-4	-1	0	-1	-1	0	0
R1	3	1	0	1	0	0	3
R2	4	3	-1	0	1	0	6
x4	1	2	0	0	0	1	4

 

Как и в М-методе сначала вычисляется новая r-строка:

Новая r-строка = Старая r-строка + 1R₁-строка + 1R₂-строка

Новая r-строка используется для решения задачи первого этапа.

 

Базис	x1	x2	x3	R1	R2	x4	Решение
r	0	0	0	-1	-1	0	0
x1	1	0	1/5	3/5	-1/5	0	3/5
x2	0	1	-3/5	-4/5	3/5	0	6/5
x4	0	0	1	1	-1	1	1

 

Достигнут минимум r=0, значит получено допустимое базисное решение x₁=3/5,x₂=6/5 и x₄=1. Искусственные переменные выполнили свою миссию, и их можно удалить.

 Далее выполняется Этап 2.

 

Двойственность в линейном программировании.

 

Каждой задаче ЛП можно поставить в соответствие так называемую двойственную задачу.

Задача ЛП в стандартной форме имеет вид:

Минимизировать или максимизировать

 

при ограничениях:

 

 

 

Правила формировании двойственной задачи:

1. Каждому из m ограничений прямой задачи соответствует переменная                            двойственной задачи

          2.Каждой из n переменных прямой задачи соответствует ограничение     

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

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

           4.Коэффициенты целевой функции двойственной задачи равны правым частям               ограничений прямой задачи.

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

Пример. Прямая задача

z=5x₁+12x₂+4x₃ max

x₁+2x₂+x₃10

2x₁-x₂+3x₃ = 8

x₁,x₂,x₃  0

Прямая задача в стандартной форме:

z=5x₁+12x₂+4x₃+0x₄  max

x₁+2x₂+x₃+x₄ = 10

2x₁-x₂+3x₃+0x₄ = 8

x₁,x₂,x₃,x₄ 0

Двойственные переменные:

w=10y₁+8y₂   min

y₁+2y₂ 5

2y₁-y₂ 12

y₁+3y₂ 4

 

y₁+0y₂0

y₁,y₂ – свободные     (y₁0, y₂ – свободная переменная)

 

Пример. Прямая задача

z=15x₁+12x₂  min

x₁+2x₂3

2x₁-4x₂ 5

x₁,x₂  0

Прямая задача в стандартной форме:

z=15x₁+12x₂+0x₃+0x₄  min

x₁+2x₂-x₃+0x₄ = 3

2x₁-4x₂+0x₃+x₄ = 5

x₁,x₂,x₃,x₄ 0

Двойственные переменные: y₁,y₂

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

w=3y₁+5y₂   max

y₁+2y₂ 15

2y₁-4y₂ 12

-y₁0 (или y10)

y₂0

y₁,y₂-свободные переменные.

 

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

 

Пусть задана задача оптимального распределения ресурсов. Ресурсы b₁,b₂..b_m могут использоваться для выпуска n видов продукции. Известны стоимость j-го вида продукта c_j (j=) и норма потребления i-го ресурса (i=) на производство единицы продукта j – a_ij. Требуется определить объем производства продукта каждого вида x_j (j=), максимизирующий доход

z=c₁x₁+c₂x₂+..+c_nx_n

Расход ресурсов не должен превышать их наличия:

 

a₁₁x₁+a₁₂x₂+..+a_1nx_nb₁

_{------------------------------------------}

a_i1x₁+a_i2x₂+..+a_inx_nb_i

_{------------------------------------------}

a_m1x₁+a_m2x₂+..+a_mnx_nb_m

 

Все переменные неотрицательны.

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

 

w=b₁y₁+b₂y₂+..+b_my_m min

a₁₁y₁+a₂₁y₂+..+a_m1y_mc₁

_{------------------------------------------}

a_1jy₁+a_2jy₂+..+a_mjy_mc_j

_{------------------------------------------}

a_1ny₁+a_2ny₂+..+a_mny_mc_n

y_i0, (i=)

Переменные y_i двойственной задачи отражают «ценность» i-го ресурса. В связи с этим переменные двойственной задачи называют теневыми ценами или скрытыми доходами (иногда симплексными мультипликаторами).

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

 

Основные теоремы двойственности.

 

Теорема 1. Если x₀ и y₀ – допустимые решения прямой и двойственной задач,     т.е.  Ax₀b и A^Ty₀c, то

c^Tx₀b^Ty₀,

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

Теорема 2 (основная теорема двойственности). Если x₀ и y₀ – допустимые решения прямой и двойственной задач и если  c^Tx₀=b^Ty₀, то x₀ и y₀ – оптимальные решения пары двойственных задач.

Именно эта теорема связывает оптимальные решения прямой и двойственной задач. Если в прямой задаче при малом количестве переменных имеется большое количество ограничений (m>n), выгоднее решать двойственную задачу.

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

Смысл таков : Если некоторый ресурс b_i имеется в избытке и i-е неравенство выполняется как строгое неравенство, то оно становится несущественным и оптимальная теневая цена такого ресурса равна нулю.

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

Дадим интерпретацию теоремы 4. Поскольку величины y_i(i=)- это цены соответствующих ресурсов, то  - это затраты на j-й технологический процесс. Теорема тогда означает следующее: если j-й технологический процесс оказывается невыгодным с точки зрения оптимальных цен ресурсов y_опт, то в оптимальном решении прямой задачи интенсивность такого технологического процесса должна быть равна нулю. Теорема 4 выражает принцип рентабельности оптимально функционирующей системы.

 

Решение задачи ЛП путем графического анализа двойственности.

z=-6x₁-12x₂+3x₃-x₄max

2x₁-4x₂+3x₃-x₄=6

-3x₁+3x₂+x₃=12

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

w=6u₁+12u₂min

2u₁-3u₂-6

-4u₁+3u₂-12

3u₁+u₂3

-u₁-1

u₁,u₂ –свободные

 

Область допустимых решений - . Оптимальное решение достигается в т.C(1,0) и w_min=6. Этим решением удовлетворяются как строгие равенства первое и второе ограничения (2-0=2>-6 и -4+0=-4>-12). Соответствующие им переменные прямой задачи равны нулю. Тогда

 

3x₃-x₄=6

x₃=12

Отсюда x₃=12, x₄=30. Решение прямой задачи x₀=(0,0,12,30).             z_max=312-130=6. Так как z_max=w_min=6, то вычисления выполнены верно.

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