Реферат: Економіко-математичне програмування
Завдання1
Побудуватиматематичну модель задачі.
На підприємствівиготовляються вироби двох видів А і В. Для цього використовується сировиначотирьох типів – І, ІІ, ІІІ, ІV, запаси якої дорівнюють, відповідно, 21; 4; 6;10 од. Для виготовлення одного виробу А необхідна така кількість одиницьсировини чотирьох видів: 2; 1; 0; 2. Для виробу В – 3; 0; 1; 1 од. відповідно.Випуск одного виробу А дає 3 грн. од. прибутку, типу В – 2 грн. од. Скластиплан виробництва, який забезпечує найбільший прибуток.
Сировина Норма витрат сировини, од Запаси сировини, од. А В І 2 3 21 ІІ 1 4 ІІІ 1 6 ІV 2 1 10 Ціна, грн. од. 3 2
Розв’язок
Складаємоматематичну модель задачі. Позначимо через х1 кількістьвиробів 1-ї моделі, що виготовляє підприємство за деяким планом, а через х2кількість виробів 2-ї моделі. Тоді прибуток, отриманий підприємством відреалізації цих виробів, складає
∫= 3х1+2х2.
Витратисировини на виготовлення такої кількості виробів складають відповідно:
CI=2х1 + 3х2,
CII=1х1 + 0х2,
CIII=0х1 + 1х2,
CIV=2х1 + 1х2,
Оскількизапаси сировини обмежені, то повинні виконуватись нерівності:
2х1+ 3х2≤ 21
1х1≤4
1х2≤6
2х1+ 1х2≤ 10
Оскільки,кількість виробів є величина невід'ємна, то додатково повинні виконуватись щенерівності: х1> 0, х2> 0.
Такимчином, приходимо до математичної моделі (задачі лінійного програмування):
Знайтих1, х2 такі, що функція ∫ = 3х1+2х2досягаємаксимуму при системі обмежень:
/>
Розв'язуємозадачу лінійного програмування симплексним методом.
Дляпобудови першого опорного плану систему нерівностей приведемо до системирівнянь шляхом введення додаткових змінних. Оскільки маємо змішаніумови-обмеження, то введемо штучні змінні x.
2x1+ 3x2 + 1x3 + 0x4 + 0x5 + 0x6= 21
1x1+ 0x2 + 0x3 + 0x4 + 0x5 + 1x6= 4
0x1+ 1x2 + 0x3 + 1x4 + 0x5 + 0x6= 6
2x1+ 1x2 + 0x3 + 0x4 + 1x5 + 0x6= 10
дех1,..., х6>0
Дляпостановки задачі на максимум цільову функцію запишемо так:
F(X)= 3 x1 +2 x2 — M x6 =>max
Оскількизавдання вирішується на максимум, то ведучий стовпець вибираємо помаксимальному негативному кількістю та індексного рядку. Всі перетворенняпроводять до тих пір, поки не вийдуть в індексному рядку позитивні елементи.
Складаємосимплекс-таблицю:
План Базис Вx1
x2
x3
x4
x5
x6
min 1x3
21 2 3 1 10.5x6
41
14
x4
6 1 1x5
10 2 1 1 5 Індексний рядок F(X1) -400000-100003
-2Оскільки,в індексному рядку знаходяться негативні коефіцієнти, поточний опорний планнеоптимальний, тому будуємо новий план. У якості ведучого виберемо елемент устовбці х1, оскільки значення коефіцієнта за модулем найбільше.
План Базис Вx1
x2
x3
x4
x5
x6
min 2x3
13 3 1 -2 4.33x1
4 1 1x4
6 1 1 6x5
21
1 -22
Індексний рядок F(X2) 12-2
100003Данийплан, також не оптимальний, тому будуємо знову нову симплексну таблицю. Уякості ведучого виберемо елемент у стовбці х2.
План Базис Вx1
x2
x3
x4
x5
x6
Min 3x3
7 0 0 1 0 -3 4 4.33x1
4 1 0 0 0 0 1 0x4
4 0 0 0 1 -1 2 6x2
2 0 1 0 0 1 -2 2 Індексний рядок F(X3) 16 0 0 0 0 2 99999 0Оскільки всіоцінки >0, то знайдено оптимальний план, що забезпечує максимальнийприбуток: х1=4, х2=2. Прибуток, при випуску продукції зацим планом, становить 16 грн.
Завдання2
Записати двоїстузадачу до поставленої задачі лінійного програмування. Розв’язати одну із задачсимплексним методом і визначити оптимальний план іншої задачі. Оптимальнірезультати перевірити графічно.
/>
/>
Розв’язок
Вирішимопряму задачу лінійного програмування симплексним методом, з використанням симплексноготаблиці.
Визначимомінімальне значення цільової функції F(X) = 3x1+2x2 затаких умов-обмежень.
2x1+4x2≥10
3x1+2x2≥11
4x1+7x2≤32
Дляпобудови першого опорного плану систему нерівностей наведемо до системи рівняньшляхом введення додаткових змінних (перехід до канонічної форми).
2x1+ 4x2-1x3 + 0x4 + 0x5 = 10
3x1+ 2x2 + 0x3-1x4 + 0x5 = 11
4x1+ 7x2 + 0x3 + 0x4 + 1x5 = 32
Введемоштучні змінні x.
2x1+ 4x2-1x3 + 0x4 + 0x5 + 1x6+ 0x7 = 10
3x1+ 2x2 + 0x3-1x4 + 0x5 + 0x6+ 1x7 = 11
4x1+ 7x2 + 0x3 + 0x4 + 1x5 + 0x6+ 0x7 = 32
Дляпостановки завдання на мінімум цільову функцію запишемо так:
F(X)= 3x1+2x2+Mx6+Mx7 => min
Завикористання штучних змінних, що вводяться в цільову функцію, накладається такзваний штраф величиною М, дуже велике позитивне число, яке зазвичай незадається.
Отриманийбазис називається штучним, а метод рішення називається методом штучного базису.
Причомуштучні змінні не мають відношення до змісту поставленого завдання, однак вонидозволяють побудувати стартову точку, а процес оптимізації змушує ці змінні прийматинульові значення та забезпечити допустимість оптимального рішення.
Зрівнянь висловлюємо штучні змінні:
x6= 10-2x1-4x2+x3
x7= 11-3x1-2x2+x4
якіпідставимо в цільову функцію:
F(X)= 3x1 + 2x2 + M(10-2x1-4x2+x3)+ M(11-3x1-2x2+x4) => min
або
F(X)= (3-5M)x1+(2-6M)x2+(1M)x3+(1M)x4+(21M)=> min
Матрицякоефіцієнтів A = a(ij) цієї системи рівнянь має вигляд:
2 4 -1 1 3 2 -1 1 4 7 1Базисніперемінні це змінні, які входять тільки в одне рівняння системи обмежень і при томуз одиничним коефіцієнтом.
Вирішимосистему рівнянь відносно базисних змінних:
x6,x7, x5,
Вважаючи,що вільні змінні рівні 0, отримаємо перший опорний план:
X1= (0,0,0,0,32,10,11)
План Базис Вx1
x2
x3
x4
x5
x6
x7
x6
10 2 4 -1 1x7
11 3 2 -1 1x5
32 4 7 1Індексний
рядок
F(X0) 21M -3+5M -2+6M -1M -1MПереходимодо основного алгоритму симплекс-методу.
План Базис Вx1
x2
x3
x4
x5
x6
x7
min 1x6
10 24
-1 12.5
x7
11 3 2 -1 1 5.5x5
32 4 7 1 4.57Індексний
рядок
F(X1) 21M -3+5M-2+6M
-1M -1MОскільки, віндексному рядку знаходяться позитивні коефіцієнти, поточний опорний планнеоптимальний, тому будуємо новий план. У якості ведучого виберемо елемент устовбці х2, оскільки значення коефіцієнта за модулем найбільше.
План Базис Вx1
x2
x3
x4
x5
x6
x7
min 2x2
2.5 0.5 1 -0.25 0.25 5x7
62
0.5 -1 -0.5 13
x5
14.5 0.5 1.75 1 -1.75 29Індексний
рядок
F(X2) 5+6M-2+2M
-0.5+0.5M -1M 0.5-1.5MДаний план,також не оптимальний, тому будуємо знову нову симплексну таблицю. У якостіведучого виберемо елемент у стовбці х1.