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


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

>Завдання 1

Длявиготовленнявиробів №1 й №2є 100 кгметалу. Навиготовленнявиробу №1витрачається 2 кгметалу, але ввиріб №2 – 4 кг.

>Скласти планвиробництва, щозабезпечуєодержаннянайбільшогоприбутку від продажвиробів,якщовідпускнавартість одноговиробу №1становить 3 грн. од., авиробу №2 – 2 грн. од.,причомувиробів №1потрібновиготовити не понад 40 штук, авиробів №2 – 20 прим.

>Сировина >Вироби >Кількістьсировини
В1 В2
Метал 2 4 100
>Вартість, грн. кг 3 2

>Розв’язок

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

=3х1+2х2.

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

CI =>2х1+4х2,

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

>2х1+4х2100

>Окрім того,виробів №1потрібновиготовити не понад 40 штук, авиробів №2 – 20 прим.,тобтоповиннівиконуватисьщенерівності:х140,х220.

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

>Знайтих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 0 0 50
>x4 40

1

0 0 1 0

40

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

-3

-2 0 0 0 0

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

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

4

1 -2 0

5

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

-2

0 3 0 0

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

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

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


 

>Завдання 2

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

>Розв’язок

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

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

>9x1+10x245

>5x1-x242

->x1+13x24

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

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

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

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

13

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

0

0 0 0 0 0

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

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

9,77

0 -1 0 -0,7692 1

4,29

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

0

0 0 0 0 0 0

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

План >Базис У >x1 >x2 >x3 >x4 >x5 >x6 >min
3 >х1 4,29 1 0 -0,1024 0 -0,0787 0,1024

0

>x4 21,18 0 0 0,5039 1 0,4646 -0,5039 45,59
>х2 0,6378 0 1 -0,0079 0

0,0709

0,0079

9

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

0

0 0 0

0

0 0

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

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

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

>x1 = 5

>x4 = 17

>x5 = 9

>F(X) = 1*5 = 5

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

>9y1+5y2-y31

>10y1-y2+13y33

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

[+]

0

u1 = 0

а2 = 300

2 3

1

[+]40

2

90

4

[-]70

0

100

u2 = -6

а3 = 150

2 1 3 1 4

0

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

0

u1 = 0

а2 = 300

2 3

1

100

2

90

4

[-]10

0

[+]100

u2 = 3

а3 = 150

2

1

[+]

3 1 4

0

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

0

[+]

u1 = 0

а2 = 300

2 3

1

100

2

90

4

0

110

u2 = -3

а3 = 150

2

1

[+]10

3 1 4

0

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

0

70

u1 = 0

а2 = 300

2 3

1

100

2

[-]90

4

0

[+]110

u2 = 0

а3 = 150

2

1

80

3

1

[+]

4

0

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

0

70

u1 = 0

а2 = 300

2 3

1

100

2

20

4

0

180

u2 = 0

а3 = 150

2

1

80

3

1

70

4 0

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+2x22 (1)

>2x1+2x210 (2)

>x1+x2=6 (3)

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

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

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

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

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

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


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


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

Навігація