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

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

>Завдання 1

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

>Фірма, щоспеціалізується навиробництвіелектроприладів,отрималазамовлення навиготовлення 100електроплит.Конструкторамизапропоновано довипуску тримоделі плит А, У й З заціноювідповідно 100, 60 та 50грн.од.Нормивитратсировини длявиготовленняоднієїелектроплитирізних моделей та запассировини нафірмі наведено втаблиці.

>Сировина >Нормивитратсировини,грн.од. Запассировини,грн.од.
А У З
І 10 4 5 700
ІІ 3 2 1 400
>Ціна,грн.од. 100 60 50

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

>Розв’язок

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

=100х1 +60х2+50х3.

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

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

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

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

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

>3х1 +2х2 +1х3 400

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

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

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

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

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

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

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


>Базис >x1 >х2 >x3 >x4 >x5 b
I II III IV V VI VII
а 0 10 4 5 1 0 700
б 0 3 2 1 0 1 400
>d >Індексний ряд, і 100 60 50 0 0 0

>Складаємоперший план. Ос-кількизміннихх4,х5вцільовійфункції немає, тоїмвідповідаютькоефіцієнти 0;

План >Базис У >x1 >x2 >x3 >x4 >x5 >min
1 >x4 700 10 4 5 1 0 70
>x5 400 3 2 1 0 1 133.33
>Індексний ряд >F(X1) 0 -100 -60 -50 0 0 0

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

План >Базис У >x1 >x2 >x3 >x4 >x5 >min
2 >x1 70 1 0.4 0.5 0.1 0 175
>x5 190 0 0.8 -0.5 -0.3 1 237.5
>Індексний ряд >F(X2) 7000 0 -20 0 10 0 0

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

План >Базис У >x1 >x2 >x3 >x4 >x5 >min
3 >x2 175 2.5 1 1.25 0.25 0 175
>x5 50 -2 0 -1.5 -0.5 1 237.5
>Індексний ряд >F(X3) 10500 50 0 25 15 0 0

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

>Дамоекономічнутрактовурозв'язку:щобидосягнути максимальноможливого, за умівзадачі,прибутку (10500 грн.),необхідновиробівдругоїмоделівипустити 175 од.


>Завдання 2

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

>Розв’язок

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

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

>2x1+3x26

>2x1+4x24

>2x1+x24

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

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

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

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

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

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

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

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

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

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

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

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

>x6 =4-2x1-x2+x5

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

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

чи

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

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

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

>x3,x4,x6,

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

>X1 = (0,0,6,4,0,4)

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

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

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

>індексний ряд симплекс метод

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

План  >Базис  У  >x1  >x2  >x3  >x4  >x5  >x6  >min
 2  >x3  2  0  2  1  0  1  -1  1
   >x4  0  0  3  0  1  1  -1  0
   >x1  2  1  0.5  0  0  -0.5  0.5  4
>Індексний ряд >F(X2)  2  0  -1.5  0  0  -0.5 >0.5+1M  0

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

План  >Базис  У  >x1  >x2  >x3  >x4  >x5  >x6
 3  >x3  2  0  0  1  -0.6667  0.3333  -0.3333
   >x2  0  0  1  0  0.3333  0.3333  -0.3333
   >x1  2  1  0  0  -0.1667  -0.6667  0.6667
>Індексний ряд  >F(X3)  2  0  0  0  0.5  0  >1M

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

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

>x3 = 2

>x2 = 0

>x1 = 2

>F(X) = 1*2 + 2*0 = 2

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

>2y1+2y2+2y31

>3y1+4y2+y32

>6y1+4y2+4y3 =>min

>y1 0

 >y2 0

 >y3 0

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

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

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

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

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


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

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

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

>y1 = 0

>y2 = 0.5

>y3 = 0

>Z(Y) = 6*0+4*0.5+4*0 = 2


>Завдання 3

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

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

>Розв’язок

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

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

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

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

В1 В2 >В3 >В4 >В5 В6 >Запаси
А1 5 2 3 6 1 0 150
А2 1 1 4 4 2 0 320
А3 4 1 2 3 5 0 400
>Потреби 100 120 100 200 300 50

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

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

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

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

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

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

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

за умів:

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

>Ai >Bj >ui
>b1 = 100 >b2 = 120 >b3 = 100 >b4=200 >b5=300 >b6=50
>а1 = 150

5

100

2

[-] 50

3 6

1

[+]

0 >u1 = 0
А2 = 320 1

1

[+] 70

4

100

4

[-] 150

2 0 >u2 = -1
>а3 = 400 4 1 2

3

[+] 50

5

[-] 300

0

50

>u3 = -2
>vj >v1 = 5 >v2 = 2 >v3 = 5 >v4 = 5 >v5 = 7 >v6 = 2

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

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

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

>u1 +v1 = 5; 0 +v1 = 5;v1 = 5

>u1 +v2 = 2; 0 +v2 = 2;v2 = 2

>u2 +v2 = 1; 2 +u2 = 1;u2 = -1

>u2 +v3 = 4; -1 +v3 = 4;v3 = 5

>u2 +v4 = 4; -1 +v4 = 4;v4 = 5

>u3 +v4 = 3; 5 +u3 = 3;u3 = -2

>u3 +v5 = 5; -2 +v5 = 5;v5 = 7

>u3 +v6 = 0; -2 +v6 = 0;v6 = 2

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

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

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

(1;3): 0 + 5 > 3; ∆13 = 0 + 5 - 3 = 2

(1;5): 0 + 7 > 1; ∆15 = 0 + 7 - 1 = 6

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

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

(2;5): -1 + 7 > 2; ∆25 = -1 + 7 - 2 = 4

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

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

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

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

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

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

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

>Ai >Bj >ui
>b1 = 100 >b2 = 120 >b3 = 100 >b4=200 >b5=300 >b6=50
>а1 = 150

5

[-] 100

2 3 6

1

[+] 50

0 >u1 = 0
А2 = 320

1

[+]

1

120

4

100

4

[-] 100

2 0 >u2 = 5
>а3 = 400 4 1 2

3

[+] 100

5

[-] 250

0

50

>u3 = 4
>vj >v1 = 5 >v2 = -4 >v3 = -1 >v4 = -1 >v5 = 1 >v6 = -4

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

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

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

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

(2;6): 5 + -4 > 0; ∆26 = 5 + -4 - 0 = 1

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

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

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

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

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

>Ai >Bj >ui
>b1 = 100 >b2 = 120 >b3 = 100 >b4=200 >b5=300 >b6=50
>а1 = 150

5

[-] 0

2 3 6

1

[+] 150

0 >u1 = 0
А2 = 320

1

[+] 100

1

120

4

[-] 100

4 2 0 >u2 = -4
>а3 = 400 4 1

2

[+]

3

200

5

[-] 150

0

50

>u3 = 4
>vj >v1 = 5 >v2 = 5 >v3 = 8 >v4 = -1 >v5 = 1 >v6 = -4

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

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

(1;2): 0 + 5 > 2; ∆12 = 0 + 5 - 2 = 3

(1;3): 0 + 8 > 3; ∆13 = 0 + 8 - 3 = 5

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

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

(3;3): 4 + 8 > 2; ∆33 = 4 + 8 - 2 = 10

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

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

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

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

>Ai >Bj >ui
>b1 =
Страница 1 из 2 | Следующая страница

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

Навігація