Математичне програмування (стр. 1 из 3)
Завдання 1
Побудувати математичну модель задачі.
Фірма, що спеціалізується на виробництві електроприладів, отримала замовлення на виготовлення 100 електроплит. Конструкторами запропоновано до випуску три моделі плит А, В і С за ціною відповідно 100, 60 та 50 грн.од. Норми витрат сировини для виготовлення однієї електроплити різних моделей та запас сировини на фірмі наведено в таблиці.
| Сировина | Норми витрат сировини, грн.од. | Запас сировини, грн.од. | ||
| А | В | С | ||
| І | 10 | 4 | 5 | 700 |
| ІІ | 3 | 2 | 1 | 400 |
| Ціна, грн.од. | 100 | 60 | 50 | |
Визначити оптимальні обсяги виробництва електроплит різних моделей, що максимізують дохід фірми.
Розв’язок
Складаємо математичну модель задачі. Позначимо через х1 кількість електроплит 1-ї моделі, що виготовляє фірма за деяким планом, а через х2 кількість електроплит 2-ї моделі та через та через х3 кількість виробів 3-ї моделі Тоді прибуток, отриманий фірмою від реалізації цих електроплит, складає
∫ = 100х1 + 60х2+ 50х3.
Витрати сировини на виготовлення такої кількості виробів складають відповідно:
А =10х1 + 4х2 + 5х3,
В =3х1 + 2х2 + 1х3,
Оскільки запаси сировини обмежені, то повинні виконуватись нерівності:
10х1 + 4х2 + 5х3 ≤ 700
3х1 + 2х2 + 1х3 ≤ 400
Оскільки, кількість виробів є величина невід'ємна, то додатково повинні виконуватись ще нерівності: х1> 0, х2> 0, х3> 0.
Таким чином, приходимо до математичної моделі (задачі лінійного програмування):
Знайти х1 , х2, х3 такі, що функція∫ = 100х1 + 60х2 + 50х3 досягає максимуму при системі обмежень:
Розв'язуємо задачу лінійного програмування симплексним методом. Введемо балансні змінні х4 ≥ 0, х5 ≥ 0. Їх величина поки що невідома, але така, що перетворює відповідну нерівність у точну рівність. Після цього, задача лінійного програмування набуде вигляду: ∫ = 100х1 + 60х2 + 50х3 → max при обмеженнях
де х1,...,х5>0
Оскільки завдання вирішується на максимум, то ведучий стовпець вибирають по максимальному негативному кількістю та індексного рядку. Всі перетворення проводять до тих пір, поки не вийдуть в індексному рядку позитивні елементи.
Складаємо симплекс-таблицю:
| Базис | x1 | х2 | x3 | x4 | x5 | b | |
| I | II | III | IV | V | VI | VII | |
| а | 0 | 10 | 4 | 5 | 1 | 0 | 700 |
| б | 0 | 3 | 2 | 1 | 0 | 1 | 400 |
| d | Індексний рядок, ∆i | 100 | 60 | 50 | 0 | 0 | 0 |
Складаємо перший план. Оскільки змінних х4,х5в цільовій функції немає, то їм відповідають коефіцієнти 0;
| План | Базис | В | x1 | x2 | x3 | x4 | x5 | min |
| 1 | x4 | 700 | 10 | 4 | 5 | 1 | 0 | 70 |
| x5 | 400 | 3 | 2 | 1 | 0 | 1 | 133.33 | |
| Індексний рядок | F(X1) | 0 | -100 | -60 | -50 | 0 | 0 | 0 |
Оскільки, в індексному рядку знаходяться негативні коефіцієнти, поточний опорний план неоптимальний, тому будуємо новий план. У якості ведучого виберемо елемент у стовбці х1, оскільки значення коефіцієнта за модулем найбільше.
| План | Базис | В | x1 | x2 | x3 | x4 | x5 | min |
| 2 | x1 | 70 | 1 | 0.4 | 0.5 | 0.1 | 0 | 175 |
| x5 | 190 | 0 | 0.8 | -0.5 | -0.3 | 1 | 237.5 | |
| Індексний рядок | F(X2) | 7000 | 0 | -20 | 0 | 10 | 0 | 0 |
Даний план, також не оптимальний, тому будуємо знову нову симплексну таблицю. У якості ведучого виберемо елемент у стовбці х2.
| План | Базис | В | x1 | x2 | x3 | x4 | x5 | min |
| 3 | x2 | 175 | 2.5 | 1 | 1.25 | 0.25 | 0 | 175 |
| x5 | 50 | -2 | 0 | -1.5 | -0.5 | 1 | 237.5 | |
| Індексний рядок | F(X3) | 10500 | 50 | 0 | 25 | 15 | 0 | 0 |
Оскільки всі оцінки >0, то знайдено оптимальний план, що забезпечує максимальний прибуток: х1=0, х2=175, х3=0, х4=0, х5=50. Прибуток, при випуску продукції за цим планом, становить 10500 грн.
Дамо економічну трактову розв'язку: щоби досягнути максимально можливого, за умов задачі, прибутку (10500 грн.), необхідно виробів другої моделі випустити 175 од.
Завдання 2
Записати двоїсту задачу до поставленої задачі лінійного програмування. Розв’язати одну із задач симплексним методом і визначити оптимальний план іншої задачі. Оптимальні результати перевірити графічно.
Розв’язок
Розв’яжемо задачу лінійного програмування симплексним методом.
Визначимо максимальне значення цільової функції F(X) = x1+2x2 за таких умов-обмежень.
2x1+3x2≤6
2x1+4x2≤4
2x1+x2≥4
Для побудови першого опорного плану систему нерівностей приведемо до системи рівнянь шляхом введення додаткових змінних (перехід до канонічної форми).
2x1 + 3x2 + 1x3 + 0x4 + 0x5 = 6
2x1 + 4x2 + 0x3 + 1x4 + 0x5 = 4
2x1 + 1x2 + 0x3 + 0x4-1x5 = 4
Введемо штучні змінні x.
2x1 + 3x2 + 1x3 + 0x4 + 0x5 + 0x6 = 6
2x1 + 4x2 + 0x3 + 1x4 + 0x5 + 0x6 = 4
2x1 + 1x2 + 0x3 + 0x4-1x5 + 1x6 = 4
Для постановки завдання на максимум цільову функцію запишемо так:
F(X) = x1+2x2 - Mx6 => max
Отриманий базис називається штучним, а метод рішення називається методом штучного базису.
З рівнянь висловлюємо штучні змінні:
x6 = 4-2x1-x2+x5
які підставимо в цільову функцію:
F(X) = x1 + 2x2 - M(4-2x1-x2+x5) => max
або
F(X) = (1+2M)x1+(2+1M)x2+(-1M)x5+(-4M) => max
Матриця коефіцієнтів A = a(ij) цієї системи рівнянь має вигляд:
Вирішимо систему рівнянь відносно базисних змінних:
x3, x4, x6,
Вважаючи, що вільні змінні рівні 0, отримаємо перші опорний план:
X1 = (0,0,6,4,0,4)
| План | Базис | В | x1 | x2 | x3 | x4 | x5 | x6 |
| 0 | x3 | 6 | 2 | 3 | 1 | 0 | 0 | 0 |
| x4 | 4 | 2 | 4 | 0 | 1 | 0 | 0 | |
| x6 | 4 | 2 | 1 | 0 | 0 | -1 | 1 | |
| Індексний рядок | F(X0) | -4M | -1-2M | -2-1M | 0 | 0 | 1M | 0 |
Переходимо до основного алгоритму симплекс-методу.
| План | Базис | В | x1 | x2 | x3 | x4 | x5 | x6 | min |
| 1 | x3 | 6 | 2 | 3 | 1 | 0 | 0 | 0 | 3 |
| x4 | 4 | 2 | 4 | 0 | 1 | 0 | 0 | 2 | |
| x6 | 4 | 2 | 1 | 0 | 0 | -1 | 1 | 2 | |
| Індексний рядок | F(X1) | -4M | -1-2M | -2-1M | 0 | 0 | 1M | 0 | 0 |
індексний рядок симплекс метод
Оскільки, в індексному рядку знаходяться негативні коефіцієнти, поточний опорний план неоптимальний, тому будуємо новий план. У якості ведучого виберемо елемент у стовбці х1, оскільки значення коефіцієнта за модулем найбільше.
| План | Базис | В | x1 | x2 | x3 | x4 | x5 | x6 | min |
| 2 | x3 | 2 | 0 | 2 | 1 | 0 | 1 | -1 | 1 |
| x4 | 0 | 0 | 3 | 0 | 1 | 1 | -1 | 0 | |
| x1 | 2 | 1 | 0.5 | 0 | 0 | -0.5 | 0.5 | 4 | |
| Індексний рядок | F(X2) | 2 | 0 | -1.5 | 0 | 0 | -0.5 | 0.5+1M | 0 |
Даний план, також не оптимальний, тому будуємо знову нову симплексну таблицю. У якості ведучого виберемо елемент у стовбці х2.
| План | Базис | В | x1 | x2 | x3 | x4 | x5 | x6 |
| 3 | x3 | 2 | 0 | 0 | 1 | -0.6667 | 0.3333 | -0.3333 |
| x2 | 0 | 0 | 1 | 0 | 0.3333 | 0.3333 | -0.3333 | |
| x1 | 2 | 1 | 0 | 0 | -0.1667 | -0.6667 | 0.6667 | |
| Індексний рядок | F(X3) | 2 | 0 | 0 | 0 | 0.5 | 0 | 1M |
Остаточний варіант симплекс-таблиці оптимальний, тому що в індексному рядку знаходяться позитивні коефіцієнти.
Оптимальний план можна записати так:
x3 = 2
x2 = 0
x1 = 2
F(X) = 1*2 + 2*0 = 2
Складемо двоїсту задачу до прямої задачі.
2y1+2y2+2y3≥1
3y1+4y2+y3≥2
6y1+4y2+4y3 => min
y1 ≥ 0
y2 ≥ 0
y3 ≤ 0
Рішення двоїстої задачі дає оптимальну систему оцінок ресурсів.
Використовуючи останню ітерацію прямої задачі знайдемо, оптимальний план двоїстої задачі.
З першої теореми двоїстості випливає, що Y = C*A-1.
Складемо матрицю A з компонентів векторів, що входять в оптимальний базис.
Визначивши зворотну матрицю А-1 через алгебраїчні доповнення, отримаємо:
Як видно з останнього плану симплексного таблиці, зворотна матриця A-1 розташована в стовпцях додаткових змінних .
Тоді Y = C*A-1 =
Оптимальний план двоїстої задачі дорівнює:
y1 = 0
y2 = 0.5
y3 = 0
Z(Y) = 6*0+4*0.5+4*0 = 2
Завдання 3
Розв’язати транспортну задачу.
| 5 | 2 | 3 | 6 | 1 | 150 |
| 1 | 1 | 4 | 4 | 2 | 320 |
| 4 | 1 | 2 | 3 | 5 | 400 |
| 100 | 120 | 100 | 200 | 300 |
Розв’язок
Побудова математичної моделі. Нехай xij — кількість продукції, що перевозиться з і-го пункту виробництва до j-го споживача
. Оскільки 
, то задачу треба закрити, тобто збалансувати (зрівняти) поставки й потреби: 
