Модифицированный симплекс-метод

(µ-метод).

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

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

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

Пример: Общая постановка задачи М-метода

Дано: m - количество типов судов; i - индекс типа судна;

    n - количество линий движения; j - индекс линии;

     - количество судов каждого типа;

     - грузооборот каждой линии за планируемый период;

     - провозная способность i-го типа судна на j-ой линии за                          планируемый период;

     - расходы i-го типа судна на j-ой линии за планируемый период.

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

              Сформулируем математическую постановку задачи       

    Искомая переменная -  - количество судов i-го типа, закрепленное за j-ой линией в оптимальном плане

Ограничения

1) ³ 0 – количество судов i-го типа, закрепленное за j-ой линией, д.б. величиной неотрицательной;

2) – на каждую линию необходимо расставить такое количество судов, чтобы выполнить запланированный грузооборот;

3)  – необходимо использовать флота не более, чем имеется в наличии.

Целевая функция

    Расстановка грузовых судов по линиям симплексным М-методом (на минимум эксплуатационных расходов).

Пример:

Дано: 1. 2 типа грузовых самоходных судов (m=2) i=1,2

    2. 3 грузовые линии движения судов (n=3) j=1,2,3.

    3. Количество судов каждого типа: ,

    4. Грузооборот на каждой линии, млн. т. км.

                     

5. Z_ij – провозная способность судна i-того типа на j-той линии за навигацию, млн. т. км.:

6. Э_ij – эксплуатационные расходы судна i-того типа на j-той линии за навигацию, тыс. усл. руб.:

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

Алгоритм решения.

1. Составление ограничений и целевой функции.

Ограничения:

      

   

  

 

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

                 

                 

 

Таким образом получим равенства и единичные векторы Р₁, Р₂ и Р₃ – искусственные векторы, которые показывают недовыполнение плана перевозок на линиях.

Р₄ и Р₅ – свободные векторы, которые показывают недоиспользованное количество флота.

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

    После преобразования функционал цели будет иметь вид:

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

3. После произведенных преобразований составляем симплексную таблицу и заполняем ее исходными данными.

Таблица 1

Ci             Базис			65	70	80	80	90	110	М	М	М	0	0
		Po	Ф11	Ф12	Ф13	Ф21	Ф22	Ф23	P1	P2	P3	P4	P5
М P1		800	50	0	0	90	0	0	1	0	0	0	0
М P2		1200	0	70	0	0	130	0	0	1	0	0	0
М	P3	900	0	0	100	0	0	120	0	0	1	0	0
О	P4	15	1	1	1	0	0	0	0	0	0	1	0
О	P5	20	0	0	0	1	1	1	0	0	0	0	1
Zj			50М	70М	100М	90М	130М	120М	М	М	М	О	О
Zj – Cj			50М -65	70М-70	100М-80	90М-80	130М-90	120М-110	М-М=0	0	0	0	0

 

В таблице Р_о – вектор решений, который составляется из правых частей уравнений и численно выражает грузооборот и количество судов.

    C_i – цена базисных векторов;

C_j – цена структурных, искусственных и свободных векторов.

4. Определяем Z_j и разности Z_j - C_j для каждого вектора.

где Х_ij – элементы i-той строки и j-го столбца-вектора .

Разность Z_j - C_j показывает оптимальность плана, т.е. является условием оптимальности.

Если решаем задачу на min критерия, то решение будет оптимальным при условии

Если же решаем задачу на max критерия, то для оптимальности должно выполняться условие

Далее реализуем алгоритм симплекс-метода:

1. Выбираем вектор, который будем вводить в базис. Он будет соответствовать наибольшему нарушению, т.е. наибольшей разности

 Z_j - C_j .

 

Наибольшая разность равна 130М-90, что соответствует вектору Ф₂₂ . Обозначим этот вектор Р_к.

2. Определяем в базисе вектор, который будем выводить из базиса, т.е. будем замещать вектором Р_к. Для этого производится деление элементов Х_i из столбца Р_о на соответствующие положительные элементы Х_iк вектора Р_к. В таблице замещается вектор, для которого достигается минимум отношения.

Следовательно, будем выводить из базиса вектор Р₂, обозначим его как Р_r. Элемент на пересечении векторов Р_к (ключевой столбец) и Р_r (ключевая строка) называется генеральным элементом. Обозначаем его Х_rк, в нашем случае Х_rk = 130.

Вектор Р_к (Ф₂₂) вводим в базис, а вектор Р_r (Р₂) выводим. Для этого строим новую симплексную таблицу 2.

 

 

Таблица 2

Ci       Базис			65	70	80	80	90	110	М	М	М	0	0
		Po	Ф11	Ф12	Ф13	Ф21	Ф22	Ф23	P1	P2	P3	P4	P5
М P1		800	50	0	0	90	0	0	1	0	0	0	0
90 Ф22		9,2	0	0,54	0	0	1	0	0	0,1	0	0	0
М	P3	900	0	0	100	0	0	120	0	0	1	0	0
0	P4	15	1	1	1	0	0	0	0	0	0	1	0
0	P5	10,8	0	-0,54	0	1	0	1	0	-0,01	0	0	1
Zj			50М	48	100М	90М	90	120М	М	9	М	О	О
Zj – Cj			50М -65	48-70	100М-80	90М-80	0	120М-110	0	9-М	0	0	0

 

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

Для вновь введенного в базисе вектора (Ф₂₂)

Находим для остальных:

Х1= 800-9,2*0 = 800

 = 9,2

Х3= 900-9,2*0 = 900

Х4= 15-9,2*0 = 15

Х5= 20-9,2*1 = 10,8

4. В таблице 2 заполняется строка вводимого в базис вектора Ф22 (ключевая строка). Для этого все элементы строки Р2 в таблице 1 делятся на генеральный элемент (130) и заносятся в соответствующие клетки таблицы 2. В этой строке базиса ставится цена вектора Ф22, т.е. 90.

5. Все остальные элементы новой таблицы 2 определяются по формуле:

Из формулы видно, что :

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

2) Если в ключевом столбце (вектор Р_к) какой-либо элемент Х_ik=0, то все элементы этой строки (где находится Х_ik=0) переписываются в новую матрицу без изменения.

    В нашем случае без изменения перепишутся строки Р₁,Р₃,Р₄.

    3) Если в ключевой строке (вектор Рr) какой-либо элемент Хrj=0, то все элементы j-го столбца переписываются в матрицу 2 без изменения. (столбцы Р11, Р13, Р21, Р23, Р1, Р3, Р4, Р5)

Оставшиеся элементы таблицы 2 определим по приведенной формуле  

     Определяем значения Z_j и Z_j-C_j в таблице 2, т.е. ищем максимальное нарушение. В нашем случае max нарушение в таблице 2 равно 120 М-110, что соответствует вектору Ф₂₃.

Выше приведенные действия повторяются до тех пор, пока не будут устранены все нарушения оптимальности плана, т.е. во всех случаях Z_j-C_j будет ≤ 0.

 Расшифровка после решения.

Сi	Базис	Ро
80	Ф13	9
80	Ф21	8,8889
90	Ф22	9,2308
0	Р4	6
0	Р5	1,883

                                                То есть Ф₁₃ = 9

                                                Ф₂₁ = 8,8889

                                                Ф₂₂ = 9,2308

                                                Р₄ = 6

                                                Р₅ = 1,883

 

Остальные переменные = 0.

Z = 80*9+80*8,8889+90*9,2308 = 2261,88 тыс. усл. руб.

Проверка ограничений:

1. 90*8,8889 = 800 млн. т.км

2. 130*9,2308 = 1200 млн. т.км

3. 100*9 = 900 млн. т.км

4. 9 < 15 (9+6=15) судов

5. 8,8889+9,2308 < 20 судов

                                                (8,8889+9,2308+1,883 = 20)

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

      Допустим, что для выбора есть 3 актива. Их ожидаемая доходность составляет:

А – 0,11

В – 0,15

С – 0,08

      Причём риск каждого актива составляет:

А – 1,0

В – 1,2

С – 0,9

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

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

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

      Z = 0,11W_a + 0,15W_в + 0,08W_c → max

     Ограничения:

 

Обозначим: W_a = x₁; W_в = x₂; W_c = x₃,            

тогда Z = 0,11x₁ + 0,15x₂ + 0,08x₃ → max

     Ограничения:

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

      Преобразуем ограничения и целевую функцию для нахождения первоначального плана.

Z = 0,11x₁ + 0,15x₂ + 0,08x₃ - µA₅ → max

S₁, S₂, S₃, S₄ – свободные переменные, их цена в целевой функции = 0.

      Переменная А₅ – искусственная переменная, её цена в целевой функции = µ. В данном случае при решении задачи на max значение µ будет большим отрицательным числом. В оптимальном плане значение А₅ должно быть = 0.

      Построим первоначальную симплекс-таблицу с первым базисным решением.

                                        

Сj	Базис	Р0	0,11	0,15	0,08	0	0	0	0	-µ
Сi			x1	x2	x3	S1	S2	S3	S4	A5
0	S1	1,1	1	1,2	0,9	1	0	0	0	0
0	S2	1	1	0	0	0	1	0	0	0
0	S3	1	0	1	0	0	0	1	0	0
0	S4	1	0	0	1	0	0	0	1	0
-µ	A5	1	1	1	1	0	0	0	0	1
			-µ	-µ	-µ	0	0	0	0	-µ
Zj - Cj			-µ-0,11	-µ-0,15	-µ-0,08	0	0	0	0	0

      Воспользуемся алгоритмом симплекс-метода, который позволяет превратить не оптимальный план в оптимальный.

I. Определяется вектор, который вводится в базис. Это вектор, имеющий max нарушение признака оптимальности – х₂.

II. Определяется вектор, который выводится из базиса

Θ = min  =  = 0,917    Это вектор S₁

Для хik > 0

III. Определяется новое значение вектора решений.

P₀ = P₀ – Θ x_ik       P^’₂ = 1 – 0,917*0 = 1; P^’₄ = 1 – 0,917*0 = 1

Р¢₁ = q = 0,917   P^’₃ = 1 – 0,917*1 = 0,083; P^'₅ = 11 – 0,9177*1 = 0,08

 

 

Сj      Сi	базис	P0	0,11	0,15	0,08	0	0	0	0	-µ
			Х1     Wa	X2    Wв	X3        Wc	S1	S2	S3	S4	A5
0,15	x2	0,917	0,833	1	0,75	0,833	0	0	0	0
0	S2	1	1	0	0	0	1	0	0	0
0	S3	0,083	-0,833	0	-0,75	-0,833	0	1	0	0
0	S4	1	0	0	1	0	0	0	1	0
-µ	A5	0,083	0,167	0	0,25	-0,833	0	0	0	1
Zj			0,125-0,167м	0,125	0,112-0,25м	0,15 + 0,833м	0	0	0	-µ
Zj - Cj			0,015-0,167м	0	0,032-0,25м	0,15 + 0,833м	0	0	0	0

 

Используем правила, упрощающие заполнение симплекс-таблицы

IV. Определяется новое значение ключевой строки.

Х^’_rj  =

X₁₁ =  = 0,833

X₁₃ =  = 0,75                X₁₄ =  = 0,833

V. Определяются новые значения всех остальных элементов.

X₃₁ = 0 -  = -0,833

X₅₁ = 1-  = 0,167

X₃₃ = 0 -  = -0,75

      Поскольку в последней строке имеются нарушения, то план не является оптимальным.

      Построив ещё несколько таблиц, получим оптимальное решение:

Сj  Ci	базис	Р0	0,11	0,15	0,08	0	0	0	0	-µ
			х1	х2	х3	S1	S2	S3	S4	A5
0,15	x2	0,5	0	1	-0,5	5	0	0	0	-5
0	S2	0,5	0	0	-1,5	5	1	0	0	-6
0	S3	0,5	0	0	0,5	-5	0	1	0	8
0	S4	1	0	0	1	0	0	0	1	0
0,11	х1	0,5	1	0	1,5	-5	0	0	0	6
Zj			0,11	0,15	0,09	0,2	0	0	0	-0,09
Zj - Cj			0	0	0,01	0,2	0	0	0	-0,09+ µ

Х₁ = 0,15         Х₂ = 0,5

Z = 0, 11*0, 5 + 0, 15*0, 5 + 0, 08*0 - µ*0 = 0, 13 – max

Выполнение ограничений:

1*0, 5 + 1, 2*0, 5 + 0, 9*0 = 1, 1

0, 5 < 1   (0, 5 + 0, 5 = 1)

0, 5 < 1    (0, 5 + 0, 5 = 1)

0 < 1        (0 + 1 = 1)

0, 5 + 0, 5 + 0 = 1