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

Завдання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 50 x4 40

1

1

40

x5 20 1 1 Індексний рядок F(X1)

-3

-2

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

План Базис В x1 x2 x3 x4 x5 min 2 x3 20

4

1 -2

5

x1 40 1 1 x5 20 1 1 20 Індексний рядок F(X2) 120

-2

3

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

План Базис В x1 x2 x3 x4 x5 min 3 x2 5 1 0,25 -0,5 5 x1 40 1 1 x5 15 -0,25 0,5 1 20 Індексний рядок F(X3) 130 0,5 2

Оскількивсі оцінки >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 х6 45 9 10 -1 1 x4 42 5 -1 1 х5 4 -1 13 1 Індексний рядок F(X0)

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

План Базис В x1 x2 x3 x4 x5 x6 min 1 х6 45 9 10 -1 1 5,5 x4 42 5 -1 1 х5 4 -1

13

1 0,3077 Індексний рядок F(X1)

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

План Базис В x1 x2 x3 x4 x5 x6 min 2 х6 41,92

9,77

-1 -0,7692 1

4,29

x4 42,31 4,92 1 0,0769 8,59 х2 0,3077 -0,0769 1 0,0769 Індексний рядок F(X2)

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

План Базис В x1 x2 x3 x4 x5 x6 min 3 х1 4,29 1 -0,1024 -0,0787 0,1024 x4 21,18 0,5039 1 0,4646 -0,5039 45,59 х2 0,6378 1 -0,0079

0,0709

0,0079

9

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

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

План Базис В x1 x2 x3 x4 x5 x6 4 х1 5 1 1,11 -0,1111 0,1111 x4 17 -6,56 0,5556 1 -0,5556 х5 9 14,11 -0,1111 1 0,1111 Індексний рядок F(X4)

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

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 250 А2 2 3 1 2 4 300 А3 2 1 3 1 4 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

[+]

u1 = 0

а2 = 300

2 3

1

[+]40

2

90

4

[-]70

100

u2 = -6

а3 = 150

2 1 3 1 4

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

u1 = 0

а2 = 300

2 3

1

100

2

90

4

[-]10

[+]100

u2 = 3

а3 = 150

2

1

[+]

3 1 4

[-]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

[+]

u1 = 0

а2 = 300

2 3

1

100

2

90

4

110

u2 = -3

а3 = 150

2

1

[+]10

3 1 4

[-]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

70

u1 = 0

а2 = 300

2 3

1

100

2

[-]90

4

[+]110

u2 = 0

а3 = 150

2

1

80

3

1

[+]

4

[-]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

70

u1 = 0

а2 = 300

2 3

1

100

2

20

4

180

u2 = 0

а3 = 150

2

1

80

3

1

70

4

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. Будемо рухати цю прямупаралельним чином. Оскільки нас цікавить мінімальне рішення, тому рухався прямодо першого торкання позначеної області. На графіку ця пряма позначенапунктирною лінією.

/>

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

/>

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