Математичне програмування

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

На підприємстві виготовляються вироби двох видів А і В. Для цього використовується сировина чотирьох типів – І, ІІ, ІІІ, І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

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

Розв’язок

Пряма задача лінійного програмування має вигляд:

При обмеженнях:

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

Для досягнення відповідного вигляду помножимо 1-у та 2-у нерівність на -1

1х₁ -4ч₂ ≥-8

-1х₁ +1х₂ ≥-3

В результаті отримаємо наступні матриці:

Для складання двоїстої задачі лінійного програмування знайдемо матриці А, В, С^Т .

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

F(Y)= -8Y₁ -3Y₂ +9Y₃ (max)

Обмеження:

1Y₁ -1Y₂ +2Y₃ ≤2

-4Y₁ +1Y₂ +1Y₃ ≤1

Y₁ ≥0

Y₂ ≥0

Y₃ ≥0

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

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

-x₁ +4x₂ ≤8

x₁ -x₂ ≤3

2x₁ +x₂ ≥9

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

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

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

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

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

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

F(X) = 2 x₁ + x₂ +M x₆ =>min

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

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

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

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

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

x₃ = 8

x₁ = 4

x₂ = 1

F(X) = 2*4 + 1*1 = 9

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

F(Y)= -8Y₁ -3Y₂ +9Y₃ (max)

Обмеження:

1Y₁ -1Y₂ +2Y₃ ≤2

-4Y₁ +1Y₂ +1Y₃ ≤1

Y₁ ≥0

Y₂ ≥0

Y₃ ≥0

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

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

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

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

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

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

x₃ = 1

x₂ = 0

F(X) = -3*0 + 9*1 = 9

Завдання 3

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

Розв’язок

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

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

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

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

Забезпечивши закритість розв'язуваної задачі, розпочинаємо будувати математичну модель даної задачі:

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

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

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

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

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

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

за умов:

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

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

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

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

Тоді всі інші потенціали однозначно визначаються з цієї системи рівнянь: u ₁ =0, u ₂ = 7, u ₃ = 7, v ₁ =5, v ₂ =1, v ₃ = -6 v ₄ =1, v ₅ = -5, v ₆ = -7. Ці значення потенціалів першого опорного плану записуємо у транспортну таблицю.

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

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

(2;1): 7 + 5 > 7

(3;1): 7 + 5 > 4

(3;2): 7 + 1 > 1

Тому відньогонеобхідно перейти до другого плану, змінившиспіввідношеннязаповнених і порожніхклітиноктаблиці. Вибираємомаксимальнуоцінкувільноїклітини (А ₃ B ₁ ): 4

Ставимо в ній знак «+». Для визначення клітинки, що звільняється, будуємо цикл, починаючи з клітинки А ₃ B ₁ , та позначаємо вершини циклу почергово знаками «–» і «+». Тепер необхідно перемістити продукцію в межах побудованого циклу. Для цього у порожню клітинку А ₃ B ₁ переносимо менше з чисел х_ij , які розміщені в клітинках зі знаком «–». Одночасно це саме число х_ij додаємо до відповідних чисел, що розміщені в клітинках зі знаком «+», та віднімаємо від чисел, що розміщені в клітинках, позначених знаком «–».

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

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

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

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

(1;6): 0 + 1 > 0

(2;1): 7 + 5 > 7

(2;5): 7 + 3 > 2

(2;6): 7 + 1 > 0

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

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

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

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

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

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