Втрати живої ваги при перевезенні худоби, кг на 1 т

М'ясокомбінати	Господарства
	S1	S2	S3	S4	S5
D1	20	15	25	10	50
D2	15	10	30	20	30
D3	25	30	15	35	55

Задача 4.2.Потрібно скласти такий план розміщення сортів озимої пшениці за попередниками, щоб очікуваний валовий збір зерна був максимальним. Площі попередників та посівні площі сортів озимої пшениці наведені в таблицях 4.4 та 4.5, а середня урожайність сортів озимої пшениці за попередниками в таблиці 4.6.

Таблиця 4.4

Площі попередників озимої пшениці, га

Варіант (за передостанньою цифрою шифру Р)	Попередники
	Ярі зернобобові	Кукурудза на зелений корм	Багаторічні трави	Насінники багаторічних трав	Ранні овочі
	S1	S2	S3	S4	S5
0	300	300	300	50	50
1	200	250	400	50	100
2	200	150	500	100	50
3	300	100	400	100	100
4	250	350	300	60	40
5	400	150	250	80	120
6	350	200	350	50	50
7	300	150	450	40	60
8	300	200	350	70	80
9	250	250	350	60	90

Таблиця 4.5

Площа сортів озимої пшениці, га

Варіант (за останньою цифрою шифру К)	Сорти озимої пшениці
	Тіра	Одеська-267	Донецька -48	Коломак-5
	D1	D2	D3	D4
0	250	450	200	100
1	300	300	250	150
2	400	300	100	200
3	350	300	250	100
4	300	250	300	150
5	100	350	300	250
6	150	400	150	300
7	200	400	200	200
8	350	200	350	100
9	450	100	200	250

Таблиця 4.6

Середня урожайність озимої пшениці за попередниками, ц з 1 га

Попередники		Сорти озимої пшениці
		Тіра	Одеська-267	Донецька 48	Коломак 5
		D1	D2	D3	D4
Ярі зернобобові	S1	47	48	49	52
Кукурудза на зелений корм	S2	44	47	48	45
Багаторічні трави	S3	52	56	51	54
Насінники багаторічних трав	S4	50	56	48	54
Ранні овочі	S5	46	49	47	48

Зміст виконання завдання

1. Запис умов задачі за індивідуальним варіантом.

2. Побудова початкового опорного плану задачі.

3. Розв'язок задачі в транспортних таблицях та на ПЕОМ за допомогою надбудови MS Excel ”Поиск решения” (додаток В) .

4. Висновки за результатами розв'язку задачі.

Зм 3. Двоїстість у лінійному програмуванні

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

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

1. Кожному обмеженню прямої задачі відповідає одна змінна двоїстої задачі.

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

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

4. Якщо в прямій задачі обмеження мають вигляд менше або дорівнює () і на змінні накладена умова невід’ємності, то обмеження двоїстої задачі мають вигляд більше або дорівнює (), а на її змінні також накладено умову невід’ємності і навпаки.

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

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

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

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

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

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

1) при введенні в базис одиниці основної небазисної змінної додатні коефіцієнти структурних зрушень показують величину зменшення базисних змінних, а від’ємні - збільшення. Значення цільової функції зменшується на величину двоїстої оцінки;

2) при введенні в базис одиниці додаткової небазисної змінної при обмеженнях виду менше або дорівнює () додатні коефіцієнти структурних зрушень показують величину збільшення базисних змінних, а від’ємні - зменшення. Значення цільової функції збільшується на величину двоїстої оцінки;

3) при обмеженнях виду більше або дорівнює () додатні коефіцієнти структурних зрушень показують величину зменшення базисних змінних, а від’ємні - збільшення. Значення цільової функції зменшується на величину двоїстої оцінки.

Для задач мінімізації цільової функції знаки змінюються на зворотні.

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

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

Розрахунки виконуються за формулою

X_j^*  X_j´  _Ij ∆X_j

де X_j^* - значення базисної змінної в новому варіанті оптимального розв"язку;

X_j´ - значення базисної змінної у початковому оптимальному розв"язку;

_ij - коефіцієнти структурних зрушень та двоїсті оцінки небазисної змінної, яка вводиться в оптимальний розв’язок;

∆X_j - величина небазисної змінної, яка вводиться в оптимальний розв’язок.

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

Контрольні питання

1. За якими правилами пряму задачу лінійного програмування можна перетворити у двоїсту ?

2. Де знаходяться двоїсті оцінки та коефіцієнтів структурних зрушень в кінцевій симплексній таблиці прямої задачі ?

3. Як впливають двоїсті оцінки на значення цільової функції ?

4. Як впливають коефіцієнти структурних зрушень на значення відповідних базисних змінних ?

5. Як визначаються максимальні межі введення в базисний розв'язок небазисних змінних ?

6. Як отримати новий варіант оптимального розв'язку задачі за допомогою двоїстих оцінок та коефіцієнтів структурних зрушень ?

7. Як визначити доцільність введення в оптимальний розв'язок нової небазисної змінної ?

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

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

Z_max = 90x₁ + 50x₂

при обмеженнях: 1) x₁ + x₂ < 400; 2) 50x₁+30x₂ < 18000; 3) 6x₁+ 3x₂ < 1800

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

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

при обмеженнях: 1) у₁ + 50у₂ + 6у₃ 90;2) у₁ + 30у₂ + 3у₃ 50

Розв'язок двоїстої задачі: W_min = 28000, у₁ =10; у₂ =0; у₃= 13,3; r₁ = 0; r₂ = 0,

де r₁ і r₂ – додаткові змінні двоїстої задачі.

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

Базисні змінні		Значення базисних змінних		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 симплексної таблиці) і двоїстої задач показує, що значення цільових функцій прямої і двоїстої задач однакові Z_max = W_min=28000; коефіцієнти при змінних в Z_max-рядку прямої задачі дорівнюють значенням базисних змінних двоїстої задачі. При цьому: y₁ = 10; y₂ = 0;

у₃ = 13.333; r₁ = 0; r₂ = 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).

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

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

Таблиця 5.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
Zmax	28000	10	1010 = 100	28000+100=28100

^*)Примітка. Для основних та додаткових змінних при обмеженнях виду більше або дорівнює () добутки віднімаються.

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

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

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

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

Задачі для самостійного розв'язання

Задача 5. За умовами задачі 2.1 для самостійного розв"язування:

а) записати до неї двоїсту задачу і розв'язати її на ПЕОМ за допомогою надбудови MS Excel ”Поиск решения” (додаток А) ;

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

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

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

- отримати нові варіанти оптимальних розв'язків задачі шляхом введення в базисний розв'язок небазисних змінних (величина небазисної змінної не повинна перевищувати визначених меж);

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

^*)Примітка. Розрахунки виконати для всіх небазисних змінних кінцевої симплексної таблиці прямої задачі.