Моделювання задач лінійного програмування та розв’язання їх симплексним методом

Мета: навчитися моделювати задачі лінійного програмування, які розв’язуються симплексним методом.

Прилади й обладнання: калькулятор.

Короткі теоретичні відомості

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

Процес розв’язання задачі симплекс-методом має ітераційний характер: однотипні обчислювальні процедури (ітерації) повторюються у певній послідовності доти, доки не буде отримано оптимальний план задачі або з’ясовано, що його не існує.

Порядок виконання роботи

У результаті землевпорядного обстеження в сільськогосподарському підприємстві виявлені землі, які можуть бути трансформовані в більш цінні угіддя. Установлено, що ріллю можна трансформувати в сади і ріллю зрошувану (РЗ), пасовище і болота доцільно трансформувати в ріллю богарну (РБ) і культурні зрошувані пасовища (КЗП). За умов господарської діяльності площа садів не має перевищувати 240+ij (205, 8) га, а культурних
пасовищ – 168+ij (145, 8) га.

У таблиці 3.1 наведено витрати на трансформацію 1 га в угіддя, що проектуються: у чисельнику – грошові ресурси (грн/га), у знаменнику – витрати праці (люд. днів/га).

Господарство на проведення робіт, пов’язаних з трансформацією менш продуктивних угідь у більш продуктивні, може виділити
840000+ij00 (705800) грн грошових ресурсів і 162000+ij00 (140800) люд. днів трудових ресурсів.

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

Таблиця 3.1 – Витрати на трансформацію

Угіддя, які підлягають трансформації	Запроектовані угіддя				Площа угідь, придатних для трансформації, га
	Сади	Рілля зрошувана	Рілля богарна	Культурні пасовища
Рілля богарна			–	–	1080+ij (958)
Пасовище	–	–			220+  (189, 6)
Болота	–	–			160+  (141, 6)
Вартість валової продукції з 1 га запроектованих угідь, грн	1505 (1253)	1325 (1104)	295 (245)	215 (179)	–

Примітка: ij – номер студента у списку групи; у дужках указані вихідні дані прикладу розрахунку.

    Алгоритм розв’язання економіко-математичної задачі симплексним методом розглянемо на конкретному прикладі.

1. Невідомі в задачі:

х₁ – площа РБ, яка трансформується в сади;

х₂ – площа РБ, яка трансформується в РЗ;

х₃ – площа пасовищ, яка трансформується в РБ;

х₄ – площа пасовищ, яка трансформується в КЗП;

х₅ – площа боліт, яка трансформується в РБ;

х₆ – площа боліт, яка трансформується в КЗП.

2. Ресурси підприємства:

b₁ – площа ріллі богарної, яка може бути трансформована;

b₂ – площа пасовищ, придатних для трансформації;

b₃ – площа боліт, відведена для цілей трансформації;

b₄ – максимально допустима площа садів;

b₅ – максимально допустима площа КЗП;

b₆ – виділені грошові ресурси для цілей трансформації;

b₇ – виділені трудові ресурси для цілей трансформації.

3. Техніко-економічні коефіцієнти:

а₁₁ = а₁₂ = 1 – одиниця вимірювання площі РБ для трансформації її в сади і РЗ;

а₂₃ = а₂₄ = 1 – одиниця вимірювання площі пасовищ, придатних для трансформації в РБ і КЗП;

а₃₅ = а₃₆ = 1 – одиниця вимірювання площі боліт, придатних для трансформації в РБ і КЗП;

а₆₁ – витрати грошових ресурсів на трансформацію 1га РБ у сади;

а₆₂ – витрати грошових ресурсів на трансформацію 1га РБ у РЗ;

а₆₃ – витрати грошових ресурсів на трансформацію 1га пасовищ у РБ;

а₆₄ – витрати грошових ресурсів на трансформацію 1га пасовищ у КЗП;

а₆₅ – витрати грошових ресурсів на трансформацію 1га боліт у РБ;

а₆₆ – витрати грошових ресурсів на трансформацію 1га боліт у КЗП;

а₇₁ – витрати трудових ресурсів на 1 га трансформації РБ у сади;

а₇₂  – витрати трудових ресурсів на 1 га трансформації РБ у РЗ;

а₇₃ – витрати трудових ресурсів на 1 га трансформації пасовищ у РБ;

а₇₄ – витрати трудових ресурсів на 1 га трансформації пасовищ у КЗП;

а₇₅ – витрати трудових ресурсів на 1 га трансформації боліт у РБ;

а₇₆ – витрати трудових ресурсів на 1 га трансформації боліт у КЗП.

4. Коефіцієнти при невідомих цільової функції:

с₁ – вихід валової продукції з 1 га садів;

с₂ – вихід валової продукції з 1 га РЗ;

с₃, с₅ – вихід валової продукції з 1 га РБ;

с₄, с₆ – вихід валової продукції з 1 га КЗП.

5. Економіко-математична модель задачі в розгорнутому вигляді, згідно з прийнятими умовними позначеннями.

    Знайти: ,

за умов:

 

6. Розгорнутий запис економіко-математичної моделі з техніко-економічними коефіцієнтами та ресурсами:

Знайти: ,

за умов:

 

7. Для знаходження економічного оптимуму необхідно розв’язати систему нерівностей. У такому вигляді система має нескінченну множину розв’язків. Для розв’язання її необхідно звести до канонічного вигляду, де всі умови подають у вигляді рівнянь. Задля цього до лівих частин нерівностей додають додаткові змінні x_{n +1,} (додаткові невідомі). У цільову функцію додаткові невідомі вводять з нульовими коефіцієнтами.

Додаткові невідомі:

х₇ – площа РБ, яка не може бути трансформована;

х₈ – площа пасовищ, яка не може бути трансформована;

х₉ – площа боліт, яка не може бути трансформована;

х₁₀ – площа садів, якої не вистачає до максимально допустимої площі цих садів у господарстві;

х₁₁ – площа КЗП, якої не вистачає до максимально допустимої площі в господарстві;

х₁₂ – недовикористані грошові ресурси, які виділені на трансформацію;

х₁₃ – недовикористані трудові ресурси.

    Тоді економіко-математична модель задачі має такий вигляд.

    Знайти:

за умов:

 

 

 

8. Для розв’язання системи з метою знаходження оптимального плану необхідно знайти базисний розв’язок. Для цього візьмемо: х₁ = 0; х₂ = 0; х₃ = 0; х₄ = 0; х₅ = 0; х₆ = 0; х₇ = 958; х₈ = 189, 6; х₉ = 141, 6; х₁₀ = 205, 8; х₁₁ = 145, 8;
х₁₂ = 705800; х₁₃ = 140800.

9. Результатом розв’язання системи є додатне значення, яке задовольняє систему рівнянь, тобто це перший допустимий розв’язок, що називається першим або початковим опорним планом. Початковий опорний план призводить до нульового значення цільової функції: . Тобто за початковий опорний план вибирається такий розв’язок, за якого всі додаткові невідомі (х₇–х₁₃) дорівнюють ресурсам, а всі основні невідомі (х₁–х₆) дорівнюють нулю.

10.  Знаходження оптимального плану виконується у симплексних таблицях. Зразок обчислень наведено у додатку А.

Перша симплексна таблиця відображає перший опорний план.

Рядок «m+1», у який записуються коефіцієнти при цільовій функції, називається індексним. Під час розв’язання задачі на максимум у цей рядок коефіцієнти записують зі знаком «–», а на мінімум – зі знаком «+».

    У місці перетину індексного рядка і стовпця ресурсів (b_i) зазначається значення цільової функції.

    Обчислення здійснюють шляхом заміни базисних невідомих. Для цього необхідно визначити ключовий (генеральний) елемент. Він знаходиться на перетині ключового стовпця і ключового рядка.

    Ключовим буде той стовпець, де в індексному рядку знаходиться максимальний за абсолютною величиною коефіцієнт, але зі знаком «–».

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

    Ключовий стовпець указує економічну доцільність уведення змінної до базисного розв’язку.

    У рядку «m+1» число 1253 показує вартість валової продукції, одержаної з 1 га усіх угідь, що проектуються. Ключовий рядок указує на найбільш «вузьке» місце в наявності ресурсів у виробництві, у цьому разі це 205, 8 га.

    Заповнення другої та наступних симплексних таблиць починають з генерального рядка. Коефіцієнти цього рядка знаходять шляхом ділення кожного коефіцієнта попередньої таблиці на генеральний елемент. Результати записують до таблиці. У ключовому стовпці таблиці замість генерального елемента ставлять 1, а на місця інших коефіцієнтів – нулі.

    Усі інші коефіцієнти обчислюють за правилом «прямокутника» (рисунок 3.2), включаючи індексний рядок і стовпець контролю.

 

Рисунок 3.2 – Позначення вершин під час обчислення за правилом «прямокутника»

 

Елемент  симплексної таблиці обчислюють за формулою:  

,                                  

де  – генеральний елемент

Аналіз коефіцієнтів останньої симплексної таблиці

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

1) основні невідомі:

х₂ = 958, 0 га – площа РБ, яка трансформована в РЗ;

х₃ = 189, 6 га – площа пасовищ, які трансформовані в РБ;

х₅ = 141, 6 га – площа боліт, трансформованих у РБ;

2) додаткові невідомі:

х₁₀ = 205, 8 га – показує, на скільки га площа садів не перевищує максимально допустиму;

х₁₁ = 145, 8 га – площа КЗП, якої не вистачає до максимально допустимої їх площі в господарстві;

х₁₂ = 18545 грн – недовикористані грошові ресурси, що виділені для цілей трансформації;

х₁₃ = 30801, 319 люд.-днів – недовикористані трудові ресурси.

При такому співвідношенні угідь досягається максимальний вихід валової продукції,  грн.

Використання виділених ресурсів за оптимальним планом:

1) рілля богарна трансформована повністю:

х₁ + х₂ = 958 + 0 = 958 га;

2) пасовище і болота трансформуються повністю:

х₃ + х₄ = 189, 6 + 0 = 189, 6 га;

х₅ + х₆ = 141, 6 + 0 = 141, 6 га;

3) у сади і культурні зрошувані пасовища виділені угіддя не трансформувалися, х₁ = 0 га; х₄ = 0 га; х₆ = 0 га;

4) виділені трудові та грошові ресурси (х₁₂ і х₁₃) використані не повністю.

Розглянемо коефіцієнти в стовпцях основної (х₁, х₄, х₆) і одиничної (х₇, х₈, х₉) матриць оптимального плану.

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

Значення коефіцієнтів основної та додаткової матриць протилежні. Під час аналізу основної таблиці знак «–» указує на збільшення, а «+» – на зменшення. У додатковій матриці – навпаки.

Значення стовпців основної матриці:

х₁ – якщо ввести в оптимальний план сади площею 1 га, то необхідно зменшити площу запроектованої (за рахунок богарної) ріллі зрошуваної на 1 га; при цьому витрати виділених грошових ресурсів зменшаться на 333, 33 грн, а значення цільової функції зменшиться на 32, 33 грн;

х₄ – якщо передбачити трансформування 1 га пасовищ в КЗП, то площа пасовищ, які трансформуються у ріллю богарну, зменшиться на 1 га, грошові витрати зменшаться на 151, 33 грн, витрати трудових ресурсів збільшаться на 3, 35 люд.-днів, а значення цільової функції зменшиться на 147, 05 грн;

х₆ – якщо 1 га боліт трансформувати в КЗП, то площа боліт, які трансформуються в ріллю богарну, зменшиться на 1 га, грошові витрати зменшаться на 136, 33 грн, витрати трудових ресурсів збільшаться на
1, 226 люд.-днів, а значення цільової функції зменшиться на 138, 70 грн.

Значення стовпців одиничної частини матриці:

х₇ – якщо в господарстві будуть додатково знайдені резерви ріллі богарної площею 1 га для трансформації її в ріллю зрошувану, то витрати грошових ресурсів зменшаться на 499, 67 грн, а витрати трудових ресурсів зменшаться на 83, 45 люд.-днів; при цьому значення цільової функції збільшиться на 836, 59 грн;

х₈ – якщо в господарстві будуть додатково знайдені резерви пасовищ обсягом 1 га з для трансформації їх у ріллю богарну, то витрати грошових ресурсів зменшаться на 15 грн, а витрати трудових ресурсів зменшаться на 1, 971 люд.-днів; при цьому значення цільової функції збільшиться на
236, 642 грн;

х₉ – якщо в господарстві буде додатково виділений 1 га боліт для трансформації їх у ріллю богарну, то витрати грошових ресурсів зменшаться на 242, 33 грн, а витрати трудових ресурсів зменшаться на 9, 139 люд.-днів; при цьому значення цільової функції збільшиться на 115, 47 грн.

Цей аналіз свідчить про найбільшу очікувану ефективність трансформації ріллі богарної в ріллю зрошувану з заданими умовами і ресурсами за оптимальним планом.

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

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

2. Сутність симплексного методу.

3. Який план називається опорним?

4. Алгоритм симплексного методу розв’язання задачі лінійного програмування.

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

6. Як вибрати генеральний стовпець симплексної таблиці?

7. Як вибрати генеральний елемент симплексної таблиці?

8. Як обчислюються елементи симплексної таблиці за правилом «прямокутника»?

9. Як виконується аналіз коефіцієнтів останньої симплексної таблиці?

 

Практична робота № 4

⇐ Предыдущая1234Следующая ⇒

Поделиться: