Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:

CKT_l.r.03_Optimizacija / Задача оптимизации в MathCad

.pdf
Скачиваний:
39
Добавлен:
29.02.2016
Размер:
181.54 Кб
Скачать

Розв’язання задач оптимізації засобами Mathcad

доктор фіз.–мат. наук, професор Гавриленко В.В., старший викладач Парохненко Л.М.

(Национальный транспортный университет)

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

Найбільш ефективними, глибоко розробленими і широко перевіреними на практиці методами розв’язку задач щодо визначення оптимального плану (задач оптимізації) єметодилінійногопрограмування[1], якіможнарозділитинадвігрупи.

До першої групи відносяться універсальні методи, за допомогою яких можна розв’язати будь-яку задачу лінійного програмування. З універсальних методів найбільше розповсюдження одержав симплексний метод, запропонований Дж. Данцигом. До цієї групи належить також метод розв’язуючих множників академіка Л.В. Канторовича. Серед методів розв’язання задач цілочислового лінійного програмування можна відзначити метод Р. Гоморі.

До другої групи відносяться спеціальні методи, що використовуються для отримання розв’язку окремих типів задач лінійного програмування. спеціальні методи, як правило, простіше універсальних, але вони застосовні лише для конкретних типів задач. Такими є методи розв’язання транспортної задачі, серед яких можна відзначити розподільний метод і його модифікації, метод розв’язуючих доданків А.Л. Лур'є, метод диференціальних рент А.Л. Брудно, угорський метод.

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

Слід зазначити, що метою статті не є викладання курсу лінійного програмування з тим чи іншим ступенем повноти. Основна мета – на конкретних прикладах показати можливості математичного пакета Mathcad [2,3] для розв’язання задач оптимізації; проілюструвати, як відносно легко такі задачі можуть бути розв’язані навіть користувачем, що не володіє глибокими знаннями лінійного програмування.

Нижче на прикладах показано, як Mathcad дозволяє одержувати розв’язки задач про визначення оптимального виробничого плану підприємства.

Задача. Фірма виробляє вироби трьох модифікацій (I, II, III). Витрати, що пов'язані з виконанням кожної операції (у грн.) в процесі виготовлення одного виробу, наведені в таблиці.

Операція

 

Витрати, грн.

 

I

 

II

 

III

 

 

 

Виготовлення

20

 

30

 

20

комплектуючих

 

 

 

 

 

 

 

Складання

10

 

20

 

30

виробу

 

 

 

 

 

 

 

Тестування

10

 

10

 

20

і упакування

 

 

 

 

 

 

 

Максимальні тижневі витрати фірми, що пов’язані з виконанням операцій по виготовленню комплектуючих, по складанню виробів, по тестування й упакуванню виробів, становлять 3600 грн., 2400 грн., 1800 грн. відповідно.

Прибуток від продажу одного виробу модифікації I, II, III складає відпові-

дно 15, 22, 19 грн.

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

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

2.Для задоволення потреб постійного клієнта фірма зобов'язана випускати в тиждень не менш 30 виробів модифікації III. Як вплине ця умова на оптимальний план випуску виробів?

3.Хоча ринок збуту необмежений, можливості збереження виробів на фірмі обмежуються 140 екземплярами. Як це обмеження впливає на оптимальний план виробництва продукції?

Математичне формулювання задачі 1

Нехай x1, x2, x3 – кількість виробів модифікації I, II, III відповідно в плані виробництва.

За змістом x1, x2, x3 можуть приймати тільки невід’ємні та цілі значення,

тобто: x1 0; x2 0; x3 0 ; x1, x2, x3 – цілі. Оскільки витрати, пов'язані з вико-

нанням робіт по виготовленню комплектуючих для виробів модифікацій I, II, III, по складанню цих виробів, по їхньому тестуванню й упакуванню, не перевищують 3600, 2400 і 1800 грн. відповідно, то отримаємо наступну систему обмежень:

20 x1 +30 x2 +20 x3 3600;

 

 

 

 

2400;

 

10 x1 +20 x2 +30 x3

 

 

 

 

1800;

(1)

10 x1 +10 x2 +20 x3

x

j

цілі, j =1; 2; 3;

 

 

 

 

 

 

 

 

0, j =1; 2; 3.

 

 

x j

 

 

Тижневий прибуток фірми від реалізації виробленої продукції визначається цільовою функцією

Z =15 x1 + 22 x 2 +19 x3 .

(2)

Отже, розв’язання сформульованої задачі оптимізації зводиться до розв’язування задачі цілочислового лінійного програмування, а саме, до визна-

чення тих значень x1, x2, x3, які задовольняють системі обмежень (1) і при яких цільова функція (2) досягає максимуму.

Розв’язання задачі 1

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

Висновок: одержано оптимальний план виробництва: максимальний прибуток у 2760 грн. фірма може одержати у випадку, якщо буде виготовляти вироби модифікацій I, II, III у кількості 100, 40, 20 екземплярів відповідно.

Математичне формулювання та розв’язання задачі 2

У випадку, коли фірма пов’язана з клієнтом такою угодою, що повинна випускати в тиждень не менш 30 виробів модифікації III, одержуємо додаткове обмеження x3 30 .

Тоді будемо мати наступну систему обмежень

20 x1 +30 x2 +20 x3 3600;

 

 

 

 

 

 

 

 

 

 

 

 

10 x1 +20 x2 +30 x3 2400;

 

10 x

1

+10 x

2

+20 x

3

1800;

 

 

 

 

 

 

 

 

(3)

x

3

30;

 

 

 

 

 

 

 

 

 

j =1; 2; 3;

 

 

x j цілі,

 

 

 

 

0, j =1; 2; 3.

 

 

 

x

j

 

 

 

 

 

 

 

 

 

 

 

 

 

Розв’язок даної задачі зводиться до визначення тих значень x1, x2, x3, що задовольняють системі обмежень (3), при яких цільова функція (2) буде мати максимальне значення.

Розв’язок цієї задачі отримаємо за методикою розв’язання задачі 1: Нижче наведена програмна реалізація задачі 2.

Висновок: одержано оптимальний план виробництва: максимальний прибуток у 2580 грн. фірма може одержати у випадку, якщо буде виготовляти вироби модифікацій I, II, III у кількості 90, 30, 30 екземплярів відповідно.

Математичне формулювання та розв’язання задачі 3

Якщо виробництво фірми стримується можливостями збереження виробів 140 екземплярами, хоча ринок збуту необмежений, то будемо мати додаткове обмеження x1 + x 2 + x3 140 .

У цьому випадку будемо мати наступну систему обмежень

20 x1 +30 x2 +20 x3 3600;

 

 

 

 

 

 

 

10 x1 +20 x2 +30 x3 2400;

 

 

 

 

 

 

 

10 x1 +10 x2 +20 x3 1800;

x3 30;

 

(4)

x

1

+x

2

+x

3

140;

 

 

 

 

x j

цілі, j =1; 2; 3;

 

 

0,

j =1; 2; 3.

x

j

 

 

 

 

 

 

Розв’язання цієї задачі зводиться до визначення значень x1, x2, x3, які задовольняють системі обмежень (4), при яких цільова функція (2) буде мати максимальне значення.

Розв’язок даної задачі одержуємо за методикою розв’язування попередньої задачі. Програмна реалізація задачі 3 наведена нижче.

Висновок: одержано оптимальний план виробництва: максимальний прибуток у 2500 грн. фірма може одержати у випадку, якщо буде виготовляти вироби модифікацій I, II, III у кількості 70, 40, 30 екземплярів відповідно.

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

 

 

 

 

 

 

I

II

III

Макс.

 

прибуток

 

 

 

 

Задача 1

100

40

20

2760 грн.

Задача 2

90

30

30

2580 грн.

Задача 3

70

40

30

2500 грн.

Рис. 1. Порівняльна таблиця результатів.

Література

1.Терехов Л.Л. Экономико–математические методы. М.: Статистика, 1968. – 300 с.

2.Mathcad в інженерних розрахунках. Частина 1. Посібник для студентів інженерних спеціальностей НТУ / Гавриленко В.В., Величко К.С., Алєксєєнко К.М. – К.: НТУ, 2002. – 127 с.

3.Mathcad в інженерних розрахунках. Частина 2. Посібник для студентів інженерних спеціальностей НТУ / Гавриленко В.В., Величко К.С., Алєксєєнко К.М. – К.: НТУ, 2002. – 108 с.