Реферат: Економіко-математичне програмування

Завдання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 1

x3

21 2 3 1 10.5

x6

4

1

1

4

x4

6 1 1

x5

10 2 1 1 5 Індексний рядок F(X1) -400000

-100003

-2

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

План Базис В

x1

x2

x3

x4

x5

x6

min 2

x3

13 3 1 -2 4.33

x1

4 1 1

x4

6 1 1 6

x5

2

1

1 -2

2

Індексний рядок F(X2) 12

-2

100003

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

План  Базис  В

 x1

 x2

 x3

 x4

 x5

 x6

Min  3

 x3

 7  0  0  1  0  -3  4  4.33

 x1

 4  1  0  0  0  0  1  0

 x4

 4  0  0  0  1  -1  2  6

 x2

 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 1

x7

11 3 2 -1 1

x5

32 4 7 1

Індексний

рядок

F(X0) 21M -3+5M -2+6M -1M -1M

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

План Базис В

x1

x2

x3

x4

x5

x6

x7

min 1

x6

10 2

4

-1 1

2.5

x7

11 3 2 -1 1 5.5

x5

32 4 7 1 4.57

Індексний

рядок

F(X1) 21M -3+5M

-2+6M

-1M -1M

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

План Базис В

x1

x2

x3

x4

x5

x6

x7

min 2

x2

2.5 0.5 1 -0.25 0.25 5

x7

6

2

0.5 -1 -0.5 1

3

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.

еще рефераты
Еще работы по экономико-математическому моделированию