Этапы решения задач с помощью симплекс-метода с естественным базисом

 

1. Привести задачу к канонической форме (знаки «=» в функциональных ограничениях и х_i ≥ 0).

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

3. Проверить допустимое решение на оптимальность с помощью симплекс-разности: Δ_j = Σ c_ia_ij - с_j.

Если для всех векторов Δ_j ≥ 0, то решение оптимально.

4. Если решение неоптимальное, то в него вводим вектор (А_к), дающий минимальную величину симплекс-разности Δ_к (к - номер разрешающего столбца).

Если все компоненты вводимого в базис вектора ≤ 0, то задача решений не имеет.

5. Определить вектор (А_r), который должен быть выведен из базиса, для этого вычислить отношение Q = min  = , где  ≥ 0, (r – номер разрешающей строки).

Элемент а _rk – разрешающий элемент.

6. Пересчитать элементы матрицы функциональных ограничений по формулам:

 →                                   →

                                          

→                      →

(Проиллюстрировать правило прямоугольника.)

 

Примечание. Для использования приведенной процедуры к минимизации линейной функции f (x₁,x₂,…, x_n) следует искать максимум     «-f(x₁,x₂,…, x_n)», затем полученный максимум взять с противоположным знаком. Оптимальное решение то же.

 

Пример. Получить решение по модели: 

 

 

1 этап. Эта задача (модель) линейного программирования, приведем ее к каноническому виду путем введения дополнительных переменных x ₃ и x₄:

               

2 этап.

Запишем матрицу коэффициентов функциональных ограничений.

 

 

КЗЛП имеет необходимое число единичных столбцов, т.е. обладает очевидным начальным опорным планом (0,0,300,150).

3 этап. Проверяется оптимальность полученного плана.

Расчеты  оформляются в симплекс-таблицах:

№	Базис	сi Сj	В план	2	3	0	0	Q
				А1	А2	А3	А4
	А3	0	300	1	3	1	0
0	А4	0	150	1	1	0	1
	Δ		0	-2	-3	0	0

 

Т.к. среди симплекс-разностей есть отрицательные, то полученный план не оптимален.

4 этап. Т.к. минимальная величина симплекс-разности соответствует вектору А₂, то он войдет в базис.

Второй столбец – разрешающий.

Этап.

Считаем величину Q.         Q = min  = , где  ≥ 0,

№	Базис	сi Сj	В план	2	3	0	0	Q
				А1	А2	А3	А4
	←А3	0	300	1	3	1	0	100
0	А4	0	150	1	1	0	1	150
	Δ		0	-2	-3	0	0

 

Т.к. минимальная величина Q соответствует вектору А₃, то выйдет из базиса вектор А₃. Первая строка - разрешающая. Элемент а₁₂ – разрешающий элемент.

 6 этап. Пересчитываем  элементы матрицы функциональных ограничений по формулам:

            

    

 

№	Базис	сi Сj	В план	2	3	0	0	Q
				А1	А2	А3	А4
	←А3	0	300	1	3	1	0	100
0	А4	0	150	1	1	0	1	150
	Δ		0	-2	-3	0	0
	А2	3	100	1/3	1	1/3	0	300
I	←А4	0	50	2/3	0	-1/3	1	75
	Δ		300	-1	0	1	0

Далее повторяем этапы 2-6 до получения оптимального решения.

 

№	Базис	сi  Сj	В план	2	3	0	0	Q
				А1	А2	А3	А4
	←А3	0	300	1	3	1	0	100
0	А4	0	150	1	1	0	1	150
	Δ		0	-2	-3	0	0
	А2	3	100	1/3	1	1/3	0	300
I	←А4	0	50	2/3	0	-1/3	1	75
	Δ		300	-1	0	1	0
	А2	3	75	0	1	1/2	-1/2
II	А1	2	75	1	0	-1/2	3/2
	Δ		375	0	0	1/2	3/2

 

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

 Оптимальные значения переменных равны: x1*=75, x2* =75 (основные переменные), x3*= 0, x4*= 0 (дополнительные переменные). Максимальное значение целевой функции равно 375.

 

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

 Этот метод заключается в применении правил симплекс-метода к так называемой М-задаче.

Она получается из исходной:

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

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

 

В полученной задаче первоначальный опорный план очевиден.

Как решать М-задачу: обычным симплекс-методом, но

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

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

Пример.

Решить ЗЛП по модели:

min f(х) = 10х₁ – 5х₂

2х₁ – х₂ ≥ 3

х₁ + х₂ ≥ 2

х₁ + 2х₂ ≥ -1

х_1,2  ≥ 0.

 1 этап. Эту ЗЛП приведем к каноническому виду и одновременно перейдем к задаче «на максимум».

max (- 10х₁ + 5х₂)

2х₁ – х₂ –х₃ = 3

х₁ + х₂  - х₄  = 2

-х₁ - 2х₂  + х₅  = 1

х_1,2,3,4,5  ≥ 0.

 

2 этап.

Запишем матрицу коэффициентов функциональных ограничений.

А₁  А₂ А₃   А₄ А₅

Если умножить на «-1» 1 и 2 строки, то станут отрицательными правые части (а это недопустимо)

Для нахождения опорного плана переходим к М - задаче: вводим искусственные единичные вектора в матрицу

А₁  А₂ А₃   А₄ А₅ Р₁   Р₂

Изменяем целевую функцию.

max (- 10х₁ + 5х₂ – Му₁ - Му₂)

Дальнейшее решение проводим в симплекс-таблицах:

 

 

Номер симплекс-таблицы	Базис	Сj   Сi	В	-10	5	0	0	0	-М	-М	Q
				А1	А2	А3	А4	А5	Р1	Р2
0	←Р1 Р2 А5	-М -М 0	3 2 1	2 1 -1	-1 1 -2	-1 0 0	0 -1 0	0 0 1	1 0 0	0 1 0	3/2 2 -
-	∆	-	-	-3М+10	-5	М	М	0	0	0	-
I	А1 ←Р2 А5	-10 -М 0	3/2 1/2 5/2	1 0 0	-1/2 3/2 -5/2	-1/2 1/2 -1/2	0 -1 0	0 0 1		0 1 0	- 1/3 -
-	∆	-		0	-3М/2	-М/2+5	М	0		0	-
II	А1 А2 А5	-10 5 0	5/3 1/3 10/3	1 0 0	0 1 0	-1/3 1/3 0	-1/3 -2/3 -5/3	0 0 1
-	∆	-	-	0	0	5	0	0			-

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

Особые случаи решения ЗЛП

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

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

 

 

2.1.6 Двойственность в линейном программировании, свойства двойственных оценок и их использование в анализе оптимального плана

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

Актуальность темы: Для чего составляют и решают двойственные задачи? – для того, чтобы провести анализ решения исходной задачи, а именно, ответить на следующие вопросы:

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

2. Как изменится прибыль при изменении запаса ресурсов?

3. Каковы нормы заменяемости ресурсов  (не абсолютные, а относительные, т.е. рассматриваемые с точки зрения конечного эффекта)?

4. Выгодно или нет вводить в план производства новые изделия?

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

Заметим, что 2-ая задача контрольной работы – задача, решаемая с использованием теории двойственности.

Ранее была рассмотрена задача ЛП об использовании ограниченных ресурсов (Тема 1.).

Запишем модель задачи ЛП в общем виде для для m- видов сырья и n- видов продукции.

Назовем ее задача I (исходная). Рядом запишем модель двойственной задачи.

 

 

Задача I (исходная)

Задача II (двойственная)

F = c1x1 + c2x2 +…+ cnxn → max при ограничениях: a11x1 + a12x2 + …+ a1nxn ≤ b1, a21x1 + a22x2 + …+ a2nxn ≤ b2, ……………………………… am1x1 + am2x2 + …+ amnxn ≤ bm, x1, …,n ≥ 0 Составить такой план выпуска продукции X=(x1,x2,…,xn), при котором прибыль от реализации продукции будет максимальной при условии, что потребление ресурсов по каждому виду продукции не превзойдет имеющихся запасов.

Z = b1y1 + b2y2 +…+ bmym → min при ограничениях: a11y1 + a21y2 + …+ am1ym ≥ c1, a12y1 + a22y2 + …+ am2ym ≥ c2, ……………………………… a1ny1 + a2ny2 + …+ amnym ≥ cn, y1, …,m ≥ 0  Найти такой набор цен (оценок) ресурсов Y=(y1,y2,…,ym), при котором общие затраты на ресурсы будут минимальными при условии, что выручка от продажи ресурсов будет не меньше той суммы, которую предприятие может получить при переработке сырья в готовую продукцию. .

 

Экономическая интерпретация прямой задачи следующая: составить такой план выпуска продукции X=(x₁,x_2,…,x_n), при котором прибыль от реализации продукции будет максимальной при условии, что потребление ресурсов по каждому виду продукции не превзойдет имеющихся запасов.

Рассмотрим экономическую интерпретацию двойственной задачи.

Предположим, что некоторая организация решила закупить ресурсы S₁,S₂,…,S_m предприятия и необходимо установить оптимальные цены на эти ресурсы: обозначим их y₁,y₂,…,y_m.

1) Покупающая организация заинтересована в том, чтобы затраты на все ресурсы Z были минимальны: Z = b₁y₁ + b₂y₂ +…+ b_my_m → min

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

Запишем это условие отдельно для каждого вида продукции:

a₁₁y₁ + a₂₁y₂ + …+ a_m1y_m ≥ c₁,- для первого вида продукции (выручка от продажи сырья, необходимого для производства единицы продукции первого вида, должна быть больше или равна прибыли от реализации единицы продукции первого вида)

a₁₂y₁ + a₂₂y₂ + …+ a_m2y_m ≥ c₂, - для второго вида продукции

………………………………

a_1ny₁ + a_2ny₂ + …+ a_mny_m ≥ c_n, - для n-ого вида продукции.

 

3) В результате учета интересов двух сторон (покупателя и продавца) мы получаем вторую задачу: Найти такой набор цен (оценок) ресурсов Y =(y _1, y ₂,…, y_m), при котором общие затраты на ресурсы будут минимальными при условии, что выручка от продажи ресурсов будет не меньше той суммы, которую предприятие может получить при переработке сырья в готовую продукцию.

 

Цены ресурсов y₁,y₂,…,y_m  в экономической литературе получили различные названия: учетные, неявные, теневые. Смысл этих названий состоит в том, что это условные, «ненастоящие» цены, определяемые в результате решения задачи. Поэтому их чаще называют оценками ресурсов.