Реферати українською » Экономико-математическое моделирование » Математічні Моделі задач лінійного програмування


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

>Завдання 1

Цехвипускає вали й чопи. Навиробництво одного валуробочийвитрачає 3 рік.,однієї чопи – 2 рік.Відреалізації одного валупідприємствоодержуєприбуток 80 грн., а відреалізаціїоднієї чопи – 60 грн. Цехмаєвипустити не менше 100валів й не менше 200 втулок.Скількивалів й стільки втулокмаєвипустити цех,щободержатинайбільшийприбуток,якщо фондробочого годиниробітниківстановить 900людино-годин?

Ресурс >Вироби Фондробочого години
Валі >Втулки
>Робітник, рік. од. 3 2 900
>Вартість, грн. од. 80 60

>Розв’язок

>Складаємоматематичну модельзадачі.Позначимо черезх1кількістьвалів, щовиготовляєпідприємство задеяким планом, а ще черезх2кількість втулок.Тодіприбуток,отриманийпідприємством відреалізаціїцихвиробів,складає

=80х1+60х2.

>Витратиресурсів навиготовленнятакоїкількостівиробівскладаютьвідповідно:

CI =>3х1+2х2,

Ос-кількизапасиресурсівобмежені, топовиннівиконуватисьнерівності:


>3х1+2х2900

>Окрім того,валівпотрібновиготовити не менше 100 штук, а втулок – 200 прим.,тобтоповиннівиконуватисьщенерівності:х1 100,х2 200.

Таким чином,приходимо доматематичноїмоделі:

>Знайтих1,х2такі, щофункція =80х1+60х2досягає максимуму присистеміобмежень:

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

Дляпобудови Першого опорного плану системунерівностейприведемо досистемирівнянь шляхомвведеннядодатковихзмінних. Ос-кільки маємозмішаніумови-обмеження, товведемоштучнізмінні x.

>3x1 +2x2 +1x3 +0x4 +0x5 +0x6 +0x7 = 900

>1x1 +0x2 +0x3-1x4 +0x5 +1x6 +0x7 = 100

>0x1 +1x2 +0x3 +0x4-1x5 +0x6 +1x7 = 200

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

>F(X) = 80x1 +60x2 - Mx6 - Mx7 =>max

>Отриманий базисназиваєтьсяштучним, а методрішенняназивається методом штучного базису.

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

Зметоюформулюваннязадачі длявирішенняїї втабличнійформіскористаємосявиразами ізсистемирівнянь дляштучнихзмінних:

>x6 =100-x1 +>x4

>x7 =200-x2 +>x5

котріпідставимо вцільовуфункцію:

>F(X) =80x1 +60x2 -M(100-x1 +>x4 ) -M(200-x2 +>x5 ) =>max

чи

>F(X) = (>80+1M)x1 +(>60+1M)x2 +(->1M)x4 +(->1M)x5 +(->300M) =>max

>Матрицякоефіцієнтів A =a(ij)цієїсистемирівняньмаєвигляд:

3 2 1 0 0 0 0
1 0 0 -1 0 1 0
0 1 0 0 -1 0 1

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

>Вирішимо системурівняньвідноснобазиснихзмінних:

>x3 ,x6 ,x7

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

>X1 = (0,0,900,0,0,100,200)

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

>Складаємосимплекс-таблицю:

План >Базис У >x1 >x2 >x3 >x4 >x5 >x6 >x7 >min
1 >x3 900 3 2 1 0 0 0 0 300
>x6 100 1 0 0 -1 0 1 0 100
>x7 200 0 1 0 0 -1 0 1 0
>Індексний ряд >F(X1) -30000000 -100080 0 -100060 0 100000 0 0 0

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

План >Базис У >x1 >x2 >x3 >x4 >x5 >x6 >x7 >min
2 >x3 600 0 2 2 0 3 -3 0 300
>x1 100 1 0 0 0 -1 1 0 0
>x7 200 0 1 1 0 0 0 1 200
>Індексний ряд >F(X2) -19992000 0 0 -100060 0 -80 100080 0 0

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

План >Базис У >x1 >x2 >x3 >x4 >x5 >x6 >x7 >min
3 >x3 200 0 0 1 3 2 -3 -2 66,67
>x1 100 1 0 0 -1 0 1 0 0
>x2 200 0 1 0 0 -1 0 1 0
>Індексний ряд >F(X3) 20000 0 0 0 -80 -60 100080 100060 0

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

План >Базис У >x1 >x2 >x3 >x4 >x5 >x6 >x7 >min
4 >x4 66,67 0 0 0,33 1 0,67 -1 -0,67 100
>x1 166,67 1 0 0,33 0 0,67 0 -0,67 250
>x2 200 0 1 0 0 -1 0 1 0
>Індексний ряд >F(X4) 25333,33 0 0 26,67 0 -6,67 100000 100006,67 0

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

План >Базис У >x1 >x2 >x3 >x4 >x5 >x6 >x7 >min
5 >x5 100 0 0 0,5 1,5 1 -1,5 -1 100
>x1 100 1 0 0 -1 0 1 0 250
>x2 300 0 1 0,5 1,5 0 -1,5 0 0
>Індексний ряд >F(X5) 26000 0 0 30 10 0 99990 100000 0

Ос-кільки усіоцінки >0, тознайденооптимальний план, щозабезпечуємаксимальнийприбуток:х1=100,х2=300.Прибуток, привипускупродукції зацим планом,становить 26000 грн.


>Завдання 2

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

>Розв’язок

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

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

>x1+2x26

->5x1+4x22

>7x1+5x235

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

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

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

>7x1 +5x2 +0x3 +0x4-1x5 = 35

>Введемоштучнізмінні x.


>1x1 +2x2 +1x3 +0x4 +0x5 +0x6 = 6

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

>7x1 +5x2 +0x3 +0x4-1x5 +1x6 = 35

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

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

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

>X1 = (0,0,6,2,0,35)

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

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

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

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

План >Базис У >x1 >x2 >x3 >x4 >x5 >x6 >min
2 >х3 1 0 1,29 1 0 0,1429 -0,1429 7
>x4 27 0 7,57 0 1 -0,7143 0,7143 0
>х1 5 1 0,7143 0 0 -0,1429 0,1429 0
>Індексний ряд >F(X2) 0 0 0 0 0 0 0 0

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

План >Базис У >x1 >x2 >x3 >x4 >x5 >x6
3 >х5 7 0 9 7 0 1 -1
>x4 32 0 14 5 1 0 0
>х1 6 1 2 1 0 0 0
>Індексний ряд >F(X3) 0 0 0 0 0 0 0

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

>x5 = 7

>x4 = 32

>x1 = 6

>F(X) = 3*6 = 18

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

>y1+5y2+7y33

>2y1-4y2+5y31

>6y1-2y2+35y3 =>min

>y1 0

>y2 0

>y3 0

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

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

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

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

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

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

>y1 = 3

>y2 = 0

>y3 = 0

>Z(Y) = 6*3+-2*0+35*0 = 18


>Завдання 3

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

2 4 5 8 6 180
7 3 6 4 5 300
8 5 6 5 3 230
110 140 220 190 120

>Розв’язок

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

У нашомувипадкуробитьсяцевведеннямфіктивногопостачальника,оскільки

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

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

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

В1 В2 >В3 >В4 >В5 >Запаси
А1 2 4 5 8 6 180
А2 7 3 6 4 5 300
А3 8 5 6 5 3 230
А4 0 0 0 0 0 70
>Потреби 110 140 220 190 120

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

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

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

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

>minZ=2x11+4x12+5x13+86x14+6x15+7x21+3x22+6x23+4x24+5x25+8x31+5x32+6x33+5x34+ +>3x35+0x41+0x42+0x43+0x44+0x45.

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

>minZ=2x11+4x12+5x13+86x14+6x15+7x21+3x22+6x23+4x24+5x25+8x31+5x32+6x33+5x34+ +>3x35+0x41+0x42+0x43+0x44+0x45.

за умів:

 

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

>Ai >Bj >ui
>b1 = 110 >b2 = 140 >b3 = 220 >b4=190 >b5=120
>а1 = 180

2

110

4

70

5 8 6 >u1 = 0
А2 = 300 7

3

70

6

[-] 220

4

[+] 10

5 >u2 = -1
>а3 = 230 8 5 6

5

[-] 180

3

[+] 50

>u3 = 0
>а4 = 70 0 0

0

[+]

0

0

[-] 70

>u4 = -3
>vj >v1 = 2 >v2 = 4 >v3 = 7 >v4 = 5 >v5 = 3

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

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

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

>u1=0,u2=-1,u3=0,u4=-3,v1=2,v2=4,v3=7v4=5,v5=3

>Цізначенняпотенціалів Першого опорного планузаписуємо утранспортнутаблицю.

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

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

(1;3): 0 + 7 > 5

(3;3): 0 + 7 > 6

(4;2): -3 + 4 > 0

(4;3): -3 + 7 > 0

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

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

>Тепернеобхіднопереміститипродукцію вмежахпобудованого циклу.

Звантажівхij що стояти вмінусовихклітинах,вибираємонайменше,тобто у =min (4;5) = 70.

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

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

>Одночасноцесаме числохijдодаємо довідповідних чисел, щорозміщені вклітинкахзі знаком «+», тавіднімаємо від чисел, щорозміщені вклітинках,позначених знаком «–».

>Усііншізаповненіклітинкипершоїтаблиці, котрі не входили до циклу,переписуємо у другутаблицю беззмін.

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

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

>Ai >Bj >ui
>b1 = 110 >b2 = 140 >b3 = 220 >b4=190 >b5=120
>а1 = 180

2

110

4

[-] 70

5

[+]

8 6 >u1 = 0
А2 = 300 7

3

[+] 70

6

[-] 150

4

80

5 >u2 = -1
>а3 = 230 8 5 6

5

110

3

120

>u3 = 0
>а4 = 70 0 0

0

70

0 0 >u4 = -7
>vj >v1 = 2 >v2 = 4 >v3 = 7 >v4 = 5 >v5 = 3

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

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

(1;3): 0 + 7 > 5

(3;3): 0 + 7 > 6

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

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

Цикл наведено втаблиці.

Звантажівхij що стояти вмінусовихклітинах,вибираємонайменше,тобто у =min (>А1B2) = 70.

>Додаємо 70 дообсягіввантажів, що стояти вплюсовихклітинах йвіднімаємо 70 ізХij, що стояти вмінусовихклітинах.

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

>Ai >Bj >ui
>b1 = 110 >b2 = 140 >b3 = 220 >b4=190 >b5=120
>а1 = 180

2

110

4

5

70

8 6 >u1 = 0
А2 = 300 7

3

140

6

[-] 80

4

[+] 80

5 >u2 = 1
>а3 = 230 8 5

6

[+]

5

[-] 110

3

120

>u3 = 2
>а4 = 70 0 0

0

70

0 0 >u4 = -5
>vj >v1 = 2 >v2 = 2 >v3 = 5 >v4 = 3 >v5 = 1

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

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

(3;3): 2 + 5 > 6

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

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

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

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

>Ai >Bj >ui
>b1 = 110 >b2 = 140 >b3 = 220 >b4=190 >b5=120
>а1 = 180

2

110

4

5

70

8 6 >u1 = 0
А2 = 300 7

3

140

6

4

160

5 >u2 = 0
>а3 = 230 8 5

6

80

5

30

3

120

>u3 = 1
>а4 = 70 0 0

0

70

0 0 >u4 = -5
>vj >v1 = 2 >v2 = 3 >v3 = 5 >v4 = 4 >v5 = 2

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

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

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

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

>F(x) = 2*110 + 5*70 + 3*140 + 4*160 + 6*80 + 5*30 + 3*120 + 0*70 = 2620

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

>Завдання 4

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

 

 

.

>Розв’язок

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

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


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

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

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


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

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

ПрямаF(x) =constперетинає область уточці A. Ос-кільки точка Aотримана врезультатіперетинупрямих 1 і 5, тоїїкоординатизадовольняютьрівняннямцихпрямих:

>x1+x21

>x1=0

>Вирішивши системурівнянь, одержимо

>x1 = 0,x2 = 1

>Звідкизнайдемомінімальнезначенняцільовоїфункції

>F(X) = 9*0 + 8*1 = 8


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

Навігація