Реферат Задачі математичного програмування

>Завдання 2

>Записатидвоїсту завдання допоставленоїзадачілінійногопрограмування.Розв’язати одну з завданьсимплексним методом йвизначитиоптимальний планіншоїзадачі.Оптимальнірезультатиперевіритиграфічно.

>Розв’язок

>Розв’яжемо завданнялінійногопрограмуваннясимплексним методом.

>ВизначимомінімальнезначенняцільовоїфункціїF(X) =4x1+2x2 принаступнихумовах-обмежень.

>x1-x24

>x1+3x26

>x1+2x22

Дляпобудови Першого опорного плану системунерівностейприведемо досистемирівнянь шляхомвведеннядодатковихзмінних.

Ос-кільки маємозмішаніумови-обмеження, товведемоштучнізмінні x.

>1x1-1x2 +1x3 +0x4 +0x5 = 4

>1x1 +3x2 +0x3 +1x4 +0x5 = 6

>1x1 +2x2 +0x3 +0x4-1x5 = 2

Для постановкизадачі намінімумцільовуфункціюзапишемо так:

>F(X) =4x1+2x2 -Mx6 =>max

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

План >Базис У >x1 >x2 >x3 >x4 >x5 >х6
0 >х3 4 1 -1 1 0 0 0
>x4 6 1 3 0 1 0 0
>х6 2 1 2 0 0 -1 1
>Індексний ряд >F(X0) 0 0 0 0 0 0 0

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

План >Базис У >x1 >x2 >x3 >x4 >x5 >x6 >min
1 >x3 4 1 -1 1 0 0 0 0
>x4 6 1 3 0 1 0 0 2
>x6 2 1 2 0 0 -1 1 1
>Індексний ряд >F(X1) 0 0 0 0 0 0 0 0

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

План >Базис У >x1 >x2 >x3 >x4 >x5 >x6 >min
2 >x3 5 1.5 0 1 0 -0.5 0.5 3.33
>х4 3 -0.5 0 0 1 1.5 -1.5 0
>x2 1 0.5 1 0 0 -0.5 0.5 2
>Індексний ряд >F(X2) 0 0 0 0 0 0 0 0

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

План  >Базис  У  >x1  >x2  >x3  >x4  >x5  >x6  >min
3  >x3 2 0 -3 1 0 1 -1 2
   >X4 4 0 1 0 1 1 -1 4
   >X1 2 1 2 0 0 -1 1 0
 >Індексний ряд  >F(X3) 0 0 0 0 0 0 0 0
План >Базис У >x1 >x2 >x3 >x4 >x5 >x6 >min
4 >х5 2 0 -3 1 0 1 -1 0
>X4 2 0 4 -1 1 0 0 0.5
>X1 4 1 -1 1 0 0 0 0
>Індексний ряд >F(X4) 0 0 0 0 0 0 0 0
План >Базис У >x1 >x2 >x3 >x4 >x5 >х6
5 >х5 3.5 0 0 0.25 0.75 1 -1
>х2 0.5 0 1 -0.25 0.25 0 0
>х1 4.5 1 0 0.75 0.25 0 0
>Індексний ряд >F(X5) 0 0 0 0 0 0 0

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

>x5 = 3.5

>x2 = 0.5

>x1 = 4.5

>F(X) = 4*4.5 + 2*0.5 = 19

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

>y1+y2+y34

->y1+3y2+2y32

>4y1+6y2+2y3 =>min

>y1 0

>y2 0

>y3 0

>Рішеннядвоїстоїзадачідаєоптимальнуоцінокресурсів.Використовуючиостаннюінтиграціюпрямоїзадачізнайдемо,оптимальний пландвоїстоїзадачі. Зтеоремидвоїстостіслідує, що Y =C*A-1.

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

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

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

>Тоді Y =C*A-1 =

>Запишемооптимальний пландвоїстоїзадачі:

>y1 = 2.5

>y2 = 1.5

>y3 = 0

>Z(Y) = 4*2.5+6*1.5+2*0 = 19


>Завдання 3

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

1 2 4 1 5 200
1 2 1 3 1 120
2 1 3 3 1 150
100 90 200 30 80

>Розв’язок

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

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

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

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


В1 В2 >В3 >В4 >В5 >Запаси
А1 1 2 4 1 5 200
А2 1 2 1 3 1 120
А3 2 1 3 3 1 150
А4 0 0 0 0 0 30
>Потреби 100 90 200 30 80

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

>лінійнийпрограмуванняматематичний модель

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

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

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

>min Z =1x11 +2x12 +4x13 +1x14 +>5x15 +1x21 +2x22 +1x23 +3x24 +>1x25 +>2x31 +1x32 +3x33 +3x34 +>1x35 +0x41+0x42 +0x43 +0x44+0x45.

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

>min Z =1x11 +2x12 +4x13 +1x14 +>5x15 +1x21 +2x22 +1x23 +3x24 +>1x25 +>2x31 +1x32 +3x33 +3x34 +>1x35 +0x41+0x42 +0x43 +0x44+0x45.

за умів:

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

>Ai >Bj >ui
>b1 = 100 >b2 = 90 >b3 = 200 >b4=30 >b5=80
>а1 = 200

1

100

2

90

4

[-] 10

1

[+]

5 >u1 = 0
А2 = 120 1 2

1

120

3 1 >u2 = -3
>а3 = 150 2 1

3

[+] 70

3

[-] 30

1

50

>u3 = -1
>а4 = 30 0 0 0 0

0

30

>u4 = -2
>vj >v1 =1 >v2 =2 >v3 =4 >v4 =4 >V5 =2

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

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

>Перевіримооптимальність опорного плану,складемо системурівнянь (длязаповненихклітинтаблиці) длявизначенняпотенціалів Першого опорного плану:

>Записана системарівняньєневизначеною, й один ізїїрозв’язківдістанемо,узявши,наприклад,u1 = 0.Тоді усііншіпотенціали однозначновизначаються ізцієїсистемирівнянь:u1 =0,u2 = -3,u3 = -1,u4=-2,v1 =1,v2 =2,v3 =4v4=4,v5=2.Цізначенняпотенціалів Першого опорного планузаписуємо утранспортнутаблицю.

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

>А1B4 :u1 +v4 = 0 + 4 = 4 > 1;

>А1B5 :u1 +v5 = 0 + 2 = 2 < 5;

>А2B1 :u2 +v1 = -3 + 1 = -2 < 1;

>А2B2 :u2 +v2 = -3 + 2 = -1 < 2;

>А2B4 :u2 +v4 = -3 + 4 = 1 < 3;

>А2B5 :u2 +v5 = -3 + 2 = -1 < 1;

>А3B1 :u3 +v1 = -1 + 1 = 0 < 2;

>А3B2 :u3 +v2 = -1 + 2 = 1 = 1;

>А4B1 :u4 +v1 = -2 + 1 = -1 < 0;

>А4B2 :u4 +v2 = -2 + 2 = 0 = 0;

>А4B3 :u4 +v3 = -2 + 4 = 2 > 0;

>А4B4 :u4 +v4 = -2 + 4 = 2 > 0.

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

>А1B4 :u1 +v4 = 0 + 4 = 4 > 1;

>А4B3 :u4 +v3 = -2 + 4 = 2 > 0;

>А4B4 :u4 +v4 = -2 + 4 = 2 > 0.

Тому відньогонеобхідно перейти до іншого плану,змінившиспіввідношеннязаповнених йпорожніхклітиноктаблиці.Вибираємомаксимальнуоцінкувільноїклітини (>А1B4): 1

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

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

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


>Ai >Bj >ui
>b1 = 100 >b2 = 90 >b3 = 200 >b4=30 >b5=80
>а1 = 200

1

100

2

[-] 90

4

1

[+] 10

5 >u1 = 0
А2 = 120 1 2

1

120

3 1 >u2 = 0
>а3 = 150 2

1

[+]

3

80

3

[-] 20

1

50

>u3 = 2
>а4 = 30 0 0 0 0

0

30

>u4 = 1
>vj >v1 =1 >v2 =2 >v3 =1 >v4 =1 >V5 =-1

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

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

(>А3B1): 2 + 1 = 3 > 2;

(>А3B2): 2 + 2 = 4 > 1;

(>А4B1): 1 + 1 = 2 > 0;

(>А4B2): 1 + 2 = 3 > 0;

(>А4B3): 1 + 1 = 2 > 0;

(>А4B4): 1 + 1 = 2 > 0.

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

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

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


>Ai >Bj >ui
>b1 = 100 >b2 = 90 >b3 = 200 >b4=30 >b5=80
>а1 = 200

1

100

2

70

4

1

30

5 >u1 = 0
А2 = 120 1 2

1

120

3 1 >u2 = -3
>а3 = 150 2

1

20

3

[-] 80

3

1

[+] 50

>u3 = -1
>а4 = 30 0 0

0

[+]

0

0

[-] 30

>u4 = -2
>vj >v1 =1 >v2 =2 >v3 =1 >v4 =1 >V5 =-1

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

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

(>А4B3): -2 + 4 = 2 > 0

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

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

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

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

>Ai >Bj >ui
>b1 = 100 >b2 = 90 >b3 = 200 >b4=30 >b5=80
>а1 = 200

1

100

2

70

4

1

30

5 >u1 = 0
А2 = 120 1 2

1

120

3 1 >u2 = -3
>а3 = 150 2

1

20

3

50

3

1

80

>u3 = -1
>а4 = 30 0 0

0

30

0 0 >u4 = -4
>vj >v1 =1 >v2 =2 >v3 =4 >v4 =1 >V5 =2

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

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

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

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

>Z(x) = 1*100 + 2*70 + 1*30 + 1*120 + 1*20 + 3*50 + 1*80 + 0*30 = 640

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


>Завдання 4

>Знайтиграфічним методомекстремумифункції вобласті,визначенійнерівностями (в всіхваріантахвважати )

, , ,

>Розв’язок

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

>Межіобласті


>Позначимограниціобластібагатокутникарішень.

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

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

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


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

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


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

Навігація