Архів якісних рефератів

Знайти реферат за назвою:         Розширений пошук

Меню сайту

Головна сторінка » Математика

Розв'язок задач лінійного математичного програмування графічним методом (розрахункова робота)

Розв'язок задачі лінійного програмування графічним методом

Приклад

 

 

F=-3x1+6x2 →max (min) (1)

x1+x2≤10

3x1+2x2≥15 (2)

x1,x2≥0 (3)

Розв'язування. Етап 1. Побудова області розв'язків.

З умови (3) x1,x2≥0 випливає, що область розв'язків в І чверті, тобто вище осі Оx1 і правіше осі Оx2.

Замінимо нерівності (2) на рівності. В результаті отримаємо рівняння прямих, які проведемо на площині.

Нерівність x1+x2≤10 замінимо рівнянням прямої x1+x2=10. Щоб провести цю пряму, потрібно знайти дві різні точки, що лежать на прямій. Покладемо x2=0, тоді x1=10, аналогічно при x1=0 знаходимо x2=10. Отже, пряма проходить через точки (10,0) і (0,10). Ця пряма позначена на рис.1 як лінія (1). Пряма (1) ділить площину на дві півплощини. Точки однієї півплощини задовольняють дану нерівність, а точки іншої – ні. Тестовою точкою може служити точка (0,0). Ця точка задовольняє нерівність 1∙0+1∙0≤10. Це означає, що точки півплощини, що містить точку (0,0), задовольняють дану нерівність. На рис.1 ця півплощина вказана стілкою. У випадку, коли точка (0,0) не задовольняє нерівність, півплощина розв'язків нерівності буде та, яка не містить цю точку.

Аналогічно нерівність 3x1+2x2≥15 замінимо рівнянням прямої 3x1+2x2=15 і проведемо цю пряму. Покладемо x2=0, тоді x1=5, при x1=0 одержимо x2=7,5. Пряма проходить через точки (5,0) і (0, 7½). Ця пряма на рис.1 позначена (2). Оскільки 3∙0+2∙0≤15, півплощина, що містить точку (0,0) є півплощиною розв'язків нерівності.

Нерівність x1+x2≥ 10 замінюємо рівнянням прямої x1+x2= 10. Якщо x2=0, то x1=0, якщо x1=0 та x2=10. Пряма проходить через точки (0,10) і позначена на рисунку (1).

Точки чотирьохкутника ABCD задовольняюсь одночасно всі нерівності (1) і (2), отже, є областю розв'язків задачі.

 

X2

X1

0

7,5

10

5

10

(1)

(2)

A

B

C

D

Рис.1

Етап 2. Знаходження оптимального розв'язку.

Вектор N=(dF/dx1, dF/dx2) називається градієнтом функції F(x1,x2). Градієнт вказує напрям найбільшого зростання функції F. Для F= -3x1+6x2 градієнт N=(-3;6).

Цільова функція F може зростати доти, доки пряма рівняння перетинає область розв'язків. Точка перетину області розв'язків і прямої рівняння, що відповідає максимальному значенню цільової функції F, буде точкою максимуму. На рис.1 видно, що максимальному розв'язку відповідає точка С, а мінімальному розв'язку – точка D. Точка C є точкою перетину прямих (1) і сиcтеми координат. Її координати знайдемо із системи рівнянь:


 

x1=0 x1=0 C(0;10)

x1+x2=10 x2=10

 

Знайдемо координати точки В:


 

x2=0 x1=10 D(10;0)

x1+x2=10 x2=0

Отже:

Fmin=F(D)= -30+0= -30

Fmax=F(C)=0+60=60

Xопт= Xmax = (0;10)

Xmin=(10;0)

Розв'язок задачі лінійного програмування М-методом

Приклад

 

 

F=-3x1+6x2 →max (1)

x1+x2≤10

3x1+2x2≥15 (2)

x1,x2≥0 (3)

Розвязування: Зведемо задачу до канонічної форми і запишемо у вигляді:

F=-3x1+6x2+0x3+0x4

x1+x2+x3=10

3x1+2x2-x4=15

x1;x2 ≥0

i=1,2,3,4

У рівності, в які не входять додаткові змінні із знаком «+», додамо штучні змінні, які будуть відігравати роль додаткових і будуть входити в початковий опорний розв'язок. Для зручності позначимо їх літерою S.

Одержимо рівності:

x1+x2+x3=10

3x1+2x2-x4+S1=15, де S1≥0.

Щоб штучні змінні в процесі ітерацій дорівнювали нулю, на них накладають штраф шляхом введення в цільову функцію виразу –М(S1) - в задачах максимізації, М(S1) – в задачах мінімізації, де М – досить велике додатне число, тобто розглядають нову лінійну функцію. В даному прикладі вона має вигляд Т==-3x1+6x2-М(S1). Таким чином одержали Т-задачу:

Т=-3x1+6x2-М(S1)→max

x1+x2+x3=10

3x1+2x2-x4+S1=15

Xi≥0, i=1,2,3,4;

S1≥0.

Оскільки, S1 – базисна змінна, а цільова функція Т не повинна містити базисних змінних, з другої рівності знайдемо S1=15-(3x1+2x2-x4) і підставимо в цільову функцію Т. Тоді Т= -3x1+6x2-М(15-(3x1+2x2-x4)). Отже, маємо:

x1+x2+x3=10

3x1+2x2-x4+S1=15

Т= -3x1+6x2+М(3x1+2x2-x4)-15М

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

 

Базисні

змінні

Х1

Х2

Х3

Х4

S1

bi

Відно

шення

Початкова

система

Х3

1

1

1

0

0

10

10

S1

3

2

0

-1

1

15

5

F

3

-6

0

0

0

0

 

M

-3М

-2М

0

М

0

-15М

 

І

Х3

0

1/3

1

1/3

-1/3

5

15

Х1

1

2/3

0

-1/3

1/3

5

15/2

F

0

-8

0

1

-1

-15

 

M

0

0

0

0

М

0

 

ІІ

Х3

-1/2

0

1

1/2

-1/2

5/2

5

Х2

3/2

1

0

-1/2

1/2

15/2

-15

F

12

0

0

-3

3

45

 

M

0

0

0

0

М

0

 

ІІІ

Х4

-1

0

2

1

-1

5

 

Х2

1

1

1

0

0

10

 

F

9

0

6

0

0

60

 

Умова допустимості . Як в задачах максимізації, так і в задачах мінімізації з базисних виводимо змінну, для якої відношення значення правої частини обмеження до додатного коефіцієнта розв'язувального стовпця мінімальне. Якщо таких змінних кілька, то вибираємо будь-яку з них.

Новий опорний розв'язок одержимо перерахуванням таблиці за правилом прямокутника. Отже, з базисних змінних виводимо x1 (відповідний рядок буде розв'язувальним). Таким чином елемент а21=3, буде розв'язувальним. Після перерахування одержимо таблицю І. В передостанньому стовпчику таблиці І маємо Х2 = (5;0;5;0;0)T, F=-15 де знак Т означає транспонування, тобто потрібно записати рядок стовпчиком. В F-рядку ітерації І найменший від'ємний коефіцієнт – (-8). Тому в базисні змінні вводимо небазисну змінну x2. За умовою допустимості (в останньому стовпці таблиці І найменший елемент 15/2) з базисних виводимо змінну x1. Розв'язувальний елемент а22=2/3.

В F-рядку ітерації ІІ вибираємо стовпчик з числом -3, тому в базисні змінні вводимо небазисну змінну х2. Отже, розв'язувальний елемент а24=-1/2. З ітерації ІІ випливає Х3 = (0;15/2; 5/2;0;0)T, F=45.

З ітерації 3 випливає Х4 = (0;10; 0;5;0)T, F=60. Оскільки в F-рядку немає від'ємних коефіцієнтів, одержаний розв'язок оптимальний. Отже, відповідь задачі Хопт= 10 Z max =60.

0

Знаходження мінімуму цільової функції

 

 

Приклад

 

 

F=-3x1+6x2→min (1)

x1+x2≤10

3x1+2x2≥15 (2)

x1,x2≥0 (3)

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

 

Базисні

змінні

Х1

Х2

Х3

Х4

S1

bi

Відно

шення

Початкова

система

Х3

1

1

1

0

0

10

10

S1

3

2

0

-1

1

15

5

F

3

-6

0

0

0

0

 

M

-2М

0

М

0

-15М

 

І

Х3

0

1/3

1

1/3

-1/3

5

15

Х1

1

2/3

0

-1/3

1/3

5

-15

F

0

-8

0

1

-1

-15

 

M

0

0

0

0

М

0

 

ІІ

Х4

0

1

3

1

-1

15

 

Х1

1

1

1

0

0

10

 

F

-1

-9

-1

0

0

-30

 

M

0

0

0

0

0

 

Умова допустимості . Як в задачах максимізації, так і в задачах мінімізації з базисних виводимо змінну, для якої відношення значення правої частини обмеження до додатного коефіцієнта розв'язувального стовпця мінімальне. Якщо таких змінних кілька, то вибираємо будь-яку з них.

Отже , на першому в базисні вводимо небазисну змінну Х 1 ,другий стовпчик буде роз'язувальним. Щоб з'ясувати, яку змінну потрібно вивести з базисних вибиремо одне з найменших відношень змінних (10:1 = 10, 15:1 = 15) отже другий рядочок буде розв'язувальним.

З таблиці видно,що Х 1 =(0,0,10,0,15)

F0 = 15M

З ітерації І випливає Х 1 = (5,0,5,0,0)

F1= 15

З ітерації ІІ випливає Х 1 = (10,0,0,15,0)

F1= -30


 

Отже, відповідь задачі Х опт = 10 Z min = -16

0

Розвязання транспортної задачі

Знаходження початкового опорного плану

Одним з можливих знаходження початкового опорного плану є метод мінімальної вартості. Цей метод знаходить кращий початковий розв'язок, ніж метод північно-західного кута, оскільки вибирає клітини з найменшою вартістю.

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

Приклад. А=(50;70;40;20)

В=(70;40;100)

 

1 9 6

С= 2 7 8

4 3 1

6 4 7

 

Розв'язання. Бачимо, що ∑аі = 50+70+40+20 = 180, ∑bj = 70+40+100 = 210. Отже, ∑аі ≤ ∑bj, умова балансу не виконана. Вводимо фіктивний пункт постачання А5, запаси якого а4 = ∑bj - ∑аі = 210-180=30, а вартості перевезень с41= с42= с43 =0.

Будуємо транспортну таблицю:

 

аi

bi

Өi

70

40

100

50

1

- 50

9

6

+

0

70

2

+ 20

7

20

8

- 30

1

40

4

3

1

40

-6

20

6

4

20

7

-2

30

9

9

9

30

2

Vi

1

6

7

 

Знайдемо початковий опорний план методом мінімальної вартості. Мінімальні вартості мають клітини (1,1) і (3,3): с1133=1. В клітину (1,1) запишемо 20 і виключимо з розгляду перший рядок. В частині таблиці, що залишилась мінімальну вартість с21=3 має клітина (2,1). Запишемо в клітину (2,1) 20 і виключимо з розгляду перший стовпчик. Після цього, мінімальну вартість с42= 4 має клітина (4;2). Запишемо в клітину (4;2) 20 і виключимо з розгляду четвертий рядок. Із залишених чисел, мінімальну вартість має с22=7, клітина (2,2). Запишемо в неї 20, і тим самим виключаємо другий стовпчик. У клітину (2,3) с23=8, запишемо 30. В єдину клітину (5,3) що залишилась, пишемо 30.

Знайдемо потенціали ui,vi. Покладемо u1 = 0. Тоді, v1 = 1, u2 = 1, далі знаходимо u3 = -6, u4 = -2, u5 = 2, v2 = 6 та v3 = 7. Обчислюємо оцінки вільних клітин:

12 = 0+6-9=-3,

13 = 0+7-6=1,

31 = -6+1-4=-9,

32 = -6+6-3=-3,

41 = -2+1-6=-7,

43 = -2+7-7=-2,

51 = 2+1-9=-6,

52 = 2+6-9=-1,

F=1*50+20*2+20*7+30*8+40*1+20*4+30*9=860

50 • •

X0= 20 20 30

• • 40

• 20 •

• • 30

Єдина клітина (1,3) має додатну оцінку. В клітині (1,3) ставимо «+» і утворюємо замкнений цикл. Розставляємо в клітинах знаки «+» і «-». Вибираємо Ө = min(1,3)=6. Після перерахування одержимо нову таблицю:

аi

bi

Өi

70

40

100

50

1

20

9

6

30

0

70

2

50

7

20

8

1

40

4

3

1

40

-5

20

6

4

20

7

-2

30

9

9

9

30

3

Vi

1

6

6

 

Знайдемо нові потенціали: u1=0, звідки u2=1, u3=-5, u4=-2, u5=3 та v1 = 1,

v2 = 6, v3 = 6. Аналогічно обчислюємо оцінки вільних клітин.

12 = 0+6-9=-3,

23 = 6+1-8=-1,

31 = -5+1-4=-8,

32 = -5+6-3=-2,

41 = -2+1-6=-7,

43 = -2+6-7=-3,

51 = 3+1-9=-5,

52 = 3+6-9=0

У зв'язку з тим, що не будуэться цикл, задача має опт розв'язок:

Fmin = 1*20+30*6+50*2+20*7+40*1+20*4-30*9=560


 

20 • 30 50 • •

50 20 • (1-α) 20 20 30

Хопт = • • 40 • • 40

• 20 • • 20 •

 





Реферат на тему: Розв'язок задач лінійного математичного програмування графічним методом (розрахункова робота)


Схожі реферати



5ka.at.ua © 2010 - 2016. Всі права застережені. При використанні матеріалів активне посилання на сайт обов'язкове.    
.