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

Страница 1 из 2 | Следующая страница

>Завдання 1

>Зібранийврожай зернатрьохсільськогосподарськихартілей винен бутиперевезений втричіелеватори, асаме:елеватор А1потужністю 100 тис. тонн,елеватор А2 – 80 тис. тонн; А3 – 90 тис. тонн.Визначити планперевезення зерна наелеватори,якиймінімізуєтранспортнівитрати.

>С/гартіль >Затрати наперевезення 1 т зерна наелеватори, грн.

Запас зерна,

тис. т

В1 В2 >В3

А1

12,5 24,0 18,4 80

А2

28,3 14,5 25,7 90

А3

15,7 20,6 16,3 100
>Потужністьелеваторів 100 80 90

>Розв’язок

 

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

>Перевіримонеобхідність йдостатність уміврозв'язаннязадачі:

Ос-кільки , тоумова балансудотримується.Запасирівніпотребам. Отже, модельтранспортноїзадачієзакритою.

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

У1

У2

У3

>Запаси

А1

12,5 24,0 18,4 80

А2

28,3 14,5 25,7 90

А3

15,7 20,6 16,3 100
>Потреби 100 80 90

>Розпочинаємо будуватиматематичну модельданоїзадачі:

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

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

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

>minZ=12,5x11+24x12+18,4x13+28,3x21+14,5x22+25,7x23+15,7x31+20,6x32+16,3x33.

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

>minZ=12,5x11+24x12+18,4x13+28,3x21+14,5x22+25,7x23+15,7x31+20,6x32+16,3x33.

за умів:

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


Aі

Bj

uі

b1 = 100

b2 = 80

b3 = 90

а1 = 80

12,5

80

24,0 18,4

u1 = 0

а2 = 90

28,3

[-]20

14,5

[+]70

25,7

u2 = 15,8

а3 = 100

15,7

[+]

20,6

[-]20

16,3

80

u3 = 21,9

vj

v1 =12,5

v2 =-1,3

v3 =-5,6

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

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

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

u1=0, u2=15,8, u3=21,9, v1=12,5, v2=-1,3, v3=-5,6.Цізначенняпотенціалів Першого опорного планузаписуємо утранспортнутаблицю.

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

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

(3;1): 21.9 + 12.5 > 15.7; ∆31 = 21.9 + 12.5 - 15.7 = 18.7

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

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

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

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

Aі

Bj

uі

b1 = 100

b2 = 80

b3 = 90

а1 = 80

12,5

80

24,0 18,4

u1 = 0

а2 = 90

28,3

[-] 0

14,5

90

25,7

[+]

u2 = 15,8

а3 = 100

15,7

[+] 20

20,6

16,3

[-]80

u3 = 3,2

vj

v1 =12,5

v2 =-1,3

v3 =13,1

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

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

(2;3): 15.8 + 13.1 > 25.7; ∆23 = 15.8 + 13.1 - 25.7 = 3.2

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

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

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


Aі

Bj

uі

b1 = 100

b2 = 80

b3 = 90

а1 = 80

12,5

80

24,0 18,4

u1 = 0

а2 = 90

28,3

14,5

90

25,7

0

u2 = 12,6

а3 = 100

15,7

20

20,6

16,3

80

u3 = 3,2

vj

v1 =12,5

v2 =1,9

v3 =13,1

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

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

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

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

>F(x) = 12.5*80 + 14.5*90 + 15.7*20 + 16.3*80 = 3923

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

 

>Завдання 2

>математична модельекстремумтранспортна завдання

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


>Розв’язок

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

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

->2x1+>6x2≤2

>4x1->3x2≤12

x1-x2≥3

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

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

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

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

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

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

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

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

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

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

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

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

Зрівняньвисловлюємоштучнізмінні:

x6 =3-x1+x2+x5

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

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

чи

>F(X) = (>3+1M)x1+(>1-1M)x2+(->1M)x5+(->3M) =>>max

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

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

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

x3, x4, x6,

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

>X1 = (0,0,2,12,0,3)

 План  >Базис  У

 x1

 x2

 x3

 x4

 x5

 x6

 0

 x3

 2  -2  6  1  0  0  0

 x4

 12  4  -3  0  1  0  0

 x6

 3  1  -1  0  0  -1  1
 >Індексний ряд  >F(X0)  ->3M  ->3-1M  ->1+1M  0  0  >1M  0

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

План  >Базис  У

 x1

 x2

 x3

 x4

 x5

 x6

>min
 1

 x3

 2  -2  6  1  0  0  0  0

 x4

 12

4

 -3  0  1  0  0

3

 x6

 3  1  -1  0  0  -1  1  3
 >Індексна ряд  >F(X1)  ->3M

->3-1M

 ->1+1M  0  0  >1M  0  0

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


План  >Базис  У

 x1

 x2

 x3

 x4

 x5

 x6

 2

 x3

 8  0  4.5  1  0.5  0  0

 x1

 3  1  -0.75  0  0.25  0  0

 x6

 0  0  -0.25  0  -0.25  -1  1
>Індексна ряд  >F(X2)  9  0  ->3.25+0.25M  0  >0.75+0.25M  >1M  0

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

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

x3 = 8

x1 = 3

x6 = 0

>F(X) = 3*3 = 9

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

->2y1+>4y2+y3≥3

>6y1->3y2-y3≥1

>2y1+>12y2+>3y3 =>>min

y1 ≥ 0

y2 ≥ 0

y3 ≤ 0

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

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

Зпершоїтеоремидвоїстостівипливає, що Y =C*A-1.

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

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

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

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

>Оптимальний пландвоїстоїзадачідорівнює:

y1 = 0

y2 = 0.75

y3 = 0

>Z(Y) = 2*0+12*0.75+3*0 = 9

 

>Завдання 3

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

1 4 7 9 1 250
2 3 1 2 4 300
2 1 3 1 4 150
110 80 100 90 70

 

>Розв’язок

>Побудоваматематичноїмоделі.Нехай x>ij —кількістьпродукції, що перевозитися із й-го пунктувиробництва до 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.

за умів:

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

Aі

Bj

uі

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. Отже,опорний планє невиродженим.

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

u1 + v1 = 1; 0 + v1 = 1; v1 = 1

u1 + v2 = 4; 0 + v2 = 4; v2 = 4

u1 + v3 = 7; 0 + v3 = 7; v3 = 7

u2 + v3 = 1; 7 + u2 = 1; u2 = -6

u2 + v4 = 2; -6 + v4 = 2; v4 = 8

u2 + v5 = 4; -6 + v5 = 4; v5 = 10

u2 + v6 = 0; -6 + v6 = 0; v6 = 6

u3 + v6 = 0; 6 + u3 = 0; u3 = -6

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

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

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

(1;5): 0 + 10 > 1; ∆15 = 0 + 10 - 1 = 9

(1;6): 0 + 6 > 0; ∆16 = 0 + 6 - 0 = 6

(3;4): -6 + 8 > 1; ∆34 = -6 + 8 - 1 = 1

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

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

Для цого упорожнюклітинку (1;5) переноситься менше із чисел x>ij, котрірозміщені вклітинкахзі знаком «–».Одночасноцесаме число x>ij >додаємо довідповідних чисел, щорозміщені вклітинкахзі знаком «+», тавіднімаємо від чисел, щорозміщені вклітинках,позначених знаком «–».

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

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

Aі

Bj

uі

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

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

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

(2;1): 3 + 1 > 2; ∆21 = 3 + 1 - 2 = 2

(2;2): 3 + 4 > 3; ∆22 = 3 + 4 - 3 = 4

(3;1): 3 + 1 > 2; ∆31 = 3 + 1 - 2 = 2

(3;2): 3 + 4 > 1; ∆32 = 3 + 4 - 1 = 6

(3;4): 3 + -1 > 1; ∆34 = 3 + -1 - 1 = 1

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

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

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

Aі

Bj

uі

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

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

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

(1;6): 0 + 3 > 0; ∆16 = 0 + 3 - 0 = 3

(3;4): -3 + 5 > 1; ∆34 = -3 + 5 - 1 = 1

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

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

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

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

Aі

Bj

uі

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

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

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

(3;4): 0 + 2 > 1; ∆34 = 0 + 2 - 1 = 1

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

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

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

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

 

Aі

Bj

uі

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

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

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

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

>Мінімальнівитратискладуть:

>F(x) = 1*110 + 1*70 + 0*70 + 1*100 + 2*20 + 0*180 + 1*80 + 1*70

Страница 1 из 2 | Следующая страница

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

Навігація