Нахождение решения задачи параметрического программирования

В задачах параметрического программирования целевая функция или функции ограничений либо и то, и другое зависят от некоторых параметров.
Решение задачи, целевая функция которой содержит параметр. Считая значение параметра t равным некоторому числу t₀∈[α, β], находим симплексным методом или методом искусственного базиса решение полученной таким образом задачи линейного программирования.
В результате при данном значении t₀ либо найдем оптимальный план задачи (1)-(3), либо установим ее неразрешимость. В первом случае, используя элементы (m+1)-й строки последней симплекс-таблицы решения задачи, в которой записаны числа Δ_j(t₀)=Δ’_j+t₀Δ’’_jt, находим:

(16)

(17)

Для всех t≤t≤t задача (1)-(3) имеет один и тот же оптимальный план, что и при t₀.
В том случае, если задача (1)-(3) при t₀ неразрешима, в (m+1)-й строке последней симплекс-таблицы ее решения имеется число Δ_k= Δ’_k+t₀Δ’’_k<0, x_ik≤0(i=1,m). Тогда:
1) если Δ’’_k=0, то задача (1)-(3) неразрешима для любого t;
2) если Δ’’_k<0, то задача (1)-(3) неразрешима для всех t<t₁=-Δ’_k/Δ’’_k;
3) если Δ’’_k>0, то задача (1)-(3) неразрешима для всех t>t₁.
Определив все значения параметра t∈[α, β], для которых задача (1)-(3) имеет один и тот же оптимальный план или для которых задача неразрешима, получаем промежуток изменения параметра t, который исключаем из рассмотрения. Снова полагаем значение параметра t равным некоторому числу, принадлежащему промежутку [α,β], и находим решение полученной задачи.
После каждой итерации определяется либо промежуток, в котором для всех значений параметра задача имеет один и тот же оптимальный план, либо промежуток, в котором для всех значений параметра задача не имеет решения.
Итак, процесс нахождения решения задачи (1)-(3) включает следующие этапы:
1⁰. Считая значение параметра t равным некоторому числу t₀∈[α, β], находим оптимальный план X^* или устанавливают неразрешимость полученной задачи линейного программирования.
2⁰. Определяют множество значений параметра t∈[α, β], для которых найденный оптимальный план является оптимальным или задача неразрешима. Эти значения параметра исключают из рассмотрения.
3⁰. Полагают значение параметра t равным некоторому числу, принадлежащему оставшейся части промежутка [α,β], и находят решение полученной задачи линейного программирования.
4⁰. Определяют множество значений параметра t, для которых новый оптимальный план остается оптимальным или задача неразрешима. Вычисления повторяют до тех пор, пока не будут исследованы все значения параметра t∈[α, β].

Задача 2. Предприятие для изготовления различных изделий А,В и С использует три вида сырья. Норма расхода сырья каждого вида на производство единицы продукции данного вида приведена в табл. 1.21. В ней же указана цена изделия каждого вида.
Таблица 1.21

Вид сырья	Норма затрат сырья (кг) на единицу продукции
	А	В	С
1	18	15	12
2	6	4	8
3	5	3	3
Цена единицы продукции (руб.)	9	10	16

Изделия А,В и С могут производиться в любых соотношениях (сбыт обеспечен). Однако производство ограничено имеющимся в распоряжении предприятия сырьем 1 вида в количестве 360 кг, 2 вида - в количестве 192 кг, 3 вида - в количестве 180 кг.
Найти план производства изделий, реализация которого обеспечивает максимальный выпуск продукции в стоимостном выражении. Одновременно с этим провести анализ устойчивости оптимального плана задачи при условиях возможного изменения цены единицы каждого из изделий.
Решение. Составим математическую модель задачи. Обозначим планируемый выпуск изделий вида А через х₁, изделий вида В - через х₂, изделий вида С - через х₃. Тогда математическая постановка задачи составит в определении максимального значения функции
F=9x₁+10x₂+16x₃ (19)
при условиях
18x₁+15x₂+12x₃≤360, (21)
6x₁+4x₂+8x₃≤192
5x₁+3x₂+3x₃≤180
x₁,x₂,x₃≥0. (20)
Найдем решение задачи (19)-(20) симплексным методом. Оно приведено в таблице 1.22.
Таблица 1.22

i	Базис	С_б	Р_о	9	10	16	0	0	0
				P₁	Р₂	Р₃	Р₄	P₅	Р₆
1	Р₂	10	8	1	1	0	1/9	-1/6	0
2	Р₃	16	20	1/4	0	1	-1/18	5/24	0
3	Р₆	0	96	5/4	0	0	-1/6	-1/8	1
4			400	5	0	0	2/9	5/3	0

Из этой таблицы видно, что оптимальным планом производства изделий А,В и С является план, согласно которому производится 8 изделий вида В, 20 изделий вида С и не производятся изделия вида А. При этом плане общая стоимость изготовляемой продукции максимальна и равна 400 руб.
Установим теперь возможные границы изменения цен каждого из изделий, внутри которых найденный оптимальный план производства продукции не меняется. Начнем с изделия вида А. Предположим, что его цена с₁ равна не 9 руб., a 9+t₁ руб., где t₁ некоторый параметр. Тогда требуется найти такие значения параметра t₁, что для найденного плана X*=(0,8,20) достигается максимальное значение функции
F=(9+t₁)x₁+10x₂+16x₃
при условиях (19) и (20). Чтобы сделать это, будем считать с₁=9+t₁ и с учетом этого составим таблицу 1.23, в которой первые три строки возьмем из табл. 1.22, а четвертую строку вычислим по правилам
Таблица 1.23

i	Базис	сб	Ро	9+t₁	10	16	0	0	0
				P₁	Р₂	Р₃	Р₄	Р₅	Р₆
1	Р₂	10	8	1	1	0	1/9	-1/6	0
2	Р₃	16	20	1/4	0	1	-1/18	5/24	0
3	Р₆	0	96	5/4	0	0	-1/6	-1/8	0
4			400	5-t₁	0	0	2/9	5/3	0

Как видно из табл. 1.23, план X*=(0,8,20) является оптимальным для построенной задачи параметрического программирования при 5-t₁≥0 т.е. t₁≤5. Это означает, что если цена с₁ одного изделия вида А меньше или равна 14 руб., то задача (18)- (20) имеет оптимальный план X*=(0,8,20), т.е. предприятию нецелесообразно включать в план производства продукции выпуск изделий вида А при условии, что цена одного такого изделия не превышает 14 руб. При этом заметим, что, предполагая возможным изменение цены одного изделия А, мы считаем, что все остальные исходные данные задачи остаются неизменными.
Аналогично можно показать, что если цена с₂ одного изделия вида В изменяется от 8 до 20 руб., то оптимальным планом производства продукции является план, согласно которому изготовляются 8 изделий вида В и 20 изделий вида С. Отметим, что при изменении цены одного изделия вида В мы считаем постоянными все остальные исходные данные задачи. Одновременно с этим заметим, что хотя указанный план и остается оптимальным, значение целевой функции при разных значениях с₂ не одинаковы. Наконец, аналогично показывается, что если цена с₃ одного изделия вида С изменяется от 8 до 20 руб., то оптимальным планом производства продукции также является план, согласно которому производится 8 изделий вида В и 20 изделий вида С.
Мы провели анализ чувствительности оптимального плана задачи (18)-(20) при возможном изменении цены каждого из изделий. Аналогично можно провести анализ чувствительности оптимального плана этой задачи при одновременном изменении значений нескольких коэффициентов целевой функции.
Решение задачи, правые части ограничений которой содержат параметр. Алгоритм решения задачи (4)-(6) подобен рассмотренному выше алгоритму решения задачи (1)-(3).
Полагая значение параметра t равным некоторому числу t₀, находим решение полученной задачи линейного программирования (4)-(6). При данном значении параметра t₀ либо определяем оптимальный план, либо устанавливаем неразрешимость задачи. В первом случае найденный план является оптимальным для любого t≤t≤t ,где

и числа q_i, p_i определены компонентами оптимального плана и зависят от t₀:
х_i*= q_i+t₀P_i.
Если при t=t₀ задача (4)-(6) неразрешима, то либо целевая функция (4) не ограничена на множестве планов, либо система уравнений (5) не имеет неотрицательных решений. В первом случае задача неразрешима для всех t∈[α, β], а во втором случае определяем все значения параметра t∈[α, β], для которых система уравнений (5) несовместна, и исключаем их из рассмотрения.
После определения промежутка, в котором задача (4)-(6) имеет один и тот же оптимальный план или неразрешима, выбираем новое значение параметра t, не принадлежащее найденному промежутку, и находим решение полученной задачи линейного программирования. При этом решение новой задачи ищем с помощью двойственного симплекс-метода. Продолжая итерационный процесс, после конечного числа шагов получаем решение задачи (4)-(6).
Итак, процесс нахождения решения задачи (4)-(6) включает следующие основные этапы:
1⁰. Считая значение параметра t равным некоторому числу t₀∈[α, β], находят оптимальный план или устанавливают неразрешимость полученной задачи линейного программирования.
2⁰. Находят значение параметра t∈[α, β], для которых задача (4)-(6) имеет один и тот же оптимальный план или неразрешима. Эти значения параметра t исключают из рассмотрения.
3⁰. Выбирают значение параметра t из оставшейся части промежутка [α,β] и устанавливают возможность определения нового оптимального плана. В случае существования оптимального плана находят его двойственным симплекс-методом.
4⁰. Определяют множество значений параметра t, для которых задача имеет один и тот же оптимальный план или неразрешима. Вычисления проходят до тех пор, пока не будут исследованы все значения параметра t∈[α, β].

2.66. Для каждого значения параметра t (-∞<t<∞) найти максимальное значение функции
F = Зх₁-2х₂+5х₃-4х₅ (21)
при условиях
x₁+x₂+x₃=12-t, (22)
2x₁-x₂+x₄=8+4t
-2x₁+2x₂+x₃=10-6t, (22)
x_1,x₂,…x₅≥0, (23)
Решение. Считая значение параметра t в системе уравнений (22) равным нулю, находим решение задачи (21)-(23) (табл. 1.24) через калькулятор.
Таблица 1.24

i	базис	С_б	Р₀	3	-2	5	0	-4
				P₁	P₂	P₃	P₄	P₅
1	Р₃	5	12+t	1	1	1	0	0
2	Р₄	0	8+4t	2	-1	0	1	0
3	Р₅	-4	10-6t	-2	2	0	0	1
4			20+29t	10	-1	0	0	0
1	Р₃	5	7+4t	2	0	1	0	-1/2
2	P₄	0	13+t	1	0	0	1	1/2
3	P₅	-2	5-3t	-1	-1	0	0	1/2
4			25+26t	9	0	0	0	1/2

Как видно из табл. 1.24, Х₀*=(0,5-3t,7+4t,13+t,0) при t=0 есть оптимальный план задачи. Очевидно, Х₀* является оптимальным планом и тогда, когда среди его компонентов не окажется отрицательных чисел, т.е. при 5-3t≥0; 7+4t≥0; 13+t≥0 или при -7/4≤t≤5/3. Таким образом, если t∈[-7/4; 5/3], то Х₀*=(0,5-3t,7+4t,13+t,0)-оптимальный план задачи (21)-(23), при котором F_max=25+26t.
Исследуем теперь, имеет ли задача оптимальные планы при t>5/3. Если t>5/3, то 5-3t<0 и, следовательно, X=(0,5-3t,7+4t,13+t,0) не является планом задачи. Поэтому при t>5/3 нужно перейти к новому плану, который был бы в тоже время и оптимальным. Это можно сделать в том случае, когда в строке вектора Р₂ имеются отрицательные числа х'₂_j. В данном случае это условие выполняется. Поэтому переходим к новому опорному плану, для чего введем в базис вектор Р₁ и исключим из него вектор Р₂ (табл. 1.25).
Таблица 1.25

i	Базис	С_б	Р₀	3	-2	5	0	-4
				P₁	P₂	P₃	P₄	P₅
1	Р_з	5	17-2t	0	2	1	0	1/2
2	Р₄	0	18-2t	0	1	0	1	1
3	Р₁	3	-5+3t	1	-1	0	0	-1/2
4			70-t	0	9	0	0	5

Как видно из табл. 2.42, X₁* =(-5+3t,0,17-2t,18-2t,0)- оптимальный план задачи для всех t, при которых 17-2t≥0; 18-2t≥0; -5-3t≥0, т.е. при 5/3≤t≤17/2. Следовательно, если t∈[5/3; 17/2], то X₁*=(-5+3t,0,17-2t, 18-2t,0) является оптимальным планом исходной задачи, причем F_max=70-t.
Если t>17/2, то X₁=(-5+3t,0,17-2t,18-2t,0) не является планом задачи, так как третья компонента 17-2t есть отрицательное число. Поскольку среди элементов 1-й строки табл. 2.42 нет отрицательных, при t>17/2 исходная задача неразрешима.
Исследуем теперь разрешимость задачи при t<-7/4. В этом случае X=(0,5-3t,7+4t,13+t,0) (см. табл. 2.41) не является планом задачи, так как третья компонента 7+4t есть отрицательное число.
Чтобы при данном значении параметра найти оптимальный план (это можно сделать, так как в строке вектора Р₃ стоит отрицательное число -1/2), нужно исключить из базиса вектор Р₃ и ввести в базис вектор P₅ (табл. 1.26).
Таблица 1.26

i	Базис	С_б	Р₀	3	-2	5	0	-4
				P₁	P₂	P₃	P₄	P₅
1	Р₅	-4	-14-8t	-4	0	-2	0	1
2	Р₄	0	20+5t	3	0	1	1	0
3	Р₂	-2	12+t	1	1	1	0	0
4			32+30t	11	0	1	0	0

Как видно из табл. 2.43, Х₂*=(0,12+t,0,20+5t,-14-8t) является оптимальным планом задачи для всех значений параметра t, при которых -14-8t≥0; 20+5t≥0; 12+t≥0, т.е. при -4≤t≤-7/4. Таким образом, если -4≤t≤-7/4, то задача (24)-(26) имеет оптимальный план Х₂*=(0,12+t,0,20+5t,-14-8t), при котором F_max=32+30t. Из табл. 1.26 также видно, что при t<-4 задача неразрешима, поскольку в строке вектора Р₄ нет отрицательных элементов.
Итак, если t∈(-∞, -4), то задача не имеет оптимального плана; если t∈[-4; -7/4], то Х₂*=(0,12+t,0,20+2t,-14-8t)- оптимальный план, a F_max=32+30t; если t∈[-7/4; 5/3], то X₀*=(0,5-3t,7+4t,13+t,0)- оптимальный план, a F_max=25+26t; если t∈[5/3; 17/2], то Х₁*=(- 5+3t,0,17-2t, 18-21,0)-оптимальный план, a F_max =70-t; если t∈(17/2; +∞), то задача неразрешима.
Решение задачи, целевая функция и правые части ограничений которой содержат параметр. Используя описанные выше алгоритмы решения задач параметрического программирования, можно найти решение задачи, в которой от параметра t линейно зависят как коэффициенты целевой функции, так и свободные члены системы уравнений.

Задача 3. Найти максимальное значение функции
F=(8-5t)x₁+(9-3t)x₂+(-3+5t)x₃-(2+4t)x₄
при условиях
x₁-x₂+x₃=24-12t
-x₁+2x₂+x₄=-18+10t
x₁, x₂≥0, t∈(-∞, +∞)
Решение. Считая значение параметра t равным числу 2 ( число 2 взято произвольно), находим симплексным методом решение полученной задачи линейного программирования (табл. 1.27).
Таблица 1.27

i	Базис	С_б	Р₀	8-5t	9-3t	-3+5t	-2-4t

				P₁	P₂	Р₃	P₄
1	Р₃	-3-5t	24-12t	1	-1	1	0
2	Р₄	-2-4t	-18+10t	-1	2	0	1
3			-36+28t-100t²	14t-9	-10t-10	0	0
1	Р₃	-3+5t	15-7t	1/2	0	1	1/2
2	P₂	9-3t	-9+5t	-1/2	1	0	1/2
3			-126+168t-50t²	9t-14	0	0	5t+5

Из табл. 1.27 видно, что если t=2, то X₀*=(0,-9+5t,15-7t,0) - оптимальный план задачи. Таким он является и для тех значений параметра t, при которых 9t-14≥0 и 5t+5≥0, а среди компонент вектора Х₀* нет отрицательных чисел. Эти неравенства выполняются при t≥14/9. Сначала такие значения параметра t и рассмотрим.
Найденный вектор Х₀* является оптимальным планом задачи при 15-7t≥0 и -9+5t≥0, т.е. 9/5 ≤t≤15/7. Итак, если 9/5 ≤t≤15/7, то Х₀*=(0, 15-7t,-9+5t,0)-оптимальный план задачи, при котором F_max=-126+168-50t².
Если t<9/5, то -9+5t<0 и вектор X=(0,-9+5t,15-7t,0) не является планом задачи.
Поэтому при t<9/5 следует перейти к новой симплекс-таблице, что можно сделать, так как в строке вектора Р₂ (табл. 1.27) имеется отрицательное число -1/2. Рассматривая это число как разрешающий элемент, переходим к новой симплекс-таблице, для чего исключим из базиса вектор Р₂ и введем вместо него вектор P₁ (табл. 1.28).
Таблица 1.28

i	Базис	C_б	Р₀	8-5t	9-3t	-3+5t	-2-4t
				P₁	P₂	Р₃	P₄
1	Р₃	-3+5t	6-2t	0	1	1	1
2	P₁	8-5t	18-10t	1	-2	0	-1
3			126-134t+40t²	0	-28+18t	0	14t-9

Из табл. 1.28 видно, что вектор X₁*=(18-10t,0,6-2t,0) есть оптимальный план задачи для всех значений параметра t (как отмечено выше, мы рассматриваем значения t≥14/9), при которых 6-2t≥0 и 18-10t≥0, т.е. t≤9/5. Следовательно, если t∈[14/9; 9/5], то X₁*=(18-10t,0,6-2t,0) является оптимальным планом задачи, при котором F_max=126-134t+40t².
Рассмотрим теперь значение параметра t>15/7. При этих значениях вектор X=(0,-9+5t,15-7t,0) уже не является оптимальным планом задачи, поскольку 15-7t<0. Так как в строке вектора Р₃ (табл. 1.28) нет отрицательных чисел, то при t>15/7 задача неразрешима.
Мы нашли решение задачи при изменении параметра t от 14/9 до +∞. Рассмотрим теперь значения параметра от -∞ до 14/9. Если t<14/9, то в последней строке табл. 1.28 имеется отрицательное число 18t-28. Поэтому следует перейти к новому опорному плану, введя в базис вектор Р₂ и исключив из него вектор Р₃ (табл. 1.29).
Таблица 1.29

i	Базис	C_б	Р₀	8-5t	9-3t	-3+5t	-2-4t
				P₁	P₂	Р₃	P₄
1	Р₂	9-3t	6-2t	0	1	1	1
2	P₁	8-5t	30-14t	1	0	2	1
3			294-98t+76t²	0	0	28-18t	19-4t

Из табл. 1.29 видно, что если -∞<t≤14/9, то Х₂*=(30-14t,6-2t,0,0) является оптимальным планом задачи, причем F_max=294-298t-+76t².
Итак, при t∈(-∞; 14/9] задача имеет оптимальный план X₂*=(30-14t,6-2t,0,0); при t∈[14/9; 9/5] - X₁*=(18-10t,0,6-2t,0); при t∈[9/5; 15/7] - X₀*=(0,-9+5t, 15-7t,0); при t>15/7 она не разрешима.

Перейти к онлайн решению своей задачи

x	f₁(x)	f₂(x)	f₃(x)
1	6.3	4	5
2	5.2	6	7
3	4.3	4.6	7.8
4	5	6	3
5*	7	6.3	8.2

x	f₁(x)	f₂(x)	f₃(x)
1	6.3	4	5
2	5.2	6	7
3	4.3	4.6	7.8
4	5	6	3
5*	7	6.3	8.2

Нахождение решения задачи параметрического программирования

Правила ввода данных

Поиск

Процесс

Сообщение