Завдання 3. Двоїсті задачі лінійного програмування

Приклад 3.1. За данними приклада 2 (завдання 2) сформулювати двоїсту задачу. Виконати економіко-математичний аналіз з використанням двоїстих оцінок і коефіцієнтів структурних зрушень.

Розв’язання. Пряма задача має такий математичний запис:

Zmax = 90x₁ + 50x₂

при обмеженнях:

x₁ + x₂ < 400

50x₁+30x₂ < 18000

6x₁+ 3x₂ < 1800

Кожну пряму задачу лінійного програмування можна перетворити у двоїсту за такими правилами:

1. Пошук максимуму цільової функції прямої задачі замінюється на пошук мінімуму цільової функції двоїстої задачі і навпаки.

2. Кожному обмеженню прямої задачі відповідає одна змінна двоїстої задачі (y_і). В зв’язку з тим, що наведена пряма задача має три обмеження, то двоїста задача має три змінних: y_1, y₂ та у_3..

3. Вільні члени (обсяги обмежень) прямої задачі є оцінками змінних двоїстої задачі.

4. Кількість обмежень двоїстої задачі дорівнює кількості змінних прямої задачі, тобто 2.

5. Коефіцієнти при змінних двоїстої задачі отримуються шляхом транспонування матриці коефіцієнтів при змінних прямої задачі (заміна колонок прямої задачі на рядки двоїстої задачі).

6. Якщо в прямій задачі обмеження мають вигляд „  ”, і на змінні накладена умова невід’ємності, то обмеження двоїстої задачі мають вигляд „  ”, а на її змінні також накладено умову невід’ємності: у₁ > 0; у₂ > 0, у₃ > 0.

7. Оцінки змінних прямої задачі є вільними членами (обсягами обмежень) двоїстої задачі.

Таким чином, двоїста задача буде мати вигляд:

W_min=400y₁+18000y₂+1800y₃

при обмеженнях:

у₁+50у₂+6у₃ 90

у₁+30у₂+3у₃ 50

Оптимальний розв'язок двоїстої задача дорівнює :основні змінні- у₁ = 10,

у₂ = 0, у₃ = 13,333 , та додаткові - ; r₁ = 0; r₂ =0, W_min=28000.

Приведемо оптимальний розв'язок (кінцеву симплексну таблицю) прямої задачі (див. завдання 2 ).

Базисні змінні	Значення базисних змінних	x1	x2	s1	s2	s3
x2	200	0	1	2	0	-0,333
s2	2000	0	0	-10	1	-6,667
x1	200	1	0	-1	0	0,333
Zmax	28000	0	0	10	0	13,333

Нагадаємо, що:

х₁ – площа кукурудзи на зерно, га

х₂ – площа ячменю, га

s₁ – площа невикористаної ріллі, га

s₂ – кількість невикористаних трудових ресурсів, людино-годин

s₃ – кількість невикористаних мінеральних добрив, ц

Z_max - обсяг виробництва кормів, ц к.од.

Порівнюючи кінцеву симплексну таблицю прямої і оптимальний розв”язок двоїстої задач можна помітити, що розв'язок прямої задачі одночасно дає і розв'язок двоїстої задачі, а саме: значення цільових функцій прямої і двоїстої задач однакові Z_max =W_min=28000; коефіцієнти при змінних в Z_max-рядку прямої задачі (позначимо їх через t) дорівнюють значенням базисних змінних двоїстої задачі.

При цьому коефіцієнти при додаткових змінних у Z_max-рядку прямої задачі дорівнюють значенням основних змінних двоїстої задачі, а коефіцієнти при основних змінних дорівнюють значенням додаткових змінних двоїстої задачі:

y₁ = t₃ = 10; y₂ = t₄ = 0; у₃ = t₅ = 13,333; r₁ = t₁ = 0; r₂ = t₂ = 0. Ці величини називаються двоїстими оцінками.

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

Аналіз кінцевої симплексної таблиці прямої задачі показує, що двоїсті оцінки базисних змінних (х₁, х₂ та s₂) дорівнюють нулю. Двоїста оцінка небазисної змінної s₁ дорівнює 10. Це означає, що кожний додатковий гектар ріллі дасть додатково 10 ц к.од (відзначимо, що за результатами розв'язку прямої задачі s₁ = 0, тобто всі 400 га ріллі були використані повністю).

Двоїста оцінка небазисної змінної s₃ дорівнює 13,333. Це означає, що кожний додатковий центнер мінеральних добрив дасть змогу збільшити виробництво кормів на 13,3 ц к.од. (за результатами розв'язку прямої задачі мінеральні добрива також використовуються повністю, s₃ = 0).

Отже двоїсті оцінки додаткових змінних при обмеженнях типу " " показують міру дефіцитності виробничих ресурсів. Дійсно, трудові ресурси повністю не використані (s₂=2000), тому двоїста оцінка цієї змінної дорівнює нулю.

Двоїсті оцінки основних небазисних змінних показують неефективність введення цієї змінної в базисний розв'язок.

Коефіцієнти структурних зрушень в колонках небазисних змінних показують величину зміни значень базисних невідомих при введені в базисний розв'язок одиниці небазисної змінної. Причому, коефіцієнти структурних зрушень основних небазисних змінних віднімаються, а додаткових при обмеженнях типу “” - додаються до значень базисних змінних; при обмеженнях типу “ ” – знов віднімаються від значень базисних змінних.

Так, коефіцієнти структурних зрушень для змінної s₁ (2; -10; -1) означають, що коли у виробництво додатково залучити ще 1га ріллі, то площа ячменю (х₂), збільшиться на 2 га, а площа кукурудзи (x₁) зменшиться на 1 га, залишок трудових ресурсів (s₂) зменшиться на 10 людино-годин. Відповідно при залученні у виробництво 1ц мінеральних добрив (s₃) площа кукурудзи (х₁) збільшиться на 0,333 га, а площа ячменю (х₂) зменшиться на 0,333 га. Залишок трудових ресурсів (s₂) зменшиться на 6,667 людино-годин.

Слід відзначити, що наведені показники дійсні тільки для умов конкретної задачі і мають певні межі застосування. Для визначення максимальних меж введення в базис небазисних змінних потрібно значення базисних змінних поділити на відповідні коефіцієнти структурних зрушень і вибрати найменше відношення. При цьому, для основних небазисних змінних значення базисних змінних потрібно поділити на додатні коефіцієнти структурних зрушень, а для додаткових небазисних змінних при обмеженнях типу “” – на від’ємні; при обмеженнях типу “ ” – знов на додатні.

Наприклад, максимальна межа введення в базисний розв'язок небазисної змінної S₁ дорівнює 200 (min2000/10=200;200/1=200), а для небазисної змінної S₃ - 300 (min200/0.333=600;2000/6.667=300).

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

Приклад 3.2. Потрібно визначити новий варіант оптимального розв'язку задачі при додатковому залученні у виробництво 10 га ріллі або S₁= +10.

Розв’язання.Для цього використаємо двоїсту оцінку і коефіцієнти структурних зрушень небазисної змінної s₁.

Розрахунок зробимо у таблиці 3.1.

Таблиця 3.1

Розрахунок нового варіанту оптимального розв'язку задачі

Базисні змінні	Значення базисних змінних	Коефіцієнти структурних зрушень і двоїста оцінка s1	Добутки коефіцієнтів структурних зрушень і двоїстої оцінки при s1 на 10	Новий варіант оптимального розв'язку задачі
x2	200	2	210 = 20	200+20=220
s2	2000	-10	-1010 = -100	2000+(-100)=1900
x1	200	-1	-110 = -10	200+(-10)=190
Z	28000	10	1010 = 100	28000+100=28100

В новому варіанті оптимального розв'язку задачі площа кукурудзи (х₁) дорівнює 190 га, ячменю (х₂) – 220 га, невикористані трудові ресурси (S₂) складають 1900 людино-годин. Виробництво кормів становить 28100ц к. од. (Z_max =28100).

Приклад 2. За умовами задачі із завдання 2 визначити доцільність вирощування гороху при затратах праці 35 людино-годин і добрив 2 ц на 1 га та при виході кормів 40 ц к. од. з 1 га.

Розв’язання. Для визначення рентабельності вирощування гороху потрібно обсяги виробничих ресурсів, які затрачені на 1 га гороху, перемножити на двоїсті оцінки цих ресурсів.

Якщо сумарна оцінка цих ресурсів менша за вихід кормових одиниць, то вирощування гороху рентабельне : 1х10 + 0х35 + 2х13,3 = 36,6 < 40.

Висновок. Вирощування гороху рентабельне.

Задачі для контрольної роботи

Задача 3. За умовами задачі для самостійної роботи 2 (завдання 2):

1) записати двоїсту до неї задачу;

2) використовуючи кінцеву симплексну таблицю задачі 2 провести економіко-математичний аналіз, а саме:

- пояснити економічну суть двоїстих оцінок і коефіцієнтів структурних зрушень небазисних змінних (як змінюється оптимальний розв”язок при введенні в базис одиниці небазисної змінної);

- визначити максимальні межі введення в базисний розв'язок небазисних змінних;

- отримати нові варіанти оптимальних розв’язків задачі шляхом введення в

базисний розв’язок небазисних змінних, величина яких повинна бути не більше визначених меж;

3) за умовами задачі 2 визначити доцільність вирощування 1 га гороху при затратах праці 40 + К людино-годин і мінеральних добрив 2 ц на 1 га та урожайності 30 + Р ц з 1 га.