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

>Завдання 1

>Побудуватиматематичну модельзадачі.

Напідприємствівиготовляютьсявироби двохвидів А й У. Для цоговикористовуєтьсясировиначотирьохтипів – І, ІІ, ІІІ,ІV,запасиякоїдорівнюють,відповідно, 21; 4; 6; 10 од. Длявиготовлення одноговиробу Анеобхідна такакількістьодиницьсировиничотирьохвидів: 2; 1; 0; 2. Длявиробу У – 3; 0; 1; 1 од.відповідно.Випуск одноговиробу Адає 3 грн. од.прибутку, типу У – 2 грн. од.Скласти планвиробництва,якийзабезпечуєнайбільшийприбуток.

>Сировина Нормавитратсировини, од >Запасисировини, од.
А У
І 2 3 21
ІІ 1 0 4
ІІІ 0 1 6
>ІV 2 1 10
>Ціна, грн. од. 3 2

>Розв’язок

 

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

=3х1+>2х2.

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

ЗI =>2х1 +3х2,

ЗII =>1х1 +0х2,

ЗIII =>0х1 +1х2,

ЗIV =>2х1 +1х2,

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

>2х1 +3х2≤ 21

>1х1≤ 4

>1х2≤ 6

>2х1 +1х2≤ 10

Ос-кільки,кількістьвиробівє величинаневід'ємна, тододатковоповиннівиконуватисьщенерівності: x1> 0, x2>0.

Таким чином,приходимо доматематичноїмоделі (>задачілінійногопрограмування):

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

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

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

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

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

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

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

де x1,...,x6>0

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

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

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

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

План >Базис У

x1

x2

x3

x4

x5

x6

>min
1

x3

21 2 3 1 0 0 0 10.5

x6

4

1

0 0 0 0 1

4

x4

6 0 1 0 1 0 0 0

x5

10 2 1 0 0 1 0 5
>Індексний ряд >F(X1) -400000

-100003

-2 0 0 0 0 0

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

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

План >Базис У

x1

x2

x3

x4

x5

x6

>min
2

x3

13 0 3 1 0 0 -2 4.33

x1

4 1 0 0 0 0 1 0

x4

6 0 1 0 1 0 0 6

x5

2 0

1

0 0 1 -2

2

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

-2

0 0 0 100003 0

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

План  >Базис  У

 x1

 x2

 x3

 x4

 x5

 x6

>Min
 3

 x3

 7  0  0  1  0  -3  4  4.33

 x1

 4  1  0  0  0  0  1  0

 x4

 4  0  0  0  1  -1  2  6

 x2

 2  0  1  0  0  1  -2  2
>Індексний ряд >F(X3)  16  0  0  0  0  2 99999  0

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

 

>Завдання 2

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

>Розв’язок

 

Пряма завданнялінійногопрограмуваннямаєвигляд:

Приобмеженнях:

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

Длядосягненнявідповідноговиглядупомножимо1-у та2-унерівність на -1

>1х1->4ч2≥-8

->1х1+>1х2≥-3

Урезультатіотримаємонаступніматриці:

Дляскладаннядвоїстоїзадачілінійногопрограмуваннязнайдемоматриці А, У, ЗТ.

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

>F(Y)= ->8Y1->3Y2+>9Y3 (>max)

>Обмеження:

>1Y1->1Y2+>2Y3≤2

->4Y1+>1Y2+>1Y3≤1

Y1≥0

Y2≥0

Y3≥0

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

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

-x1+>4x2≤8

x1-x2≤3

>2x1+x2≥9

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

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

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

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

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

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

>F(X) = 2 x1 + x2 +M x6 =>>min

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

План >Базис У

x1

x2

x3

x4

x5

x6

>Min
1

x3

8 -1 4 1 0 0 0 0

x4

3

1

-1 0 1 0 0

3

x6

9 2 1 0 0 -1 1 4.5
>Індексний ряд >F(X1) 900000

199998

99999 0 0 -100000 0 0

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

План >Базис У

x1

x2

x3

x4

x5

x6

>min
2

x3

11 0 3 1 1 0 0 3.67

x1

3 1 -1 0 1 0 0 0

x6

3 0

3

0 -2 -1 1

1

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

299997

0 -199998 -100000 0 0

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

План  >Базис  У

 x1

 x2

 x3

 x4

 x5

 x6

>min
 3

 x3

 8  0  0  1  3  1  -1  3.67

 x1

 4  1  0  0  0.33  -0.33  0.33  0

 x2

 1  0  1  0  -0.67  -0.33  0.33  1
 >Індексний ряд  >F(X3)  9  0  0  0  0  -1  -99999  0

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

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

x3 = 8

x1 = 4

x2 = 1

>F(X) = 2*4 + 1*1 = 9

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

>F(Y)= ->8Y1->3Y2+>9Y3 (>max)

>Обмеження:

>1Y1->1Y2+>2Y3≤2

->4Y1+>1Y2+>1Y3≤1

Y1≥0

Y2≥0

Y3≥0

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

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

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

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

План >Базис У

x1

x2

x3

x4

x5

0

x4

2 1 -1 2 1 0

x5

1 -4 1 1 0 1
>Індексний ряд >F(X0) 0 8 3 -9 0 0

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


План >Базис У

x1

x2

x3

x4

x5

>min
1

x4

2 1 -1

2

1 0

1

x5

1 -4 1 1 0 1 1
>Індексний ряд >F(X1) 0 8 3

-9

0 0 0
План >Базис У

x1

x2

x3

x4

x5

>min
2

x3

1 0.5 -0.5 1 0.5 0 0

x5

0 -4.5

1.5

0 -0.5 1

0

>Индекснаястрока >F(X2) 9 12.5

-1.5

0 4.5 0 0
План >Базис У

x1

x2

x3

x4

x5

3

x3

1 -1 0 1 0.3333 0.3333

x2

0 -3 1 0 -0.3333 0.6667
>Индекснаястрока >F(X3) 9 8 0 0 4 1

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

x3 = 1

x2 = 0

>F(X) = -3*0 + 9*1 = 9

>Завдання 3

 

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

5 1 2 3 4 150
7 8 1 1 2 320
4 1 3 1 2 400
100 120 100 200 300

 

>Розв’язок

 

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

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

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

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

У1

У2

У3

У4

У5

У6

>Запаси

А1

5 1 2 3 4 0 150

А2

7 8 1 1 2 0 320

А3

4 1 3 1 2 0 400
>Потреби 100 120 100 200 300 50

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

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

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

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

>minZ = 5x11 + 1x12 + 2x13 + 3x14 +4x15 + 0x16 +7x21 + 8x22 + 1x23 + 1x24 +2x25+0x26+4x31 + 1x32 + 3x33 + 1x34 +2x35 + 0x36.

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

>minZ = 5x11 + 1x12 + 2x13 + 3x14 +4x15 + 0x16 +7x21 + 8x22 + 1x23 + 1x24 +2x25+0x26+4x31 + 1x32 + 3x33 + 1x34 +2x35 + 0x36.

за умів:

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


Aі

Bj

uі

b1 = 100

b2 = 120

b3 = 100

b4=200

b5=300

B6=50

а1 = 150

5

[-] 100

1

[+] 50

2 3 4 0

u1 = 0

а2 = 320

7

8

[-] 70

1

100

1

[+] 150

2 0

u2 = 7

а3 = 400

4

[+]

1 3

1

[-] 50

2

300

0

50

u3 = 7

vj

v1 = 5

v2 = 1

v3 = -6

v4 = -6

v5= -5

V6 = -7

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

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

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

>Тоді усііншіпотенціали однозначновизначаються ізцієїсистемирівнянь: u1 =0, u2 = 7, u3 = 7, v1 =5, v2 =1, v3 = -6 v4=1, v5= -5, v6= -7.Цізначенняпотенціалів Першого опорного планузаписуємо утранспортнутаблицю.

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

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

(2;1): 7 + 5 > 7

(3;1): 7 + 5 > 4

(3;2): 7 + 1 > 1

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

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

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

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

Aі

Bj

uі

b1 = 100

b2 = 120

b3 = 100

b4=200

b5=300

B6=50

а1 = 150

5

[-] 50

1

[+] 100

2 3 4 0

u1 = 0

а2 = 320

7

8

[-] 20

1

100

1

200

2

[+]

0

u2 = 7

а3 = 400

4

[+] 50

1 3 1

2

[-] 300

0

50

u3 = -1

vj

v1 = 5

v2 = 1

v3 = -6

v4 = -6

v5= 3

V6 = 1

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

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

(1;6): 0 + 1 > 0

(2;1): 7 + 5 > 7

(2;5): 7 + 3 > 2

(2;6): 7 + 1 > 0

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

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

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

Aі

Bj

uі

b1 = 100

b2 = 120

b3 = 100

b4=200

b5=300

B6=50

а1 = 150

5

[-] 30

1

120

2 3 4

0

[+]

u1 = 0

а2 = 320

7 8

1

100

1

200

2

20

0

u2 = -1

а3 = 400

4

[+] 70

1 3 1

2

280

0

[-] 50

u3 = -1

vj

v1 = 5

v2 = 1

v3 = 2

v4 = 2

v5= 3

V6 = 1

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

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

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


Aі

Bj

uі

b1 = 100

b2 = 120

b3 = 100

b4=200

b5=300

B6=50

а1 = 150

5

1

120

2 3 4

0

30

u1 = 0

а2 = 320

7 8

1

100

1

200

2

20

0

u2 = 0

а3 = 400

4

100

1 3 1

2

280

0

20

u3 = 0

vj

v1 = 4

v2 = 1

v3 = 1

v4 = 1

v5= 2

V6 = 0

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

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

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

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

(x) = 1*120 + 0*30 + 1*100 + 1*200 + 2*20 + 4*100 + 2*280 + 0*20 = 1420

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

>Завдання 4

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

,  ,      ,    


>Розв’язок

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

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

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

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

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

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

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

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

>x1+2x22

>x1=0

>Вирішивши системурівнянь, одержимо:x1 = 0,x2 = 1

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

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


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

Навігація