Реферат Оптімізація Економічних показніків

Страница 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

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

>Розв’язок

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

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

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

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


->8х1-6ч2-48

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

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

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

>F(Y)=-48Y1-5Y2+12Y3 (>max)

>Обмеження:

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

->6Y1-2Y2+1Y32

>Y10

>Y20

>Y30

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

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

>8x1+6x248

>x1-2x2-5

>4x1+x212

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

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

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

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

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

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

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

План >Базис У >x1 >x2 >x3 >x4 >x5 >x6 >min
0 >x3 33 11 0 1 -3 0 3 0
>x2 2.5 -0.5 1 0 0.5 0 -0.5 0
>x5 9.5 4.5 0 0 -0.5 1 0.5 0
>Індексний ряд >F(X) 5 0 0 0 1 0 -100001 0

У базисномустовпчику усіелементипозитивні.

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

План >Базис У >x1 >x2 >x3 >x4 >x5 >x6 >min
1 >x3 33 11 0 1 -3 0 3 0
>x2 2.5 -0.5 1 0 0.5 0 -0.5 5
>x5 9.5 4.5 0 0 -0.5 1 0.5 0
>Індекснийрядок >F(X1) 5 0 0 0 1 0 -100001 0

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

План >Базис У >x1 >x2 >x3 >x4 >x5 >x6 >min
2 >x3 48 8 6 1 0 0 0 6
>x4 5 -1 2 0 1 0 -1 0
>x5 12 4 1 0 0 1 0 3
>Індекснийрядок >F(X2) 0 1 -2 0 0 0 -100000 0

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

План >Базис У >x1 >x2 >x3 >x4 >x5 >x6 >min
3 >x3 24 0 4 1 0 -2 0 6
>x4 8 0 2.25 0 1 0.25 -1 0
>x1 3 1 0.25 0 0 0.25 0 3
>Індекснийрядок >F(X3) -3 0 -2.25 0 0 -0.25 -100000 0

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

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

>x3 = 24

>x4 = 8

>x1 = 3

>F(X) = -1*3 = -3

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

>F(Y) = ->48Y1-5Y2+12Y3 (>max)

>Обмеження:

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

->6Y1-2Y2+1Y32

>Y10

>Y20

>Y30

>лінійнийпрограмуваннятранспортна завдання

Ос-кільки, управійчастиніприсутнівід’ємнізначення,перемножимовідповідні рядки на (-1).

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

>F(X) = ->48x1-5x2+12x3 принаступнихобмеженнях:

>8x1-x2-4x31

->6x1-2x2+x32

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

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

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

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

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

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

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

>F(X) = ->48x1-5x2+12x3 -Mx6 =>>max

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

>X1 = (0,0,0,0,2,1)


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

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

План >Базис У >x1 >x2 >x3 >x4 >x5 >x6 >min
1 >x6 1 8 -1 -4 -1 0 1 0.125
>x5 2 -6 -2 1 0 1 0 0
>Індекснийрядок >F(X1) 0 0 0 0 0 0 0 0
План >Базис У >x1 >x2 >x3 >x4 >x5 >x6
2 >x1 0.125 1 -0.125 -0.5 -0.125 0 0.125
>x5 2.75 0 -2.75 -2 -0.75 1 0.75
>Індекснийрядок >F(X2) 0 0 0 0 0 0 0

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

>x1 = 0.125

>x5 = 2.75

>F(X) = -48*0.13 = -6


>Завдання 3

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

1 4 7 8 1 200
2 3 1 4 1 150
5 1 3 2 3 350
120 130 200 180 110

>Розв’язок

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

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

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

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


В1 В2 >В3 >В4 >В5 >Запаси
А1 1 4 7 8 1 200
А2 2 3 1 4 1 150
А3 5 1 3 2 3 350
А4 0 0 0 0 0 40
>Потреби 120 130 200 180 110

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

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

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

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

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

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

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

за умів:

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

>Ai >Bj >ui
>b1 = 120 >b2 = 130 >b3 = 200 >b4=180 >b5=110
>а1 = 200

1

120

4

80

7 8 1 >u1 = 0
А2 = 150 2

3

50

1

100

4 1 >u2 = -1
>а3 = 350 5 1

3

100

2

180

3

70

>u3 = 1
>а4 = 40 0 0 0 0

0

40

>u4 = -2
>vj >v1 =1 >v2 =4 >v3 =2 >v4 =1 >V5 =2

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

>Z1 = 1 120 + 4 80 + 3 50 +1 100 +3 100+ 2 180 + 3 70 + 0 40 = 1560

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

>Перевіримооптимальність опорного плану,складемо системурівнянь (длязаповненихклітинтаблиці) длявизначенняпотенціалів Першого опорного плану:

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

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

>А1B3 :u1 +v3 = 0 + 2 = 2 < 7;

>А1B4 :u1 +v4 = 0 + 1 = 1 < 8;

>А1B5 :u1 +v5 = 0 + 2 = 2 > 1;

>А2B1 :u2 +v1 = -1 + 1 = 0 < 2;

>А2B4 :u2 +v4 = -1 + 1 = 0 < 4;

>А2B5 :u2 +v5 = -1 + 2 = 1 =1;

>А3B1 :u3 +v1 = 1 + 1 = 2 < 5;

>А3B2 :u3 +v2 = 1 + 4 = 5 > 1;

>А4B1 :u4 +v1 = -2 + 1 = -1 < 0;

>А4B2 :u4 +v2 = -2 + 4 = 2 > 0;

>А4B3 :u4 +v3 = -2 + 2 = 0 = 0;

>А4B4 :u4 +v4 = -2 + 1 = -1 < 0.

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

>А1B5 :u1 +v5 = 0 + 2 = 2 > 1

>А3B2 :u3 +v2 = 1 + 4 = 5 > 1;

>А4B2 :u4 +v2 = -2 + 4 = 2 > 0.

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

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

Уданомуразі ,тобто .Виконавшиперерозподілперевезеньпродукції згідно ззаписаними правилами,дістанемотакіновізначення: дляклітинкиА3B3 — 50 од.продукції, аА2B2 –звільняється й вновійтаблиці якщопорожньою, аА3B2 – (0 + 50) = 50 од.КлітинкаА2B3 – 100 + 50 = 150.Усііншізаповненіклітинкипершоїтаблиці, котрі не входили до циклу,переписуємо у другутаблицю беззмін.Кількістьзаповненихклітинок уновійтаблицітакожмаєвідповідатиумовіневиродженості плану,тобтодорівнювати (n +m – 1).

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

>Ai >Bj >ui
>b1 = 120 >b2 = 130 >b3 = 200 >b4=180 >b5=110
>а1 = 200

1

120

4

80

7 8 1 >u1 = 0
А2 = 150 2 3

1

150

4 1 >u2 = -5
>а3 = 350 5

1

50

3

50

2

180

3

70

>u3 = -3
>а4 = 40 0 0 0 0

0

40

>u4 = -6
>vj >v1 =1 >v2 =4 >v3 =6 >v4 =5 >V5 =6

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

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

>А1B5 :u1 +v5 = 0 + 6 = 6 > 1

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

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

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


>Ai >Bj >ui
>b1 = 120 >b2 = 130 >b3 = 200 >b4=180 >b5=110
>а1 = 200

1

120

4

[-] 10

7 8

1

[+] 70

>u1 = 0
А2 = 150 2 3

1

150

4 1 >u2 = -5
>а3 = 350 5

1

[+] 120

3

[-] 50

2

180

3 >u3 = -3
>а4 = 40 0 0

0

[+]

0

0

[-] 40

>u4 = -1
>vj >v1 =1 >v2 =4 >v3 =6 >v4 =5 >V5 =1

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

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

(>А4B2): -1 + 4 > 0

(>А4B3): -1 + 6 > 0

(>А4B4): -1 + 5 > 0

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

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

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

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

>Ai >Bj >ui
>b1 = 120 >b2 = 130 >b3 = 200 >b4=180 >b5=110
>а1 = 200

1

120

4 7 8

1

80

>u1 = 0
А2 = 150 2 3

1

150

4 1 >u2 = 0
Страница 1 из 2 | Следующая страница

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

Навігація