Реферати українською » Экономико-математическое моделирование » Математічні Моделі задач лінійного програмування


Реферат Математічні Моделі задач лінійного програмування

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

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

>Розв’язок

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

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

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

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


>0х1-11х2-11

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

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

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

>F(Y)=14Y1+27Y2-11Y3 (>max)

>Обмеження:

>8Y1+3Y2+0Y35

->14Y1+2Y2-11Y33

>Y10

>Y20

>Y30

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

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

>8x1-14x214

>3x1+2x227

>x211

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

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

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

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

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

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

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

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

План >Базис У >x1 >x2 >x3 >x4 >x5 >x6 >x7 >min
1 >x6 14 8 -14 -1 0 0 1 0 1.75
>x7 27 3 2 0 -1 0 0 1 9
>x5 11 0 1 0 0 1 0 0 0
>Індексний ряд >F(X1) 4100000 1099995 -1200003 -100000 -100000 0 0 0 0

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

>математичний модельсимплекснийлінійний

План >Базис У >x1 >x2 >x3 >x4 >x5 >x6 >x7 >min
2 >x1 1.75 1 -1.75 -0.13 0 0 0.13 0 0
>x7 21.75 0 7.25 0.38 -1 0 -0.38 1 3
>x5 11 0 1 0 0 1 0 0 11
>Індексний ряд >F(X2) 2175008.75 0 724988.25 37499.38 -100000 0 -137499.38 0 0

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

План >Базис У >x1 >x2 >x3 >x4 >x5 >x6 >x7 >min
3 >x1 7 1 0 -0.03 -0.24 0 0.03 0.24 0
>x2 3 0 1 0.05 -0.14 0 -0.05 0.14 3
>x5 8 0 0 -0.05 0.14 1 0.05 -0.14 11
>Індексний ряд >F(X3) 44 0 0 -0.02 -1.62 0 -99999.98 -99998.38 0

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

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

>x1 = 7

>x2 = 3

>x5 = 8

>F(X) = 5*7 + 3*3 = 44

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

>F(Y)=14Y1+27Y2-11Y3 (>max)

>Обмеження:

>8Y1+3Y2+0Y35

->14Y1+2Y2-11Y33

>Y10

>Y20

>Y30

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

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

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

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

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

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

План >Базис У >x1 >x2 >x3 >x4 >x5 >min
1 >x4 5 8 3 0 1 0 1.67
>x5 3 -14 2 -11 0 1 1.5
>Індексний ряд >F(X1) 0 -14 -27 11 0 0 0
План >Базис У >x1 >x2 >x3 >x4 >x5 >min
2 >X4 0.5 29 0 16.5 1 -1.5 0.0172
>X2 1.5 -7 1 -5.5 0 0.5 0
>Индексная рядок >F(X2) 40.5 -203 0 -137.5 0 13.5 0
План >Базис У >x1 >x2 >x3 >x4 >x5
3 >x1 0.0172 1 0 0.569 0.0345 -0.0517
>x2 1.62 0 1 -1.52 0.2414 0.1379
>Индексная рядок >F(X3) 44 0 0 -22 7 3
План >Базис У >x1 >x2 >x3 >x4 >x5
4 >x3 0.0303 1.76 0 1 0.0606 -0.0909
>x2 1.67 2.67 1 0 0.3333 0
>Индексная рядок >F(X4) 44.67 38.67 0 0 8.33 1

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

>x3 = 0.0303

>x2 = 1.67

>F(X) = 27*1.67 + -11*0.03 = 44.67


>Завдання 3

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

1 4 1 5 6 300
1 3 1 1 2 250
4 1 2 2 3 200
100 120 90 70 80

>Розв’язок

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

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

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

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

В1 В2 >В3 >В4 >В5 В6 >Запаси
А1 1 4 1 5 6 0 300
А2 1 3 1 1 2 0 250
А3 4 1 2 2 3 0 200
>Потреби 100 120 90 70 80 290

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

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

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

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


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

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

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

за умів:

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

>Ai >Bj >ui
>b1 = 100 >b2 = 120 >b3 = 90 >b4=70 >b5=80 >B6=290
>а1 = 300

1

100

4

[-]120

1

[+]80

5 6 0 >u1 = 0
А2 = 250 1 3

1

[-]10

1

70

2

80

0

[+]90

>u2 = 0
>а3 = 200 4

1

[+]

2 2 3

0

[-]200

>u3 = 0
>vj >v1 =1 >v2 =4 >v3 =1 >v4 =1 >v5=2 >V6 =0

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

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

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

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

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

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

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

>А1B6 :u1 +v6 = 0 + 0 = 0=0;

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

>А2B2 :u2 +v2 = 0 + 4 = 4>3;

>А3B1 :u3 +v1 = 0 + 1 = 1< 4;

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

>А3B3 :u3 +v3 = 0 + 1 = 1<2;

>А3B4 :u4 +v1 = 0 + 1 = 1<2;

>А3B5 :u4 +v2 = 0 + 2 = 2<3;

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

>А2B2 :u2 +v2 = 0 + 4 = 4>3;

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

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

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

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

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

>Ai >Bj >ui
>b1 = 100 >b2 = 120 >b3 = 90 >b4=70 >b5=80 >B6=290
>а1 = 300

1

100

4

[-] 110

1

90

5 6

0

[+]

>u1 = 0
А2 = 250 1 3 1

1

70

2

80

0

100

>u2 = -3
>а3 = 200 4

1

[+] 10

2 2 3

0

[-] 190

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

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

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

(>А1B6): 0 + 3 = 3 >0;

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

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

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

>Ai >Bj >ui
>b1 = 100 >b2 = 120 >b3 = 90 >b4=70 >b5=80 >B6=290
>а1 = 300

1

100

4

1

90

5 6

0

110

>u1 = 0
А2 = 250 1 3 1

1

70

2

80

0

100

>u2 = 0
>а3 = 200 4

1

120

2 2 3

0

80

>u3 = 0
>vj >v1 =1 >v2 =1 >v3 =1 >v4 =1 >v5=2 >V6 =0

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

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

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

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

>Z(x) = 1*100 + 1*90 + 0*110 + 1*70 + 2*80 + 0*100 + 1*120 + 0*80 = 540

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


>Завдання 4

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

,  ,  ,

>Розв’язок

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

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

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


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

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

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

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

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

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

>x1+2x22

>x1=0

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

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

>F(X) = 6*0 + 8*1 = 8


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

Навігація