Xreferat.com » Рефераты по экономико-математическому моделированию » Економіко-математичне програмування

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

Размещено на /

Завдання 1


Побудувати математичну модель задачі.

На підприємстві виготовляються вироби двох видів А і В. Для цього використовується сировина чотирьох типів – І, ІІ, ІІІ, ІV, запаси якої дорівнюють, відповідно, 21; 4; 6; 10 од. Для виготовлення одного виробу А необхідна така кількість одиниць сировини чотирьох видів: 2; 1; 0; 2. Для виробу В – 3; 0; 1; 1 од. відповідно. Випуск одного виробу А дає 3 грн. од. прибутку, типу В – 2 грн. од. Скласти план виробництва, який забезпечує найбільший прибуток.


Сировина Норма витрат сировини, од Запаси сировини, од.

А В
І 2 3 21
ІІ 1 0 4
ІІІ 0 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 0 0 0 10.5

x6 4

1

0 0 0 0 1

4


x4 6 0 1 0 1 0 0 0

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

-100003

-2 0 0 0 0 0

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


План Базис В x1 x2 x3 x4 x5 x6 min
2 x3 13 0 3 1 0 0 -2 4.33

x1 4 1 0 0 0 0 1 0

x4 6 0 1 0 1 0 0 6

x5 2 0

1

0 0 1 -2

2

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

-2

0 0 0 100003 0

Даний план, також не оптимальний, тому будуємо знову нову симплексну таблицю. У якості ведучого виберемо елемент у стовбці х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 0 0 1 0
3 2 0 -1 0 0 1
4 7 0 0 1 0 0

Базисні перемінні це змінні, які входять тільки в одне рівняння системи обмежень і при тому з одиничним коефіцієнтом.

Вирішимо систему рівнянь відносно базисних змінних:

x6, x7, x5,

Вважаючи, що вільні змінні рівні 0, отримаємо перший опорний план:

X1 = (0,0,0,0,32,10,11)


План Базис В x1 x2 x3 x4 x5 x6 x7
0 x6 10 2 4 -1 0 0 1 0

x7 11 3 2 0 -1 0 0 1

x5 32 4 7 0 0 1 0 0

Індексний

рядок

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

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


План Базис В x1 x2 x3 x4 x5 x6 x7 min
1 x6 10 2

4

-1 0 0 1 0

2.5


x7 11 3 2 0 -1 0 0 1 5.5

x5 32 4 7 0 0 1 0 0 4.57

Індексний

рядок

F(X1) 21M -3+5M

-2+6M

-1M -1M 0 0 0 0

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


План Базис В x1 x2 x3 x4 x5 x6 x7 min
2 x2 2.5 0.5 1 -0.25 0 0 0.25 0 5

x7 6

2

0 0.5 -1 0 -0.5 1

3


x5 14.5 0.5 0 1.75 0 1 -1.75 0 29

Індексний

рядок

F(X2) 5+6M

-2+2M

0 -0.5+0.5M -1M 0 0.5-1.5M 0 0

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

План Базис В x1 x2 x3 x4 x5 x6 x7
3 x2 1 0 1 -0.375 0.25 0 0.375 -0.25

x1 3 1 0 0.25 -0.5 0 -0.25 0.5

x5 13 0 0 1.63 0.25 1 -1.63 -0.25

Індексний

рядок

F(X3) 11 0 0 0 -1 0 -1M 1-1M

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

Оптимальний план можна записати так:

x2 = 1

x1 = 3

x5 = 13

F(X) = 3*3 + 2*1 = 11

Складемо двоїсту задачу до прямої задачі.

2y1+3y2+4y3≤3

4y1+2y2+7y3≤2

10y1+11y2+32y3 => max

y1 ≥ 0

y2 ≥ 0

y3 ≤ 0

Рішення двоїстої задачі дає оптимальну систему оцінок ресурсів.

Використовуючи останню ітерацію прямої задачі знайдемо, оптимальний план двоїстої задачі.

З першої теореми двоїстості випливає, що Y = C*A-1.

Складемо матрицю A з компонентів векторів, що входять в оптимальний базис.


Визначивши зворотну матрицю А-1черезалгебраїчнідоповнення, отримаємо:


Як видно з останнього плану симплексного таблиці, зворотна матриця A-1розташована в стовпцях додаткових змінних.

Тогда Y = C*A-1 =


Оптимальний план двоїстоїзадачідорівнює:

y1 = 0

y2 = 1

y3 = 0

Z(Y) = 10*0+11*1+32*0 = 11


Завдання 3


Розв’язати транспортну задачу.


1 4 2 1 2 300
2 2 3 1 3 90
3 4 5 6 7 70
100 20 70 90 180

Розв’язок

Побудова математичної моделі. Нехай xij — кількість продукції, що перевозиться з і-го пункту виробництва до j-го споживача Економіко-математичне програмування. Перевіримо необхідність і достатність умоврозв'язання задачі:

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

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

Умова балансу дотримується. Запаси рівні потребам. Отже, модель транспортної задачі є закритою.

Занесемо вихідні дані у таблицю.



В1 В2 В3 В4 В5 Запаси
А1 1 4 2 1 2 300
А2 2 2 3 1 3 90
А3 3 4 5 6 7 70
Потреби 100 20 70 90 180

Розпочинаємо будувати математичну модель даної задачі:

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

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

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

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

Загальні витрати, пов’язані з транспортуванням продукції, визначаються як сума добутків обсягів перевезеної продукції на вартості транспортування од. продукції до відповідного замовника і за умовою задачі мають бути мінімальними. Тому формально це можна записати так:

minZ=1x11+4x12+2x13+1x14+2x15+2x21+2x22+3x23+1x24+3x25+3x31+4x32+5x33+6x34+ +7x35.

Загалом математична модель сформульованої задачі має вигляд:

minZ=1x11+4x12+2x13+1x14+2x15+2x21+2x22+3x23+1x24+3x25+3x31+4x32+5x33+6x34+ +7x35.

за умов:

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

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

Запишемо умови задачі у вигляді транспортної таблиці та складемо її перший опорний план у цій таблиці методом «північно-західного кута».


Ai Bj ui

b1 = 100 b2 = 20 b3 = 70 b4=90 b5=180
а1 = 300

1

100

4

[-]20

2

70

1

90

2

[+]20

u1 = 0
а2 = 90

2


2


3


1


3

90

u2 = 1
а3 = 70

3


4

[+]

5


6


7

[-]70

u3 = 5
vj v1 =1 v2 =4 v3 =2 v4 =1 v5 =2

В результаті отримано перший опорний план, який є допустимим, оскільки всі вантажі з баз вивезені, потреба магазинів задоволена, а план відповідає системі обмежень транспортної задачі.

Підрахуємо число зайнятих клітин таблиці, їх 7, а має бути m+n-1=7. Отже, опорний план є не виродженим.

Перевіримо оптимальність опорного плану. Знайдемо потенціали ui, vi. по зайнятих клітинам таблиці, в яких ui + vi = cij, вважаючи, що u1 = 0:

u1=0, u2=1, u3=5, v1=1, v2=4, v3=2 v4=1, v5=2. Ці значення потенціалів першого опорного плану записуємо у транспортну таблицю.

Потім згідно з алгоритмом методу потенціалів перевіряємо виконання другої умови оптимальності ui + vj ≤ cij(для порожніх клітинок таблиці).

Опорний план не є оптимальним, тому що існують оцінки вільних клітин для яких ui + vi>cij

(2;2): 1 + 4 > 2; ∆22 = 1 + 4 - 2 = 3

(2;4): 1 + 1 > 1; ∆24 = 1 + 1 - 1 = 1

(3;1): 5 + 1 > 3; ∆31 = 5 + 1 - 3 = 3

(3;2): 5 + 4 > 4; ∆32 = 5 + 4 - 4 = 5

(3;3): 5 + 2 > 5; ∆33 = 5 + 2 - 5 = 2

max(3,1,3,5,2) = 5

Тому від нього необхідно перейти до другого плану, змінивши співвідношення заповнених і порожніх клітинок таблиці. Вибираємо максимальну оцінку вільної клітини (3;2): 4. Для цього в перспективну клітку (3;2) поставимо знак «+», а в інших вершинах багатокутника чергуються знаки «-», «+», «-». Цикл наведено в таблиці.

Тепер необхідно перемістити продукцію в межах побудованого циклу. З вантажів хij що стоять в мінусових клітинах, вибираємо найменше, тобто у = min (1, 2) = 20. Додаємо 20 до обсягів вантажів, що стоять в плюсових клітинах і віднімаємо 20 з хij, що стоять в мінусових клітинах. В результаті отримаємо новий опорний план.

Усі інші заповнені клітинки першої таблиці, які не входили до циклу, переписуємо у другу таблицю без змін. Кількість заповнених клітинок у новій таблиці також має відповідати умові невиродженості плану, тобто дорівнювати (n + m – 1).

Отже, другий опорний план транспортної задачі матиме такий вигляд:

Ai Bj ui

b1 = 100 b2 = 20 b3 = 70 b4=90 b5=180
а1 = 300

1

[-]100

4


2

70

1

90

2

[+] 40

u1 = 0
а2 = 90

2


2


3


1


3

90

u2 = 1
а3 = 70

3

[+]

4

20

5


6


7

[-] 50

u3 = 5
vj v1 =1 v2 =-1 v3 =2 v4 =1 v5 =2

Перевіримо оптимальність опорного плану. Знайдемо потенціали ui, vi. по зайнятих клітинам таблиці, в яких ui + vi = cij, вважаючи, що u1 = 0.

Опорний план не є оптимальним, тому що існують оцінки вільних клітин для яких ui + vi>cij

(2;4): 1 + 1 > 1; ∆24 = 1 + 1 - 1 = 1

(3;1): 5 + 1 > 3; ∆31 = 5 + 1 - 3 = 3

(3;3): 5 + 2 > 5; ∆33 = 5 + 2 - 5 = 2

max(1,3,2) = 3

Вибираємо максимальну оцінку вільної клітини (3;1): 3

Для цього в перспективну клітку (3;1) поставимо знак «+», а в інших вершинах багатокутника чергуються знаки «-», «+», «-». Цикл наведено в таблиці.

З вантажів хij що стоять в мінусових клітинах, вибираємо найменше, тобто у = min (3, 5) = 50. Додаємо 50 до обсягів вантажів, що стоять в плюсових клітинах і віднімаємо 50 з Хij, що стоять в мінусових клітинах. В результаті отримаємо новий опорний план.


Ai Bj ui

b1 = 100 b2 = 20 b3 = 70 b4=90 b5=180
а1 = 300

1

[-] 50

4


2

70

1

90

2

[+] 90

u1 = 0
а2 = 90

2


2

[+]

3


1


3

[-]90

u2 = 1
а3 = 70

3

[+] 50

4

[-] 20

5


6


7


u3 = 2
vj v1 =1 v2 =2 v3 =2 v4 =1 v5 =2

Перевіримо оптимальність опорного плану. Знайдемо потенціали ui, vi. по зайнятих клітинам таблиці, в яких ui + vi = cij, вважаючи, що u1 = 0.

Опорний план не є оптимальним, тому що існують оцінки вільних клітин для яких ui + vi>cij

(2;2): 1 + 2 > 2; ∆22 = 1 + 2 - 2 = 1

(2;4): 1 + 1 > 1; ∆24 = 1 + 1 - 1 = 1

max(1,1) = 1

Вибираємомаксимальнуоцінкувільноїклітини (2;2): 2

Для цього в перспективну клітку (2;2) поставимо знак «+», а в інших вершинах багатокутника чергуються знаки «-», «+», «-». Цикл наведено в таблиці.

З вантажів хij що стоять в мінусових клітинах, вибираємо найменше, тобто у = min (3, 2) = 20. Додаємо 20 до обсягів вантажів, що стоять в плюсових клітинах і віднімаємо 20 з Хij, що стоять в мінусових клітинах.

В результаті отримаємо новий опорний план.


Ai Bj ui

b1 = 100 b2 = 20 b3 = 70 b4=90 b5=180
а1 = 300

1

30

4


2

70

1

[-]90

2

[+] 110

u1 = 0
а2 = 90

2


2

20

3


1

[+]

3

[-] 70

u2 = 1
а3 = 70

3

70

4


5


6


7


u3 = 2
vj v1 =1 v2 =1 v3 =2 v4 =1 v5 =2

Перевіримо оптимальність опорного плану. Знайдемо потенціали ui, vi. по зайнятих клітинам таблиці, в яких ui + vi = cij, вважаючи, що u1 = 0.

Опорний план не є оптимальним, тому що існують оцінки вільних клітин для яких ui + vi>cij

(2;4): 1 + 1 > 1; ∆24 = 1 + 1 - 1 = 1

Вибираємомаксимальнуоцінкувільноїклітини (2;4): 1

Для цього в перспективну клітку (2;4)поставимо знак «+», а в інших вершинах багатокутника чергуються знаки «-», «+», «-». Цикл наведено в таблиці.

З вантажів хij що стоять в мінусових клітинах, вибираємо найменше, тобто у = min (2, 5) = 70. Додаємо 70 до обсягів вантажів, що стоять в плюсових клітинах і віднімаємо 70 з Хij, що стоять в мінусових клітинах.

В результаті отримаємо новий опорний план.


Ai Bj ui

b1 = 100 b2 = 20 b3 = 70 b4=90 b5=180
а1 = 300

1

30

4


2

70

1

20

2

180

u1 = 0
а2 = 90

2


2

20

3


1

70

3


u2 = 1
а3 = 70

3

70

4


5


6


7


u3 = 2
vj v1 =1 v2 =1 v3 =2 v4 =1 v5 =2

Перевіримо оптимальність опорного плану, тобто повторюємо описані раніше дії.

Знайдемо потенціали ui, vi. по зайнятих клітинам таблиці, в яких ui + vi = cij, вважаючи, що u1 = 0.

Перевірка останнього плану на оптимальність за допомогою методу потенціалів показує, що він оптимальний.

Розрахуємо значення цільової функції відповідно до другого опорного плану задачі:

F(x) = 1*30 + 2*70 + 1*20 + 2*180 + 2*20 + 1*70 + 3*70 = 870

За оптимальним планом перевезень загальна вартість перевезень всієї продукції є найменшою і становить 870 грн.

Завдання 4

математична модель симплекс транспортна задача екстремум

Знайти графічним методом екстремуми функцій в області, визначеній нерівностями.

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

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

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

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

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

Розв’язок

Побудуємо область допустимих рішень, тобто вирішимо графічно систему нерівностей. Для цього побудуємо кожну пряму і визначимо півплощини, задані нерівностями (півплощини позначені штрихом).


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

Межі області

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


Цільова функція F(x) =>max

Розглянемо цільову функцію завдання F = 4X1+7X2 =>max.

Побудуємо пряму, що відповідає значенню функції F = 0: F = 4X1+7X2 = 0. Будемо рухати цю пряму паралельним чином. Оскільки нас цікавить максимальне рішення, тому рухався прямо до останнього торкання позначеної області. На графіку ця пряма позначена пунктирною лінією.

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

Рівний масштаб

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

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

Пряма F(x) = const перетинає область у точці B. Оскільки точка B отримана в результаті перетину прямих 2 i 5, то її координати задовольняють рівнянням цих прямих:

x1+x2≤5

x1=0

Вирішивши систему рівнянь, одержимо: x1 = 0, x2 = 5

Звідки знайдемо максимальне значення цільової функції:

F(X) = 4*0 + 7*5 = 35


Размещено на

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту

Похожие рефераты: