Реферат: Розв'язання задач графічним методом, методом потенціалів, методом множників Лангранжа та симплекс-методом

Контрольнаробота

З дисциплiни:Математичне програмування

Варіант№5

 

Київ 2009 рiк.

 

Завдання1. Скласти математичну модель задачі та розв'язати її графічним методом

 

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

 

Група виробничого

устаткування

Кількість устаткування для випуску

одиниці продукції

Кількість

устаткування

в групі

Продукція І Продукція ІІ А 2 3 12 В 1 2 8 С 4 16 Прибуток, тис. грн. 1 3

Рішення:

Позначимо через x1і x2кількість продукції І і ІІ. Тоді умови для необхідногоустаткуваннябудуть описуватися наступними нерівностями:

2x1+ 3x2≤ 12

1x1+ 2x2≤ 8

4x1+ 0x2≤ 16

x1,x2≥ 0

А умова найбільшогоприбутку:

f= 1x1+ 3x2→ max

Для розв'язання задачіграфічним методом замість нерівностей системи обмежень беремо відповіднірівняння граничних прямих і будуємо їх графіки:

/>

Звертаючи увагу напівплощини, в яких виконуються відповідні нерівності, знаходимо спільнуобласть, помічену сірим кольором. Стрілкою вказуємо вектор зростання цільовоїфункції f, компоненти якого (1;3) дорівнюють коефіцієнтам при x1 і x2 у виразі цієїфункції.

Бачимо, щомаксимального значення функція f набуває в точці М, на перетині прямої 2x1+ 3x2= 12 і вісі x2.Підставляючи x1= 0 в це рівняння, отримуємо:

2*0 + 3x2= 12

x2= 4

М = (x1;x2)= (0; 4)

Значення функції fв точці М:

fmax= 1*0+3*4 = 12

Відповідь:

Найбільший прибуток урозмірі 12 тис. грн. буде від реалізації 4 одиниць продукції ІІ без випускупродукції І.

Завдання 2. Для заданої ЗЛП побудувати двоїсту,розв'язати одну з пари двоїстих задач симплекс-методом і за її розв'язкомзнайти розв'язок іншої задачі

F= x1 + x2 → max

/>x1 — x2 ≥ -6

3x1 + 4x2 ≤ 26

2x1 — x2 ≤ 10

x1 ≥0, x2 ≥ 0

 

Рішення.

Перепишемо ЗЛП,помноживши першу нерівність на -1:

F= x1 + x2 → max

-x1+ x2 ≤ 6

3x1+ 4x2 ≤ 26

2x1 — x2≤ 10

x1 ≥0, x2 ≥ 0

Двоїста задачазаписується у вигляді:

F*= 6y1 + 26y2 + 10y3 → min

-1y1+ 3y2 + 2y3 ≥ 1

1y1+ 4y2 — 1y3 ≥ 1

y1≥ 0, y2 ≥ 0, y3 ≥ 0

Зведемовихіднузадачудоканонічноїформи[5, с.14]. Дляцього добавимо невід'ємні величини x3,x4,x5,щоб нерівності перетворити в рівняння:

F- x1 — x2 → max

-x1+ x2 + x3 = 6

3x1+ 4x2 + x4 = 26

2x1 — x2+ x5= 10

x1 ≥0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0, x5≥ 0

Розв'яжемо дану задачусимплекс-методом [5, с. 18]. Заповнюємо симплекс-таблицю початковимизначеннями, вибираємо стовпець (x1)з першим від'ємним значенням (-1) в останньому рядку, вибираємо рядок (x5)з найменшим значенням bi/xi(5) і виділяємо розв'язувальний елемент (2):

xб

b

x1

x2

x3

x4

x5

bi/xi

x3

6 -1 1 1 —

x4

26 3 4 1 26/3

x5

10 2 -1 1 5 (min) Δ -1 -1

Вводимо в базис x1замість x5і перераховуємо таблицю. Вибираємо стовпець (x2)з єдиним від'ємним значенням (-3/2) в останньому рядку, вибираємо рядок (x4)з найменшим значенням bi/xi(2) і виділяємо розв'язувальний елемент (11/2):

xб

b

x1

x2

x3

x4

x5

bi/xi

x3

11 1/2 1 1/2 22

x4

11 11/2 1 -3/2 2 (min)

x1

5 1 -1/2 1/2 — Δ 5 -3/2 1/2

Вводимо в базис x2замість x4і перераховуємо таблицю:

xб

b

x1

x2

x3

x4

x5

bi/xi

x3

10 1 -1/11 7/11 —

x2

2 1 2/11 -3/11 —

x1

6 1 1/11 4/11 — Δ 8 3/11 1/11

В останньому рядку незалишилося від'ємних величин, тому стовбець bмістить рішення вихідної задачі — максимум функції F:

x1= 6

x2= 2

Fmax= 8

Запишемо рішеннядвоїстої задачі з останнього рядка останньої симплекс-таблиці:

y1= 0

y2= 3/11

y3=1/11

F*min= 8

Відповідь:

Вихідна задача: Fmax= F(6; 2) = 8

Двоїста задача: F*min= F*(0;3/11; 1/11) = 8

Завдання 3. Розв'язатиметодом потенціалів транспортну задачу

ai \ bj

90 50 60 80 120 5 4 3 4 100 3 2 5 5 60 1 6 3 1

 

Рішення.

Підраховуємо загальнізапаси постачальників: 120 + 100 + 60 = 280

Підраховуємо загальніпотреби споживачів: 90 + 50 + 60 + 80 = 280

Дана модель закрита [5,с. 55], тому що загальні потреби споживачів дорівнюють загальним запасам постачальників.

Запишемо умову задачі увигляді наступної таблиці:

В1

В2

В3

В4

Запаси

А1

5 4 3 4 120

А2

3 2 5 5 100

А3

1 6 3 1 60 Потреби 90 50 60 80

 

Для визначення опорногоплану транспортної задачі застосуємо спочатку метод мінімального елемента [5,с. 50]. Для цього будемо послідовно вибирати клітинки з мінімальним тарифом іробити спробу максимально задовольнити вимоги споживачів і постачальників.

Перший мінімальнийелемент (1) знаходяться в клітинці А­3В­1, тому записуємов неї запас постачальника А­3 (60) і коректуємо колонки запасів тапотреб:

В1

В2

В3

В4

Запаси

А1

120

А2

100

А3

60 — — — Потреби 30 50 60 80

Наступні мінімальніелементи (2 та 3) знаходяться в клітинках А2В2, А1В3та А2В1, тому записуємо в них потреби споживачів В2(50), В3 (60) та В1 (30) і коректуємо колонки запасів тапотреб:

В1

В2

В3

В4

Запаси

А1

— — 60 60

А2

30 50 — 20

А3

60 — — — Потреби 80

Залишилися вільніклітинки А1В4 та А2В4, томузаписуємо в них запаси постачальників А1 (60) та А2 (20)і коректуємо колонки запасів та потреб:

В1

В2

В3

В4

Запаси

А1

— — 60 60

А2

30 50 — 20

А3

60 — — — Потреби

Підрахуємо вартістьперевезення для отриманого опорного плану:

60*3 + 60*4 + 30*3 +50*2 + 20*5 + 60*1 = 770

Для визначенняоптимальності отриманого опорного плану застосуємо метод потенціалів [5, с.51]. Для цього задамо нульовий потенціал першому рядку, а решту потенціаліввизначимо враховуючи отримані клітинки:

В1

В2

В3

В4

потенц.

А1

3 4

А2

3 2 5 1

А3

1 1 потенц. 2 1 3 4

Визначаємо оцінки длявільних клітинок, знаходимо максимальну додатну оцінку (4) в клітинці А­3В­4і позначаємо для неї цикл [5, с. 51]:

В1

В2

В3

В4

потенц.

А1

-3 -3

А2

(+) -1 (-) 1

А3

(-) -4 1 4(+) 1 потенц. 2 1 3 4

В вершинах циклу зізнаком (-) вибираємо мінімальне значення (20) у клітинці А­2В­4опорного плану. Додаємо його до вершин циклу зі знаком (+) і віднімаємо йоговід вершин циклу зі знаком (-):

В1

В2

В3

В4

Запаси

А1

60 60

А2

50 50

А3

40 20 Потреби

При цьому вартістьперевезення для цього поліпшеного опорного плану:

60*3 + 60*4 + 50*3 +50*2 + 40*1 + 20*1 = 730

Для визначенняоптимальності поліпшеного опорного плану знову застосуємо метод потенціалів —задамо нульовий потенціал першому рядку, а решту потенціалів визначимовраховуючи отримані клітинки:

В1

В2

В3

В4

потенц.

А1

3 4

А2

3 2 -1

А3

1 1 -3 потенц. 4 3 3 4

Визначаємо оцінки длявільних клітинок:

В1

В2

В3

В4

потенц.

А1

-1 -1

А2

-3 -2 -1

А3

-6 -3 -3 потенц. 4 3 3 4

Оскільки всі отриманіоцінки не більші нуля, то останній опорний план є оптимальним [5, с. 51].Отримуємо оптимальний план перевезення:

Маршрут Кількість Вартість

А­1 — В3

60 180

А­1 — В­4

60 240

А­2 — В­1

50 150

А­2 — В­2

50 100

А­3 — В­1

40 40

А­3 — В­4

20 20 Всього 730

Відповідь:

Вартість оптимальногоплану транспортної задачі дорівнює 730.

Завдання 4. Методом множників Лагранжа знайти умовніекстремуми функцій

f= x12+ x1x2+ x22 — 3x1 — 6x2 заумови x1+ x2= 3.

Рішення.

Перепишемо умову увигляді c(x1,x2)= 0:

x1+ x2 — 3 = 0

Тоді функція Лагранжа[5, с. 153]:

L(x1,x2, λ) = f(x1, x2) + λ c(x1,x2)

L(x1,x2, λ) = x12 + x1x2+ x22 — 3x1 — 6x2 + λ(x1+ x2 — 3)

УточціекстремумучастинніпохідніфункціїЛагранжадорівнюютьнулю[5, с.154]:

∂L(x1,x2, λ) / ∂x1 = 2x1 + x2 — 3 + λ

∂L(x1,x2, λ) / ∂x2 = x1 + 2x2 — 6 + λ

Отримуємонаступнусистему:

2x1+ x2 — 3 + λ = 0

x1+ 2x2 — 6 + λ = 0

x1+ x2 — 3 = 0

Віднімаємодругерівняннясистемивідпершогоівизначаємоx2:

x1 — x2+ 3 = 0

x2= x1+ 3

Підставляємо отримане x2в третє рівняння системи:

x1= 0

x2= x1+ 3 = 3

Отже точка (0; 3) —умовний екстремум функції f,який дорівнює:

f(0;3) = 32 — 6*3 = -9

Розглянемо іншудовільну точку (3; 0), для якої виконується умова задачі. Значення функції дляцієї точки:

f(3;0) = 32 — 3*3 = 0

Оскільки f(0;3) < f(3; 0), то знайденийумовний екстремум — це умовний мінімум.

Відповідь: Умовниймінімум функції f досягається вточці (0; 3) і дорівнює -9.

Списоквикористаної літератури

1. Вітлінський В.В., Наконечний С.І.,Терещенко Т.О. Математичне програмування: Навчально-методичний посібник длясамостійного вивчення дисципліни. — К.: КНЕУ, 2001. — 248 с.

2. Заварыкин В.М., Житомирский В.Г.,Лапчик М.П. Численные методы: Учебное пособие для студентов. — М.: Просвещение,1991. — 176 с.

3. Лавренчук В.П., Веренич І.І.,Готинчан Т.І., Дронь В.С., Кондур О.С. Математичне програмування (методичнийпосібник для студентів економічних спеціальностей). — Чернівці: Рута, 1998. — 168с.

4. Наконечний С.І., Савіна С.С.Математичне програмування: Навчальний посібник. — К.: КНЕУ, 2003. — 452 с.

5. Попов Ю.Д., Тюптя В.І., Шевченко В.І.Методи оптимізації. — К.: КНУ, 2003. — 215 с.