Оптимізація економічних показників (стр. 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
Записати двоїсту задачу до поставленої задачі лінійного програмування. Розв’язати одну із задач симплексним методом і визначити оптимальний план іншої задачі. Оптимальні результати перевірити графічно.
Розв’язок
Пряма задача лінійного програмування має вигляд:
При обмеженнях:
Оскільки, у прямій задачі лінійного програмування необхідно знайти мінімум функції, то приведемо першопочаткову умову до вигляду:
Для досягнення відповідного вигляду помножимо 1-у нерівність на -1
-8х1-6ч2≥-48
В результаті отримаємо наступні матриці:
Для складання двоїстої задачі лінійного програмування знайдемо матриці А, В, СТ.
Відповідно, двоїста задача лінійного програмування матиме вигляд:
F(Y)=-48Y1-5Y2+12Y3 (max)
Обмеження:
-8Y1+1Y2+4Y3≤-1
-6Y1-2Y2+1Y3≤2
Y1≥0
Y2≥0
Y3≥0
Розв’яжемо задачу лінійного програмування симплексним методом.
Визначимо мінімальне значення цільової функції F(X)=-x1+2x2 при наступних умовах-обмежень.
8x1+6x2≤48
x1-2x2≥-5
4x1+x2≤12
Для побудови першого опорного плану систему нерівностей приведемо до системи рівнянь шляхом введення додаткових змінних.
Оскільки маємо змішані умови-обмеження, то введемо штучні змінні x.
8x1 + 6x2 + 1x3 + 0x4 + 0x5 + 0x6 = 48
1x1-2x2 + 0x3-1x4 + 0x5 + 1x6 = -5
4x1 + 1x2 + 0x3 + 0x4 + 1x5 + 0x6 = 12
Для постановки задачі на мінімум цільову функцію запишемо так:
F(X) = -1 x1 +2 x2 +M x6 =>min
| План | Базис | В | x1 | x2 | x3 | x4 | x5 | x6 | min |
| 0 | x3 | 33 | 11 | 0 | 1 | -3 | 0 | 3 | 0 |
| x2 | 2.5 | -0.5 | 1 | 0 | 0.5 | 0 | -0.5 | 0 | |
| x5 | 9.5 | 4.5 | 0 | 0 | -0.5 | 1 | 0.5 | 0 | |
| Індексний рядок | F(X) | 5 | 0 | 0 | 0 | 1 | 0 | -100001 | 0 |
У базисному стовпчику всі елементи позитивні.
Переходимо до основного алгоритму симплекс-методу.
| План | Базис | В | x1 | x2 | x3 | x4 | x5 | x6 | min |
| 1 | x3 | 33 | 11 | 0 | 1 | -3 | 0 | 3 | 0 |
| x2 | 2.5 | -0.5 | 1 | 0 | 0.5 | 0 | -0.5 | 5 | |
| x5 | 9.5 | 4.5 | 0 | 0 | -0.5 | 1 | 0.5 | 0 | |
| Індекснийрядок | F(X1) | 5 | 0 | 0 | 0 | 1 | 0 | -100001 | 0 |
Поточний опорний план неоптимальний, тому що в індексному рядку знаходяться позитивні коефіцієнти. Враховуючи вказане будуємо новий план здійснивши відповідні розрахунки. У якості ведучого виберемо стовпець, відповідної змінної x4, так як найбільший коефіцієнт за модулем.
| План | Базис | В | x1 | x2 | x3 | x4 | x5 | x6 | min |
| 2 | x3 | 48 | 8 | 6 | 1 | 0 | 0 | 0 | 6 |
| x4 | 5 | -1 | 2 | 0 | 1 | 0 | -1 | 0 | |
| x5 | 12 | 4 | 1 | 0 | 0 | 1 | 0 | 3 | |
| Індекснийрядок | F(X2) | 0 | 1 | -2 | 0 | 0 | 0 | -100000 | 0 |
Поточний опорний план неоптимальний, тому що в індексному рядку знаходяться позитивні коефіцієнти. Враховуючи вказане будуємо новий план здійснивши відповідні розрахунки. У якості ведучого виберемо стовпець, відповідної змінної x1, так як найбільший коефіцієнт за модулем.
| План | Базис | В | x1 | x2 | x3 | x4 | x5 | x6 | min |
| 3 | x3 | 24 | 0 | 4 | 1 | 0 | -2 | 0 | 6 |
| x4 | 8 | 0 | 2.25 | 0 | 1 | 0.25 | -1 | 0 | |
| x1 | 3 | 1 | 0.25 | 0 | 0 | 0.25 | 0 | 3 | |
| Індекснийрядок | F(X3) | -3 | 0 | -2.25 | 0 | 0 | -0.25 | -100000 | 0 |
Остаточний варіант симплекс-таблиці оптимальний, тому що в індексному рядку знаходяться негативні коефіцієнти.
Оптимальний план можна записати так:
x3 = 24
x4 = 8
x1 = 3
F(X) = -1*3 = -3
Визначаємо оптимальний план двоїстої задачі до поставленої задачі лінійного програмування.
F(Y) = -48Y1-5Y2+12Y3 (max)
Обмеження:
-8Y1+1Y2+4Y3≤-1
-6Y1-2Y2+1Y3≤2
Y1≥0
Y2≥0
Y3≥0
лінійний програмування транспортна задача
Оскільки, у правій частині присутні від’ємні значення, перемножимо відповідні строки на (-1).
Визначимо максимальне значення цільової функції
F(X) = -48x1-5x2+12x3 при наступних обмеженнях: