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

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

>Завдання 1

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

>Меблева фабрикавиготовляєстоли,стільці,тумби йкнижковішафивикористовуючидошки двохвидів,причому фабрикамає 500м2дошок Першого виду й 1000м2дошок іншого виду.Заданітакожтрудовіресурси вкількості 800людино-годин. Утаблицінаведенінорматививитрат шкірного видуресурсів навиготовлення одного виду йприбуток відреалізаціїодиницівиробу.

>Ресурси >Витрати однієювиріб Запассировини, м2
>Столи >Стільці >Тумби >Книжковішафи
>Дошки І виду, м2 5 1 9 12 500
>Дошки ІІ виду, м2 2 3 4 1 1000
>Трудовіресурси,люд.год. 3 2 5 10 800
>Прибуток відреалізації одноговиробу,грн.од. 12 5 15 10

>Визначитиасортимент, щомаксимізуєприбуток.

>Розв’язок

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

=12х1+5х2 +15х3+10х4.

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

А =>5х1+1х2 +9х3+12х4,

У =>2х1+3х2 +4х3+1х4,

З =>3х1+2х2 +5х3+10х4,

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

>5х1+1х2 +9х3+12х4 500

>2х1+3х2 +4х3+1х4 1000

>3х1+2х2 +5х3+10х4 800

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

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

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

>Розв'язуємо завданнялінійногопрограмуваннясимплексним методом.Введемобаланснізмінніх5 0,х6 0,х7 0.Їх величинапоки щоневідома, але й така, щоперетворюєвідповіднунерівність уточнурівність.Після цого, завданнялінійногопрограмуваннянабудевигляду: =12х1+5х2 +15х3+10х4 max приобмеженнях

дех1,...,х7>0

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

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

План >Базис У >x1 >x2 >x3 >x4 >x5 >x6 >x7 >min
1 >x5 500 5 1 9 12 1 0 0 55.56
>x6 1000 2 3 4 1 0 1 0 250
>x7 800 3 2 5 10 0 0 1 160
>Індексний ряд >F(X1) 0 -12 -5 -15 -10 0 0 0 0

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

План >Базис У >x1 >x2 >x3 >x4 >x5 >x6 >x7 >min
2 >x3 55.56 0.56 0.11 1 1.33 0.11 0 0 100
>x6 777.78 -0.22 2.56 0 -4.33 -0.44 1 0 0
>x7 522.22 0.22 1.44 0 3.33 -0.56 0 1 2350
>Індексний ряд >F(X2) 833.33 -3.67 -3.33 0 10 1.67 0 0 0

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

План >Базис У >x1 >x2 >x3 >x4 >x5 >x6 >x7 >min
3 >x1 100 1 0.2 1.8 2.4 0.2 0 0 500
>x6 800 0 2.6 0.4 -3.8 -0.4 1 0 307.69
>x7 500 0 1.4 -0.4 2.8 -0.6 0 1 357.14
>Індексний ряд >F(X3) 1200 0 -2.6 6.6 18.8 2.4 0 0 0

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

План >Базис У >x1 >x2 >x3 >x4 >x5 >x6 >x7 >min
4 >x1 38.46 1 0 1.77 2.69 0.23 -0.08 0 500
>x2 307.69 0 1 0.15 -1.46 -0.15 0.38 0 307.69
>x7 69.23 0 0 -0.62 4.85 -0.38 -0.54 1 357.14
>Індексний ряд >F(X4) 2000 0 0 7 15 2 1 0 0

Ос-кільки усіоцінки >0, тознайденооптимальний план, щозабезпечуємаксимальнийприбуток:х1=38.46,х2=307.69,х3=0,х4=0,х5=0,х6=0,х7=69.23.Прибуток, привипускупродукції зацим планом,становить 2000 грн.


>Завдання 2

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

>Розв’язок

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

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

 

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

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

->2X1-5X2-10

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

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

А, У, СП.

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

>F(Y)=10Y1+28Y2-8Y3 (>min)

>Обмеження:

->2Y1+3Y2+1Y3 5

->14Y1+2Y2-11Y3 5

>Y10

>Y20

>Y30


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

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

>2x1+5x210

>3x1+4x228

>x1-3x25

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

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

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

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

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

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

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

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

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

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

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

>X1 = (0,0,0,28,5,10)


План  >Базис  У  >x1  >x2  >x3  >x4  >x5  >x6
 0  >x6  10  2  5  -1  0  0  1
   >x4  28  3  4  0  1  0  0
   >x5  5  1  -3  0  0  1  0
 >Індексний ряд  >F(X0)  ->10M  ->8-2M  ->2-5M  >1M  0  0  0

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

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

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

План  >Базис  У  >x1  >x2  >x3  >x4  >x5  >x6  >min
 2  >x2  2  0.4  1  -0.2  0  0  0.2  5
   >x4  20  1.4  0  0.8  1  0  -0.8  14.29
   >x5  11  2.2  0  -0.6  0  1  0.6  5
 >Індексний ряд  >F(X2)  4  -7.2  0  -0.4  0  0  >0.4+1M  0

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

План  >Базис  У  >x1  >x2  >x3  >x4  >x5  >x6  >min
 3  >x1  5  1  2.5  -0.5  0  0  0.5  0
   >x4  13  0  -3.5  1.5  1  0  -1.5  8.67
   >x5  0  0  -5.5  0.5  0  1  -0.5  0
>Індексний ряд  >F(X3)  40  0  18  -4  0  0  >4+1M  0

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

План  >Базис  У  >x1  >x2  >x3  >x4  >x5  >x6  >min
 4  >x1  5  1  -3  0  0  1  0  0
   >x4  13  0  13  0  1  -3  0  1
   >x3  0  0  -11  1  0  2  -1  0
>Індексний ряд  >F(X4)  40  0  -26  0  0  8  >1M  0

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

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

План  >Базис  У  >x1  >x2  >x3  >x4  >x5  >x6
 5  >x1  8  1  0  0  0.2308  0.3077  0
   >x2  1  0  1  0  0.0769  -0.2308  0
   >x3  11  0  0  1  0.8462  -0.5385  -1
>Індексний ряд  >F(X5)  66  0  0  0  2  2  >1M

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

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

>x1 = 8

>x2 = 1

>x3 = 11

>F(X) = 8*8 + 2*1 = 66


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

>2y1+3y2+y38

>5y1+4y2-3y32

>10y1+28y2+5y3 =>min

>y1 0

>y2 0

>y3 0

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

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

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

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

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

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

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

>y1 = 0

>y2 = 2

>y3 = 2

>Z(Y) = 10*0+28*2+5*2 = 66


>Завдання 3

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

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

>Розв’язок

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

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

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


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

В1 В2 >В3 >В4 >В5 >Запаси
А1 1 4 7 2 3 300
А2 1 5 3 1 6 90
А3 2 1 3 1 4 70
А4 0 0 0 0 0 10
>Потреби 100 20 70 100 180

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

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

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

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

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

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

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

за умів:

 

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

>Ai >Bj >ui
>b1 = 100 >b2 = 20 >b3 = 70 >b4=100 >b5=180
>а1 = 300

1

100

4

20

7

[-] 70

2

100

3

[+] 10

>u1 = 0
А2 = 90 1 5

3

[+]

1

6

[-] 90

>u2 = 3
>а3 = 70 2 1 3 1

4

70

>u3 = 1
>а4 = 10 0 0 0 0

0

10

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

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

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

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

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

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

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

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

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

(2;3): 3 + 7 > 3; ∆23 = 3 + 7 - 3 = 7

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

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

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

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

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

(4;3): -3 + 7 > 0; ∆43 = -3 + 7 - 0 = 4

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

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

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

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

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

>Ai >Bj >ui
>b1 = 100 >b2 = 20 >b3 = 70 >b4=100 >b5=180
>а1 = 300

1

100

4

20

7

2

[-] 100

3

[+] 80

>u1 = 0
А2 = 90 1 5

3

70

1

[+]

6

[-] 20

>u2 = 3
>а3 = 70 2 1 3 1

4

70

>u3 = 1
>а4 = 10 0 0 0 0

0

10

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

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

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

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

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

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

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

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

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

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


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

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

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

>Ai >Bj >ui
>b1 = 100 >b2 = 20 >b3 = 70 >b4=100 >b5=180
>а1 = 300

1

100

4

[-] 20

7

2

80

3

[+] 100

>u1 = 0
А2 = 90 1 5

3

70

1

20

6 >u2 = -1
>а3 = 70 2
Страница 1 из 2 | Следующая страница

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

Навігація