Дослідження операцій (стр. 5 )

λк*

η = −− .
λі*

Побудуємо матрицю взаємозамінюваності (таблиця 3.16).

Таблиця 3.16.

і	k
1(λ1*=1)	2(λ2*=2)	3(λ3*=0)
1(λ1*=1)	1	2	0
2(λ2*=2)	1/2	1	0
3(λ3*=0)	∞	∞	1

Так, η21=1/2 означає, що зменшення першого ресурсу на одиницю можна компенсувати 1/2 одиницями другого ресурсу і т. д.; η31 = ∞ означає, що зменшення першого ресурсу на одиницю не можна компенсувати будь-яким збільшенням третього ресурсу; η13 = 0 означає, що, оскільки третій ресурс надлишковий, то його зменшення на одиницю компенсувати не треба.

До недопустимості оптимального розв'язку вихідної задачі можуть призвести наступні два варіанти:

1. Змінення запасів ресурсів.

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

В першому випадку має певний інтерес визначити такі проміжки змінення кожного значення ресурсу bі, в яких оптимальний план двоїстої задачі не зміниться. Це буде тільки тоді, коли для всіх (bі + Δbі) компоненти плану в останній симплекс-таблиці залишаються невід'ємними, тобто:

Хнов = Рх-1 (b + Δb) ≥ 0,

або остаточно:

- Рх-1 ∙ Δb ≤ х*,

причому

.

Визначимо проміжки стійкості двоїстих оцінок відносно до змінений ресурсів кожного виду. Якщо базисний розв'язок залишатиметься допустимим для нових значень ресурсів, то він буде оптимальним розв'язком для цієї задачі.

Оскільки матриця Рх-1 обернена до Рх, складається із компонент векторів Р2,Р3,Р6 базису, який визначає оптимальний план задачі, вона записується безпосередньо з таблиці 3.15, елементи Рх-1 взяті із стовпців векторів Р4,Р5,Р6, які складали початковий базис, тому:'

.

Отже, умови невід'ємності компонент плану зводяться до виконання такої системи нерівностей:

-2Δb1+Δb2 ≤ 400,

-Δb2 ≤ 460,

2Δb1-Δb2-Δb3 ≤ 20.

Якщо Δb2=Δb3 = 0, то -200 ≤ Δb1 ≤ 10. Це означає, що коли кількість ресурсів першого типу буде збільшена не більш ніж на 10 одиниць, або зменшена не менше ніж на 200, то оптимальний план двоїстої задачі не зміниться λ* = (1,2,0).

Далі, якщо Δb1 = Δb3 =0,то -20 ≤ Δb2 ≤ 400, а якщо Δb1=Δb2=0, то 400 ≤ Δb3 ≤ ∞.

Таким чином, кожний з ресурсів може змінюватися в межах:

230 ≤ b1 ≤ 440,

440 ≤ b2 ≤ 860,

400 ≤ b3 ≤ ∞.

Це свідчить про те, що структура оптимального плану вихідної задачі зберігається, тобто рентабельними залишається продукція другого та третього видів.

Отже, якщо один із ресурсів змінюється у визначених проміжках, а решта залишається незмінною, то двоїста задача має один і той же оптимальний план.

Якщо всі ресурси змінюються разом, то дослідження ускладнюється, тому що треба знайти многогранник розв’язків наведеної системи лінійних нерівностей.

До порушення оптимальності здобутого розв'язку може призвести:

1. Змінення коефіцієнтів цільової функції.

2. Впровадження нового виду продукції.

Розглянемо випадок, коли варіюються коефіцієнти цільової функції Сj, j= .

Виведемо умови, при яких здобутий раніше оптимальний план залишиться оптимальним. Нехай змінюються коефіцієнти при базисних змінних (Сі+ΔСі),і = .

Тоді для того, щоб оптимальний план залишився оптимальним, необхідно і достатньо зберігання знаків оцінок векторів умов при небазисних змінних:

.

або

Остаточно маємо таку систему нерівностей:

Розв'язання її дає можливість отримати шукані варіації Сі, і =, при яких зберігається попередній оптимальний базис. Для даної задачі маємо систему нерівностей:

1/4ΔС2 – 3/2ΔС3 - 2ΔС6 ≤ 4,

-1/2ΔС2 + 2ΔС6 ≤ 1,

1/4ΔС2 - 1/2ΔС3 – ΔС6 ≤ 2,

або

ΔС2 – 6ΔС3 - 8ΔС6 ≤ 16,

-ΔС2 + 4ΔС6 ≤ 2,

ΔС2 - 2ΔС3 – 4ΔС6 ≤ 8.

Звідси, якщо ΔС3 = ΔС6 = 0, то - 2 ≤ ΔС2 ≤ 8 і коефіцієнт С2 може змінюватися в проміжку

0 ≤ С2 ≤ 10,

при цьому визначений план залишиться оптимальним. Якщо ж ΔС2 = ΔС6 = 0, тоді

-8/3 ≤ ΔС3 ≤ ∞, а 7/3 ≤ С3 ≤ ∞.

Оскільки х6 вільна додаткова змінна, то коефіцієнт цільової функції С6 =0, тому варіації ΔС6 завжди повинні дорівнювати нулю.

Розглянемо випадок, коли коефіцієнти змінюються при небазисних змінних.

Система умов для визначення варіювань ΔСj, j = має вигляд

.

або остаточно

ΔСj ≤ Δj, j = .

В нашому випадку оскільки, С4 і С5 коефіцієнти при вільних змінних то їх варіації завжди дорівнюють нулю. Тому може змінюватися тільки коефіцієнт С1, для якого

-∞ ≤ ΔС1 ≤ 4.

Отже, якщо 0 ≤ С1 ≤ 7, то оптимальний план Х* = (0,100,230) залишиться оптимальним.

Розглянемо можливість організації випуску додаткової продукції. Позначимо її обсяг через х7. Нехай поопераційні витрати на технологічному обладнанні складають відповідно 7/4,1,1, а коефіцієнт цільової функції С7 = 4. Тоді математична модель задачі запишеться так:

3х1 + 2х2 + 5х3 + 4х7 → mах,

х1 + 2х2 + х3 + 1,75х7 ≤ 430,

3х1 + 2х3+х7 ≤ 460,

х1 + 4х2 + х7 ≤ 420,

х1 ≥ 0, х2 ≥ 0, х3 ≥ 0, х7 ≥ 0.

Введення нового виду діяльності еквівалентне зміненню як цільової функції, так і коефіцієнтів в обмеженнях.

Припустимо, що зміна х7 була присутня у вихідній задачі з нульовими коефіцієнтами, а в модифікованій задачі, що наведена вище, вони набули нових значень. Такий підхід дозволяє вважати змінну х7 небазисною для оптимального розв'язку. Обчислимо оцінку Δ7 за формулою і перевіримо виконання умов оптимальності плану:

Δ7 = 1,75λ1 + λ2 + λ3 – 4 = 1,75 ∙ 1 + 1 ∙ 2 + 1 ∙ 0 – 4 = - 1/4 <0

Отже, критерій оптимальності плану порушено тому, якщо ввести х7 в базис, план можна поліпшити. Обчислимо компоненти вектора Р7 в базисі Р2,Р3,Р6:

.

Додамо відповідний вектор-стовпець, що асоційований із змінною х7, до таблиці 3.15 і отримаймо нову таблицю. 3.17 .

Таблиця 3.17

і	Базис	С	Х	3	2	5	0	0	0	4
Р1	Р2	Р3	Р4	Р5	Р6	Р7
1	Р2	2	100	-1/4	1	0	1/2	-1/4	0	5/8
2	Р3	5	230	3/2	0	1	0	1/2	0	1/2
3	Р6	0	20	2	0	0	-2	1	1	-3/2
m+1			1350	4	0	0	1	2	0	-1/4

Виконуючи п.4, за один крок отримуємо новий оптимальний розв'язок (таблиця 3.18).

Таблиця 3.18

і	Базис	С	х	3	2	5	0	0	0	4
Р1	Р2	Р3	Р4	Р5	Р6	Р7
1	Р7	4	160	-2/5	8/5	0	4/5	-2/5	0	1
2	Р3	3	150	17/10	-4/5	1	-2/5	7/10	0	0
3	Р6	0	260	7/5	12/5	0	-4/5	2/5	1	0
m+1			1390	39/10	2/5	0	6/5	19/10	0	0

Отже, Х* = (0,0,150,0,0,260,160), Z7(х*) = 1390. Разом із цим знайдено і розв'язок відповідної двоїстої задачі: λ* = (6/5,19/10,0), Т(λ*)=1390.

Якщо надлишковий ресурс зменшиться на 10%, то його нове значення буде таким:

b3нов = 420 – 420 ∙ 0,1 = 378.

Отже, тепер вектор ресурсів буде таким b"нов = (430,460,378). Яким буде новий розв'язок, чи залишиться він допустимим? Обчислимо компоненти нового плану:

.

Оскільки новий розв'язок недопустимий, то перейдемо до п.5. На основі таблиці 3.15 заповнимо таблицю 3.19. Здійснивши один крок двоїстого симплекс-методу, отримуємо таблицю 3.20.

Таблиця 3.19

і	Базис	С	Х	3	2	5	0	0	0
Р1	Р2	Р3	Р4	Р5	Р6
1	Р2	2	100	-1/4	1	0	1/2	-1/4	0
2	Р3	5	230	3/2	0	1	0	1/2	0
3	Р6	0	-22	2	0	0	-2	1	1
m+1			1350	4	0	0	1	2	0

Таблиця 3.20