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

>Завдання 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

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

 

>Розв’язок

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

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

>2x1+>4x2≥10

>3x1+>2x2≥11

>4x1+>7x2≤32

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

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

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

>4x1 +7x2 +0x3 +0x4 +1x5 = 32

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

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

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

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

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

>F(X) =3x1+>2x2+>Mx6+>Mx7 =>min

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

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

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

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

x6 =10-2x1->4x2+x3

x7 =11-3x1->2x2+x4

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

>F(X) =3x1 +2x2 +M(10-2x1->4x2+x3) +M(11-3x1->2x2+x4) =>min

чи

>F(X) = (>3-5M)x1+(>2-6M)x2+(>1M)x3+(>1M)x4+(>21M) =>min

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

 2 4 -1 0 0 1 0
3 2 0 -1 0 0 1
4 7 0 0 1 0 0

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

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

x6, x7, x5,

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

>X1 = (0,0,0,0,32,10,11)

План >Базис У

x1

x2

x3

x4

x5

x6

x7

0

x6

10 2 4 -1 0 0 1 0

x7

11 3 2 0 -1 0 0 1

x5

32 4 7 0 0 1 0 0

>Індексний

ряд

>F(X0) >21M ->3+5M ->2+6M ->1M ->1M 0 0 0

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

План >Базис У

x1

x2

x3

x4

x5

x6

x7

>min
1

x6

10 2

4

-1 0 0 1 0

2.5

x7

11 3 2 0 -1 0 0 1 5.5

x5

32 4 7 0 0 1 0 0 4.57

>Індексний

ряд

>F(X1) >21M ->3+5M

->2+6M

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

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

План >Базис У

x1

x2

x3

x4

x5

x6

x7

>min
2

x2

2.5 0.5 1 -0.25 0 0 0.25 0 5

x7

6

2

0 0.5 -1 0 -0.5 1

3

x5

14.5 0.5 0 1.75 0 1 -1.75 0 29

>Індексний

ряд

>F(X2) >5+6M

->2+2M

0 ->0.5+0.5M ->1M 0 >0.5-1.5M 0 0

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



План

>Базис У

x1

x2

x3

x4

x5

x6

x7

3

x2

1 0 1 -0.375 0.25 0 0.375 -0.25

x1

3 1 0 0.25 -0.5 0 -0.25 0.5

x5

13 0 0 1.63 0.25 1 -1.63 -0.25

>Індексний

ряд

>F(X3) 11 0 0 0 -1 0 ->1M >1-1M

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

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

x2 = 1

x1 = 3

x5 = 13

>F(X) = 3*3 + 2*1 = 11

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

>2y1+>3y2+>4y3≤3

>4y1+>2y2+>7y3≤2

>10y1+>11y2+>32y3 =>max

y1 ≥ 0

y2 ≥ 0

y3 ≤ 0

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

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

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

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

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

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

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

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

y1 = 0

y2 = 1

y3 = 0

>Z(Y) = 10*0+11*1+32*0 = 11

>Завдання 3

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

1 4 2 1 2 300
2 2 3 1 3 90
3 4 5 6 7 70
100 20 70 90 180

>Розв’язок

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

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

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

У1

У2

У3

У4

У5

>Запаси

А1

1 4 2 1 2 300

А2

2 2 3 1 3 90

А3

3 4 5 6 7 70
>Потреби 100 20 70 90 180

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

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

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

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

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

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

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

за умів:

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

Aі

Bj

uі

b1 = 100

b2 = 20

b3 = 70

b4=90

b5=180

а1 = 300

1

100

4

[-]20

2

70

1

90

2

[+]20

u1 = 0

а2 = 90

2 2 3 1

3

90

u2 = 1

а3 = 70

3

4

[+]

5 6

7

[-]70

u3 = 5

vj

v1 =1

v2 =4

v3 =2

v4 =1

v5 =2

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

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

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

u1=0, u2=1, u3=5, v1=1, v2=4, v3=2 v4=1, v5=2.Цізначенняпотенціалів Першого опорного планузаписуємо утранспортнутаблицю.

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

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

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

(2;4): 1 + 1 > 1; ∆24 = 1 + 1 - 1 = 1

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

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

(3;3): 5 + 2 > 5; ∆33 = 5 + 2 - 5 = 2

>max(3,1,3,5,2) = 5

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

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

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

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


Aі

Bj

uі

b1 = 100

b2 = 20

b3 = 70

b4=90

b5=180

а1 = 300

1

[-]100

4

2

70

1

90

2

[+] 40

u1 = 0

а2 = 90

2 2 3 1

3

90

u2 = 1

а3 = 70

3

[+]

4

20

5 6

7

[-] 50

u3 = 5

vj

v1 =1

v2 =-1

v3 =2

v4 =1

v5 =2

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

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

(2;4): 1 + 1 > 1; ∆24 = 1 + 1 - 1 = 1

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

(3;3): 5 + 2 > 5; ∆33 = 5 + 2 - 5 = 2

>max(1,3,2) = 3

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

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

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

Aі

Bj

uі

b1 = 100

b2 = 20

b3 = 70

b4=90

b5=180

а1 = 300

1

[-] 50

4

2

70

1

90

2

[+] 90

u1 = 0

а2 = 90

2

2

[+]

3 1

3

[-]90

u2 = 1

а3 = 70

3

[+] 50

4

[-] 20

5 6 7

u3 = 2

vj

v1 =1

v2 =2

v3 =2

v4 =1

v5 =2

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

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

(2;2): 1 + 2 > 2; ∆22 = 1 + 2 - 2 = 1

(2;4): 1 + 1 > 1; ∆24 = 1 + 1 - 1 = 1

>max(1,1) = 1

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

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

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

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

Aі

Bj

uі

b1 = 100

b2 = 20

b3 = 70

b4=90

b5=180

а1 = 300

1

30

4

2

70

1

[-]90

2

[+] 110

u1 = 0

а2 = 90

2

2

20

3

1

[+]

3

[-] 70

u2 = 1

а3 = 70

3

70

4 5 6 7

u3 = 2

vj

v1 =1

v2 =1

v3 =2

v4 =1

v5 =2

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

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

(2;4): 1 + 1 > 1; ∆24 = 1 + 1 - 1 = 1 

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

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

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

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

Aі

Bj

uі

b1 = 100

b2 = 20

b3 = 70

b4=90

b5=180

а1 = 300

1

30

4

2

70

1

20

2

180

u1 = 0

а2 = 90

2

2

20

3

1

70

3

u2 = 1

а3 = 70

3

70

4 5 6 7

u3 = 2

vj

v1 =1

v2 =1

v3 =2

v4 =1

v5 =2

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

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

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

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

>F(x) = 1*30 + 2*70 + 1*20 + 2*180 + 2*20 + 1*70 + 3*70 = 870

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


>Завдання 4

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

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

.

>Розв’язок

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

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

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

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

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

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

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

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

x1+x2≤5

x1=0

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

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

>F(X) = 4*0 + 7*5 = 35


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

Навігація