Методика економіко-математичного програмування (стр. 1 из 3)
Завдання 1
Для виготовлення виробів №1 і №2 є 100 кг металу. На виготовлення виробу №1 витрачається 2 кг металу, а на виріб №2 – 4 кг.
Скласти план виробництва, що забезпечує одержання найбільшого прибутку від продажу виробів, якщо відпускна вартість одного виробу №1 становить 3 грн. од., а виробу №2 – 2 грн. од., причому виробів №1 потрібно виготовити не більше 40 штук, а виробів №2 – 20 шт.
| Сировина | Вироби | Кількість сировини | |
| В1 | В2 | ||
| Метал | 2 | 4 | 100 |
| Вартість, грн. кг | 3 | 2 | |
Розв’язок
Складаємо математичну модель задачі. Позначимо через х1 кількість виробу №1, що виготовляє підприємство за деяким планом, а через х2 кількість виробу №2. Тоді прибуток, отриманий підприємством від реалізації цих виробів, складає
∫ = 3х1+2х2.
Витрати сировини на виготовлення такої кількості виробів складають відповідно:
CI =2х1+4х2,
Оскільки запаси сировини обмежені, то повинні виконуватись нерівності:
2х1+4х2≤100
Окрім того, виробів №1 потрібно виготовити не більше 40 штук, а виробів №2 – 20 шт., тобто повинні виконуватись ще нерівності: х1≤40, х2≤20.
Таким чином, приходимо до математичної моделі:
Знайти х1, х2такі, що функція ∫ = 3х1+2х2досягає максимуму при системі обмежень:
Розв'язуємо задачу лінійного програмування симплексним методом.
Для побудови першого опорного плану систему нерівностей приведемо до системи рівнянь шляхом введення додаткових змінних.
2x1 + 4x2 + 1x3 + 0x4 + 0x5 = 100
1x1 + 0x2 + 0x3 + 1x4 + 0x5 = 40
0x1 + 1x2 + 0x3 + 0x4 + 1x5 = 20
Матриця коефіцієнтів A = a(ij) цієї системи рівнянь має вигляд:
Базисні змінні це змінні, які входять лише в одне рівняння системи обмежень і притому з одиничним коефіцієнтом.
Вирішимо систему рівнянь відносно базисних змінних:
x3, x4, x5
Вважаючи, що вільні змінні рівні 0, отримаємо перший опорний план:
X1 = (0,0,100,40,20)
Оскільки завдання вирішується на максимум, то ведучий стовпець вибираємо по максимальному негативному кількістю та індексного рядку. Всі перетворення проводимо до тих пір, поки не вийдуть в індексному рядку позитивні елементи.
Складаємо симплекс-таблицю:
| План | Базис | В | x1 | x2 | x3 | x4 | x5 | min |
| 1 | x3 | 100 | 2 | 4 | 1 | 0 | 0 | 50 |
| x4 | 40 | 1 | 0 | 0 | 1 | 0 | 40 | |
| x5 | 20 | 0 | 1 | 0 | 0 | 1 | 0 | |
| Індексний рядок | F(X1) | 0 | -3 | -2 | 0 | 0 | 0 | 0 |
Оскільки, в індексному рядку знаходяться негативні коефіцієнти, поточний опорний план неоптимальний, тому будуємо новий план. У якості ведучого виберемо елемент у стовбці х1, оскільки значення коефіцієнта за модулем найбільше.
| План | Базис | В | x1 | x2 | x3 | x4 | x5 | min |
| 2 | x3 | 20 | 0 | 4 | 1 | -2 | 0 | 5 |
| x1 | 40 | 1 | 0 | 0 | 1 | 0 | 0 | |
| x5 | 20 | 0 | 1 | 0 | 0 | 1 | 20 | |
| Індексний рядок | F(X2) | 120 | 0 | -2 | 0 | 3 | 0 | 0 |
Даний план, також не оптимальний, тому будуємо знову нову симплексну таблицю. У якості ведучого виберемо елемент у стовбці х2.
| План | Базис | В | x1 | x2 | x3 | x4 | x5 | min |
| 3 | x2 | 5 | 0 | 1 | 0,25 | -0,5 | 0 | 5 |
| x1 | 40 | 1 | 0 | 0 | 1 | 0 | 0 | |
| x5 | 15 | 0 | 0 | -0,25 | 0,5 | 1 | 20 | |
| Індексний рядок | F(X3) | 130 | 0 | 0 | 0,5 | 2 | 0 | 0 |
Оскільки всі оцінки >0, то знайдено оптимальний план, що забезпечує максимальний прибуток: х1=40, х2=5. Прибуток, при випуску продукції за цим планом, становить 130 грн.
Завдання 2
Записати двоїсту задачу до поставленої задачі лінійного програмування. Розв’язати одну із задач симплексним методом і визначити оптимальний план іншої задачі.
Розв’язок
Розв’яжемо задачу лінійного програмування симплексним методом.
Визначимо мінімальне значення цільової функції F(X) = x1+3x2при наступних умовах-обмежень.
9x1+10x2≥45
5x1-x2≤42
-x1+13x2≤4
Для побудови першого опорного плану систему нерівностей приведемо до системи рівнянь шляхом введення додаткових змінних.
9x1 + 10x2-1x3 + 0x4 + 0x5 = 45
5x1-1x2 + 0x3 + 1x4 + 0x5 = 42
-1x1 + 13x2 + 0x3 + 0x4 + 1x5 = 4
Введемо штучні змінні x.
9x1 + 10x2-1x3 + 0x4 + 0x5 + 1x6 = 45
5x1-1x2 + 0x3 + 1x4 + 0x5 + 0x6 = 42
-1x1 + 13x2 + 0x3 + 0x4 + 1x5 + 0x6 = 4
Для постановки задачі на мінімум цільову функцію запишемо так:
F(X) = x1+3x2+Mx6 =>min
Вважаючи, що вільні змінні рівні 0, отримаємо перший опорний план:
X1 = (0,0,0,42,4,45).
| План | Базис | В | x1 | x2 | x3 | x4 | x5 | х6 |
| 0 | х6 | 45 | 9 | 10 | -1 | 0 | 0 | 1 |
| x4 | 42 | 5 | -1 | 0 | 1 | 0 | 0 | |
| х5 | 4 | -1 | 13 | 0 | 0 | 1 | 0 | |
| Індексний рядок | F(X0) | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
Переходимо до основного алгоритму симплекс-методу.
| План | Базис | В | x1 | x2 | x3 | x4 | x5 | x6 | min |
| 1 | х6 | 45 | 9 | 10 | -1 | 0 | 0 | 1 | 5,5 |
| x4 | 42 | 5 | -1 | 0 | 1 | 0 | 0 | 0 | |
| х5 | 4 | -1 | 13 | 0 | 0 | 1 | 0 | 0,3077 | |
| Індексний рядок | F(X1) | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
Оскільки, в індексному рядку знаходяться позитивні коефіцієнти, поточний опорний план неоптимальний, тому будуємо новий план. У якості ведучого виберемо елемент у стовбці х2, оскільки значення коефіцієнта за модулем найбільше.
| План | Базис | В | x1 | x2 | x3 | x4 | x5 | x6 | min |
| 2 | х6 | 41,92 | 9,77 | 0 | -1 | 0 | -0,7692 | 1 | 4,29 |
| x4 | 42,31 | 4,92 | 0 | 0 | 1 | 0,0769 | 0 | 8,59 | |
| х2 | 0,3077 | -0,0769 | 1 | 0 | 0 | 0,0769 | 0 | 0 | |
| Індексний рядок | F(X2) | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
Даний план, також не оптимальний, тому будуємо знову нову симплексну таблицю. У якості ведучого виберемо елемент у стовбці х1.
| План | Базис | В | x1 | x2 | x3 | x4 | x5 | x6 | min |
| 3 | х1 | 4,29 | 1 | 0 | -0,1024 | 0 | -0,0787 | 0,1024 | 0 |
| x4 | 21,18 | 0 | 0 | 0,5039 | 1 | 0,4646 | -0,5039 | 45,59 | |
| х2 | 0,6378 | 0 | 1 | -0,0079 | 0 | 0,0709 | 0,0079 | 9 | |
| Індексний рядок | F(X3) | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
Даний план, також не оптимальний, тому будуємо знову нову симплексну таблицю. У якості ведучого виберемо елемент у стовбці х5.
| План | Базис | В | x1 | x2 | x3 | x4 | x5 | x6 |
| 4 | х1 | 5 | 1 | 1,11 | -0,1111 | 0 | 0 | 0,1111 |
| x4 | 17 | 0 | -6,56 | 0,5556 | 1 | 0 | -0,5556 | |
| х5 | 9 | 0 | 14,11 | -0,1111 | 0 | 1 | 0,1111 | |
| Індексний рядок | F(X4) | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
Оптимальний план можна записати так:
x1 = 5
x4 = 17
x5 = 9
F(X) = 1*5 = 5
Складемо двоїсту задачу до поставленої задачі лінійного програмування.
9y1+5y2-y3≤1
10y1-y2+13y3≤3
45y1+42y2+4y3 => max
y1 ≥ 0
y2 ≤ 0
y3 ≤ 0
Рішення двоїстої задачі дає оптимальну систему оцінок ресурсів. Використовуючи останню інтеграцію прямої задачі знайдемо, оптимальний план двоїстої задачі. Із теореми двоїстості слідує, що Y = C*A-1.
Сформуємо матрицю A із компонентів векторів, які входять в оптимальний базис.
Визначивши обернену матрицю А-1 через алгебраїчне доповнення, отримаємо:
Як видно із останнього плану симплексної таблиці, обернена матриця A-1 розміщена у стовбцях додаткових змінних.
Тоді Y = C*A-1 =
Запишемо оптимальний план двоїстої задачі:
y1 = 0.11
y2 = 0
y3 = 0
Z(Y) = 45*0.11+42*0+4*0 = 5
Завдання 3
Розв’язати транспортну задачу.
| 1 | 4 | 7 | 9 | 1 | 250 |
| 2 | 3 | 1 | 2 | 4 | 300 |
| 2 | 1 | 3 | 1 | 4 | 150 |
| 110 | 80 | 100 | 90 | 70 |
Розв’язок
Побудова математичної моделі. Нехай xij — кількість продукції, що перевозиться з і-го пункту виробництва до j-го споживача
. Оскільки 
, то задачу треба закрити, тобто збалансувати (зрівняти) поставки й потреби: 
У нашому випадку робиться це введенням фіктивного постачальника, оскільки
. З уведенням фіктивного споживача транспортній таблиці додатково заявляється n робочих клітинок.