Економіко-математичне програмування

Побудувати математичну модель задачі.

На підприємстві виготовляються вироби двох видів А і В. Для цього використовується сировина чотирьох типів – І, ІІ, ІІІ, ІV, запаси якої дорівнюють, відповідно, 21; 4; 6; 10 од. Для виготовлення одного виробу А необхідна така кількість одиниць сировини чотирьох видів: 2; 1; 0; 2. Для виробу В – 3; 0; 1; 1 од. відповідно. Випуск одного виробу А дає 3 грн. од. прибутку, типу В – 2 грн. од. Скласти план виробництва, який забезпечує найбільший прибуток.

Розв’язок

Складаємо математичну модель задачі. Позначимо через х ₁ кількість виробів 1-ї моделі, що виготовляє підприємство за деяким планом, а через х₂ кількість виробів 2-ї моделі. Тоді прибуток, отриманий підприємством від реалізації цих виробів, складає

∫ = 3х₁ +2х₂ .

Витрати сировини на виготовлення такої кількості виробів складають відповідно:

C_I =2х₁ + 3х₂ ,

C_II =1х₁ + 0х₂ ,

C_III =0х₁ + 1х₂ ,

C_IV =2х₁ + 1х₂ ,

Оскільки запаси сировини обмежені, то повинні виконуватись нерівності:

2х₁ + 3х₂ ≤ 21

1х₁ ≤ 4

1х₂ ≤ 6

2х₁ + 1х₂ ≤ 10

Оскільки, кількість виробів є величина невід'ємна, то додатково повинні виконуватись ще нерівності: х₁ > 0, х₂ > 0.

Таким чином, приходимо до математичної моделі (задачі лінійного програмування):

Знайти х₁ , х₂ такі, що функція ∫ = 3х₁ +2х₂ досягає максимуму при системі обмежень:

Розв'язуємо задачу лінійного програмування симплексним методом.

Для побудови першого опорного плану систему нерівностей приведемо до системи рівнянь шляхом введення додаткових змінних. Оскільки маємо змішані умови-обмеження, то введемо штучні змінні x.

2x₁ + 3x₂ + 1x₃ + 0x₄ + 0x₅ + 0x₆ = 21

1x₁ + 0x₂ + 0x₃ + 0x₄ + 0x₅ + 1x₆ = 4

0x₁ + 1x₂ + 0x₃ + 1x₄ + 0x₅ + 0x₆ = 6

2x₁ + 1x₂ + 0x₃ + 0x₄ + 1x₅ + 0x₆ = 10

де х₁ ,...,х₆ >0

Для постановки задачі на максимум цільову функцію запишемо так:

F(X) = 3 x₁ +2 x₂ - M x₆ =>max

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

Складаємо симплекс-таблицю:

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

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

Оскільки всі оцінки >0, то знайдено оптимальний план, що забезпечує максимальний прибуток: х₁ =4, х₂ =2. Прибуток, при випуску продукції за цим планом, становить 16 грн.

Завдання 2

Записати двоїсту задачу до поставленої задачі лінійного програмування. Розв’язати одну із задач симплексним методом і визначити оптимальний план іншої задачі. Оптимальні результати перевірити графічно.

Розв’язок

Вирішимо пряму задачу лінійного програмування симплексним методом, з використанням симплексного таблиці.

Визначимо мінімальне значення цільової функції F(X) = 3x₁ +2x₂ за таких умов-обмежень.

2x₁ +4x₂ ≥10

3x₁ +2x₂ ≥11

4x₁ +7x₂ ≤32

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

2x₁ + 4x₂ -1x₃ + 0x₄ + 0x₅ = 10

3x₁ + 2x₂ + 0x₃ -1x₄ + 0x₅ = 11

4x₁ + 7x₂ + 0x₃ + 0x₄ + 1x₅ = 32

Введемо штучні змінні x.

2x₁ + 4x₂ -1x₃ + 0x₄ + 0x₅ + 1x₆ + 0x₇ = 10

3x₁ + 2x₂ + 0x₃ -1x₄ + 0x₅ + 0x₆ + 1x₇ = 11

4x₁ + 7x₂ + 0x₃ + 0x₄ + 1x₅ + 0x₆ + 0x₇ = 32

Для постановки завдання на мінімум цільову функцію запишемо так:

F(X) = 3x₁ +2x₂ +Mx₆ +Mx₇ => min

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

Отриманий базис називається штучним, а метод рішення називається методом штучного базису.

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

З рівнянь висловлюємо штучні змінні:

x₆ = 10-2x₁ -4x₂ +x₃

x₇ = 11-3x₁ -2x₂ +x₄

які підставимо в цільову функцію:

F(X) = 3x₁ + 2x₂ + M(10-2x₁ -4x₂ +x₃ ) + M(11-3x₁ -2x₂ +x₄ ) => min

або

F(X) = (3-5M)x₁ +(2-6M)x₂ +(1M)x₃ +(1M)x₄ +(21M) => min

Матриця коефіцієнтів A = a(ij) цієї системи рівнянь має вигляд:

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

Вирішимо систему рівнянь відносно базисних змінних:

x₆ , x₇ , x₅ ,

Вважаючи, що вільні змінні рівні 0, отримаємо перший опорний план:

X1 = (0,0,0,0,32,10,11)

Переходимо до основного алгоритму симплекс-методу.

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

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

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

Оптимальний план можна записати так:

x₂ = 1

x₁ = 3

x₅ = 13

F(X) = 3*3 + 2*1 = 11

Складемо двоїсту задачу до прямої задачі.

2y₁ +3y₂ +4y₃ ≤3

4y₁ +2y₂ +7y₃ ≤2

10y₁ +11y₂ +32y₃ => max

y₁ ≥ 0

y₂ ≥ 0

y₃ ≤ 0

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

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

З першої теореми двоїстості випливає, що Y = C*A^-1 .

Складемо матрицю A з компонентів векторів, що входять в оптимальний базис.

Визначивши зворотну матрицю А^-1 черезалгебраїчнідоповнення, отримаємо:

Як видно з останнього плану симплексного таблиці, зворотна матриця A^-1 розташована в стовпцях додаткових змінних.

Тогда Y = C*A^-1 =

Оптимальний план двоїстоїзадачідорівнює:

y₁ = 0

y₂ = 1

y₃ = 0

Z(Y) = 10*0+11*1+32*0 = 11

Завдання 3

Розв’язати транспортну задачу.

Розв’язок

Побудова математичної моделі . Нехай x_ij — кількість продукції, що перевозиться з і -го пункту виробництва до j -го споживача . Перевіримо необхідність і достатність умоврозв'язання задачі:

Умова балансу дотримується. Запаси рівні потребам. Отже, модель транспортної задачі є закритою.

Занесемо вихідні дані у таблицю.

Розпочинаємо будувати математичну модель даної задачі:

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

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

Загальні витрати, пов’язані з транспортуванням продукції, визначаються як сума добутків обсягів перевезеної продукції на вартості транспортування од. продукції до відповідного замовника і за умовою задачі мають бути мінімальними. Тому формально це можна записати так:

minZ =1x ₁₁ +4x ₁₂ +2x ₁₃ +1x ₁₄ +2x ₁₅ +2x ₂₁ +2x ₂₂ +3x ₂₃ +1x ₂₄ +3x ₂₅ +3x ₃₁ +4x ₃₂ +5x ₃₃ +6x ₃₄ + +7x ₃₅ .

Загалом математична модель сформульованої задачі має вигляд:

minZ =1x ₁₁ +4x ₁₂ +2x ₁₃ +1x ₁₄ +2x ₁₅ +2x ₂₁ +2x ₂₂ +3x ₂₃ +1x ₂₄ +3x ₂₅ +3x ₃₁ +4x ₃₂ +5x ₃₃ +6x ₃₄ + +7x ₃₅ .

за умов:

Запишемо умови задачі у вигляді транспортної таблиці та складемо її перший опорний план у цій таблиці методом «північно-західного кута».

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

Підрахуємо число зайнятих клітин таблиці, їх 7, а має бути m+n-1=7. Отже, опорний план є не виродженим.

Перевіримо оптимальність опорного плану. Знайдемо потенціали u_i , v_i . по зайнятих клітинам таблиці, в яких u_i + v_i = c_ij , вважаючи, що u₁ = 0:

u ₁ =0, u ₂ =1, u ₃ =5, v ₁ =1, v ₂ =4, v ₃ =2 v ₄ =1, v ₅ =2. Ці значення потенціалів першого опорного плану записуємо у транспортну таблицю.

Потім згідно з алгоритмом методу потенціалів перевіряємо виконання другої умови оптимальності u_i + v_j ≤ c_ij (для порожніх клітинок таблиці).

Опорний план не є оптимальним, тому що існують оцінки вільних клітин для яких u_i + v_i >c_ij

(2;2): 1 + 4 > 2; ∆₂₂ = 1 + 4 - 2 = 3

(2;4): 1 + 1 > 1; ∆₂₄ = 1 + 1 - 1 = 1

(3;1): 5 + 1 > 3; ∆₃₁ = 5 + 1 - 3 = 3

(3;2): 5 + 4 > 4; ∆₃₂ = 5 + 4 - 4 = 5

(3;3): 5 + 2 > 5; ∆₃₃ = 5 + 2 - 5 = 2

max(3,1,3,5,2) = 5

Тому від нього необхідно перейти до другого плану, змінивши співвідношення заповнених і порожніх клітинок таблиці. Вибираємо максимальну оцінку вільної клітини (3;2): 4. Для цього в перспективну клітку (3;2) поставимо знак «+», а в інших вершинах багатокутника чергуються знаки «-», «+», «-». Цикл наведено в таблиці.

Тепер необхідно перемістити продукцію в межах побудованого циклу. З вантажів х_ij що стоять в мінусових клітинах, вибираємо найменше, тобто у = min (1, 2) = 20. Додаємо 20 до обсягів вантажів, що стоять в плюсових клітинах і віднімаємо 20 з х_ij , що стоять в мінусових клітинах. В результаті отримаємо новий опорний план.

Усі інші заповнені клітинки першої таблиці, які не входили до циклу, переписуємо у другу таблицю без змін. Кількість заповнених клітинок у новій таблиці також має відповідати умові невиродженості плану, тобто дорівнювати (n + m – 1).

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

Перевіримо оптимальність опорного плану. Знайдемо потенціали u_i , v_i . по зайнятих клітинам таблиці, в яких u_i + v_i = c_ij , вважаючи, що u₁ = 0.

Опорний план не є оптимальним, тому що існують оцінки вільних клітин для яких u_i + v_i >c_ij

(2;4): 1 + 1 > 1; ∆₂₄ = 1 + 1 - 1 = 1

(3;1): 5 + 1 > 3; ∆₃₁ = 5 + 1 - 3 = 3

(3;3): 5 + 2 > 5; ∆₃₃ = 5 + 2 - 5 = 2

max(1,3,2) = 3

Вибираємо максимальну оцінку вільної клітини (3;1): 3

Для цього в перспективну клітку (3;1) поставимо знак «+», а в інших вершинах багатокутника чергуються знаки «-», «+», «-». Цикл наведено в таблиці.

З вантажів х_ij що стоять в мінусових клітинах, вибираємо найменше, тобто у = min (3, 5) = 50. Додаємо 50 до обсягів вантажів, що стоять в плюсових клітинах і віднімаємо 50 з Х_ij , що стоять в мінусових клітинах. В результаті отримаємо новий опорний план.

Перевіримо оптимальність опорного плану. Знайдемо потенціали u_i , v_i . по зайнятих клітинам таблиці, в яких u_i + v_i = c_ij , вважаючи, що u₁ = 0.

Опорний план не є оптимальним, тому що існують оцінки вільних клітин для яких u_i + v_i >c_ij

(2;2): 1 + 2 > 2; ∆₂₂ = 1 + 2 - 2 = 1

(2;4): 1 + 1 > 1; ∆₂₄ = 1 + 1 - 1 = 1

max(1,1) = 1

Вибираємомаксимальнуоцінкувільноїклітини (2;2): 2

Для цього в перспективну клітку (2;2) поставимо знак «+», а в інших вершинах багатокутника чергуються знаки «-», «+», «-». Цикл наведено в таблиці.

З вантажів х_ij що стоять в мінусових клітинах, вибираємо найменше, тобто у = min (3, 2) = 20. Додаємо 20 до обсягів вантажів, що стоять в плюсових клітинах і віднімаємо 20 з Х_ij , що стоять в мінусових клітинах.

В результаті отримаємо новий опорний план.

Перевіримо оптимальність опорного плану. Знайдемо потенціали u_i , v_i . по зайнятих клітинам таблиці, в яких u_i + v_i = c_ij , вважаючи, що u₁ = 0.

Опорний план не є оптимальним, тому що існують оцінки вільних клітин для яких u_i + v_i >c_ij

(2;4): 1 + 1 > 1; ∆₂₄ = 1 + 1 - 1 = 1

Вибираємомаксимальнуоцінкувільноїклітини (2;4): 1

Для цього в перспективну клітку (2;4)поставимо знак «+», а в інших вершинах багатокутника чергуються знаки «-», «+», «-». Цикл наведено в таблиці.

З вантажів х_ij що стоять в мінусових клітинах, вибираємо найменше, тобто у = min (2, 5) = 70. Додаємо 70 до обсягів вантажів, що стоять в плюсових клітинах і віднімаємо 70 з Х_ij , що стоять в мінусових клітинах.

В результаті отримаємо новий опорний план.