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

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

Завдання 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 робочих клітинок.

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

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



В1 В2 В3 В4 В5 В6 Запаси
А1 1 4 7 9 1 0 250
А2 2 3 1 2 4 0 300
А3 2 1 3 1 4 0 150
Потреби 110 80 100 90 70 250

Забезпечивши закритість розв'язуваної задачі, розпочинаємо будувати математичну модель даної задачі:


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


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

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


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


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


minZ=1x11+4x12+7x13+9x14+1x15+0x16+2x21+3x22+1x23+2x24+4x25+0x26+2x31+1x32+3x33+1x34+ +4x35+0x36.


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


minZ=1x11+4x12+7x13+9x14+1x15+0x16+2x21+3x22+1x23+2x24+4x25+0x26+2x31+1x32+3x33+1x34+ +4x35+0x36.


за умов:


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

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


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


Ai Bj ui

b1 = 110 b2 = 80 b3 = 100 b4=90 b5=70 b6=250
а1 = 250

1

110

4

80

7

[-]60

9


1

[+]

0


u1 = 0
а2 = 300

2


3


1

[+]40

2

90

4

[-]70

0

100

u2 = -6
а3 = 150

2


1


3


1


4


0

150

u3 = -6
vj v1 =1 v2 =4 v3 =7 v4 =8 v5 =10 v6 =6

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

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

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

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

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

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

(1;5): 0 + 10 > 1

(1;6): 0 + 6 > 0

(3;4): -6 + 8 > 1

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

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

Для цього у порожню клітинку А1B5 переносимо менше з чисел хij, які розміщені в клітинках зі знаком «–». Одночасно це саме число хij додаємо до відповідних чисел, що розміщені в клітинках зі знаком «+», та віднімаємо від чисел, що розміщені в клітинках, позначених знаком «–».

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

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


Ai Bj ui

b1 = 110 b2 = 80 b3 = 100 b4=90 b5=70 b6=250
а1 = 250

1

110

4

[-]80

7


9


1

[+]60

0


u1 = 0
а2 = 300

2


3


1

100

2

90

4

[-]10

0

[+]100

u2 = 3
а3 = 150

2


1

[+]

3


1


4


0

[-]150

u3 = 3
vj v1 =1 v2 =4 v3 =-2 v4 =-1 v5 =1 v6 =-3

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

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

(2;1): 3 + 1 > 2

(2;2): 3 + 4 > 3

(3;1): 3 + 1 > 2

(3;2): 3 + 4 > 1

(3;4): 3 + -1 > 1

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

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

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


Ai Bj ui

b1 = 110 b2 = 80 b3 = 100 b4=90 b5=70 b6=250
а1 = 250

1

110

4

[-]70

7


9


1

70

0

[+]

u1 = 0
а2 = 300

2


3


1

100

2

90

4


0

110

u2 = -3
а3 = 150

2


1

[+]10

3


1


4


0

[-]140

u3 = -3
vj v1 =1 v2 =4 v3 =4 v4 =5 v5 =1 v6 =3

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

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

(1;6): 0 + 3 > 0

(3;4): -3 + 5 > 1

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

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

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

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


Ai Bj ui

b1 = 110 b2 = 80 b3 = 100 b4=90 b5=70 b6=250
а1 = 250

1

110

4


7


9


1

70

0

70

u1 = 0
а2 = 300

2


3


1

100

2

[-]90

4


0

[+]110

u2 = 0
а3 = 150

2


1

80

3


1

[+]

4


0

[-]70

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

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

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

(3;4): 0 + 2 > 1

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

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

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

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


Ai Bj ui

b1 = 110 b2 = 80 b3 = 100 b4=90 b5=70 b6=250
а1 = 250

1

110

4


7


9


1

70

0

70

u1 = 0
а2 = 300

2


3


1

100

2

20

4


0

180

u2 = 0
а3 = 150

2


1

80

3


1

70

4


0


u3 = -1
vj v1 =1 v2 =2 v3 =1 v4 =2 v5 =1 v6 =0

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

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

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

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

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

F(x) = 1*110 + 1*70 + 0*70 + 1*100 + 2*20 + 0*180 + 1*80 + 1*70 = 470

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


Завдання 4


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


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

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

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

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

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


Розв’язок

Необхідно знайти мінімальне значення цільової функції F = 2X1+4X2 =>min, при системі обмежень:


x1+2x2≥2 (1)

2x1+2x2≤10 (2)

x1+x2=6 (3)


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


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

Межі області


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

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


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

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


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

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


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

Область допустимих значень необмежена.

Размещено на

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

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

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

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