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

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

Прилади й обладнання: калькулятор, аркуш міліметрового паперу.

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

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

    Для успішного вирішення питань багатоваріантного обґрунтування схем і проектів землеустрою необхідно проводити проектування із використанням економіко-математичного моделювання і комп’ютерних розрахунків за алгоритмами математичного програмування. Загальна задача математичного програмування – визначення оптимального (максимального або мінімального) значення критерію оптимальності з визначеними обмеженнями на ресурси й інші умови виробництва.

Економіко-математичне моделювання задач лінійного програмування складається з таких стадій:

1) постановка економіко-математичної задачі;

2) якісний аналіз кількісних залежностей;

3) обробка і встановлення вірогідності вхідної та вихідної інформації, вибір математичного методу розв’язання задачі;

4) побудова структурної економіко-математичної моделі та її робочої матриці;

5) розв’язання задачі згідно з вибраним алгоритмом;

6) аналіз одержаних результатів і коригування моделі.

Сутність графічного методу полягає у знаходженні на графіку області допустимих розв’язків, у якій водночас задовольняються всі обмеження моделі. Шукана область (простір) розв’язків задачі являє собою геометричну фігуру (трикутник, прямокутник, квадрат, трапецію, багатокутник тощо). Умови невід’ємності змінних обмежують область їх допустимих значень першим квадрантом координатної площини (частина площини над віссю x₁ і справа від осі x₂). Інші межі простору розв’язків зображені прямими лініями, побудованими за рівняннями, отриманими шляхом заміни знака « » знаком «=» в обмеженнях розв’язання задачі. Області, у яких відповідні обмеження виконуються, указуються стрілками, спрямованими в бік допустимих значень змінних. У кожній точці, що належить області допустимих значень, усі обмеження виконуються, тому розв’язки, що відповідають цим точкам, є допустимими. Серед нескінченного числа таких точок можна знайти точку оптимального розв’язку, з’ясувавши, у якому напрямку зростає цільова функція. Графічний метод для визначення оптимального плану задачі лінійного програмування доцільно застосовувати лише для задач з двома змінними.

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

Під час організації території сільськогосподарського підприємства в результаті землевпорядного обстеження встановлено, що існує можливість трансформувати заболочені сіножаті (ЗС) площею 430+ij (445) га в ріллю богарну (РБ) і культурні зрошувані пасовища (КЗП). Для безперебійного забезпечення великої рогатої худоби площа КЗП має бути не менше
300 (280) га. Для проведення трансформації підприємство має такі ресурси (таблиця 2.1).

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

 

Таблиця 2.1 – Ресурси підприємства для здійснення трансформації

Порядковий номер	Витрати на 1га трансформації	Трансформація у		Ресурси на проведення трансформації
		Ріллю богарну	Культурні зрошувані пасовища
1	Грошові, грн	365 + i, j (324, 5)	565 + i, j (504, 5)	207000 + 2ij00 (204500)
2	Трудові, люд./год	23 + i, j (24, 5)	34, 5 + i, j (34, 5)	14950 + ij00 (17500)
3	Мінеральні добрива, ц	36 + i, j (36)	18 + i, j (20, 5)	11500 + ij00 (14500)
4	Вапно, ц	45, 5 + i, j (44, 5)	40 + i, j (39, 5)	19550 + ij00 (21500)
5	Механізовані, маш./дні	47, 5 + i, j (46)	34, 5 + i, j (34, 7)	17250 + ij00 (19500)
6	Вартість валової продукції з 1 га, грн	280 + i, j (249, 5)	200 + i, j (179, 5)	—

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

 

    Послідовність розв’язання задачі наводиться на конкретному прикладі.

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

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

х₂ – площа ЗС, яка трансформується у КЗП.

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

b₁ – площа ЗС для проведення трансформації в інші угіддя;

b₂ – грошові ресурси, що виділені на трансформацію;

b₃ – трудові ресурси, які виділені на трансформацію;

b₄ – мінеральні добрива, що виділені на трансформацію;

b₅ – вапно, призначене для вапнування угідь, які трансформуються;

b₆ – механізовані ресурси, які можна використовувати на трансформацію;

b₇ – мінімальна необхідна площа КЗП.

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

а₁₁ – площа 1 га ЗС, трансформованих у РБ;

а₁₂ – площа 1 га ЗС, трансформованих у КЗП;

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

а₂₂ – грошові витрати на трансформацію 1га ЗС у КЗП;

а₃₁ – трудові ресурси на трансформацію 1га ЗС у РБ;

а₃₂ – трудові ресурси на трансформацію 1га ЗС у КЗП;

а₄₁ – норма внесення мінеральних добрив на трансформацію 1 га ЗС у РБ;

а₄₂ – норма внесення мінеральних добрив на трансформацію 1га ЗС у КЗП;

а₅₁ – норма внесення вапна на трансформацію 1 га ЗС у РБ;

а₅₂ – норма внесення вапна на трансформацію 1 га ЗС у КЗП;

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

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

а₇₂ – одиниця виміру ЗС, що трансформуються у КЗП.

4. Техніко-економічні показники при невідомих цільової функції:

с₁ – вартість валової продукції, одержаної з 1 га РБ;

с₂ – вартість валової продукції, одержаної з 1 га КЗП.

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

Знайти цільову функцію  за таких умов:

 

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

Знайти цільову функцію  за умов:

 

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

 

 

та визначають координати точок перетину прямих з осями координат для побудови графіків в прийнятій системі координат на площині. Координати точок схрещення визначають шляхом почергового прирівняння до нуля невідомих у рівняннях системи. Результати розрахунків наведені у таблиці 2.2.

Таблиця 2.2 – Визначення координат x₁ та x₂

Номер рівняння	Координати перетину прямих з осями координат
	х1 (при х2 = 0)	х2 (при х1 = 0)
1	445	445
2	630, 2	405, 4
3	714, 3	507, 3
4	402, 8	707, 3
5	483, 1	544, 3
6	423, 9	562, 0
7	0	280
Fmax = 150000	601, 2	835, 7

Невідоме значення цільової функції спочатку задають довільно, наприклад, F_max= 150000, але при цьому координати точок схрещення прямої з осями повинні мати той же порядок, що і координати точок схрещення граничних прямих.

8. Користуючись даними таблиці 2.2 на кресленні (рисунок 2.1) виконують оцифрування осей ОX₁ і ОX₂, будують за координатами прямі, що відображають межі напівплощин з допустимими і недопустимими значеннями координат х₁ і х₂ для системи обмежень у даній задачі.

9. Визначають область допустимих значень задачі та позначають її штриховкою.

10. За даними таблиці 2.2, на кресленні будують лінію цільової функції. Головна властивість лінії цільової функції така, що під час переміщення її паралельно самій собі до початку координат значення F_max зменшується, а при переміщенні від початку координат – збільшується.

Лінію цільової функції переносять паралельно самій собі до перетину з точкою оптимуму (це крайня точка заштрихованої фігури – точка С) області допустимих значень. У точці оптимуму цільова функція буде мати максимальне значення. Значення координат цієї точки відповідають оптимальному варіантові нашої задачі. Графічно знімають її координати:
х₁  = 160, х₂ = 280.

11. Для більш точного визначення координат точки С розв’язують систему двох рівнянь прямих, які перетинаються в т. С – рівняння 1 і 7.

 

Звідки х₁  = 165; х₂ = 280.

Отже, оптимальним розв’язком задачі при заданих ресурсах буде трансформація 165 га заболочених сіножатей у ріллю богарну, а 280 га – у культурне зрошуване пасовище.

12. При такому використанні угідь, що трансформуються, вартість валової продукції (значення цільової функції) становитиме:

 грн.

13. На підставі знайдених обсягів трансформації проводять аналіз використання виділених ресурсів згідно з оптимальним планом. Результати заносять до таблиці 2.3.

Таблиця 2.3 – Аналіз використання виділених ресурсів

Ресурси	Обсяг ресурсів	Використання ресурсів за оптимальним планом	Різниця
Площа заболочених сіножатей, га	445	165+280=445	0
Грошові ресурси, грн	204500		+9697, 5
Трудові ресурси, люд./год	17500		+3797, 5
Мінеральні добрива, ц	14500		+2820
Вапно, ц	21500		+3097, 5
Механізовані ресурси, маш./дні	19500		+2194
Мінімальна необхідна площа КЗП, га	280	280	0

 

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

 

 

 

Рисунок 2.1 – Графічне розв’язання економіко-математичної задачі лінійного програмування

 

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

1. Які методи економіко-математичного моделювання найчастіше застосовують у землеустрої?

2. Стадії економіко-математичного моделювання задач лінійного програмування.

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

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

5. Яка головна властивість лінії цільової функції?

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

7. Як виконується аналіз використання виділених ресурсів?

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

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

Поделиться: