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

Завдання 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 55.56 x6 1000 2 3 4 1 1 250 x7 800 3 2 5 10 1 160 Індексний рядок F(X1) -12 -5 -15 -10

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

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

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

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

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

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

Оскількивсі оцінки >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+0Y3≤5

-14Y1+2Y2-11Y3≤3

Y1≥0

Y2≥0

Y3≥0

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

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

8x1-14x2≥14

3x1+2x2≥27

x2≤11

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

Оскільки маємозмішані умови-обмеження, то введемо штучні змінні 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) = 5 x1 +3x2 +M x6 +M x7 => min

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

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

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

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

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

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

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

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

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

x1 = 7

x2 = 3

x5 = 8

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

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

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

Обмеження:

8Y1+3Y2+0Y3≤5

-14Y1+2Y2-11Y3≤3

Y1≥0

Y2≥0

Y3≥0

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

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

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

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

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

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

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

1

[-]10

1

70

2

80

[+]90

u2 = 0 а3 = 200 4

1

[+]

2 2 3

[-]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 =1 v4=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

[+]

u1 = 0 а2 = 250 1 3 1

1

70

2

80

100

u2 = -3 а3 = 200 4

1

[+] 10

2 2 3

[-] 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

110

u1 = 0 а2 = 250 1 3 1

1

70

2

80

100

u2 = 0 а3 = 200 4

1

120

2 2 3

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 i 5, то її координати задовольняють рівнянням цих прямих:

x1+2x2≥2

x1=0

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

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

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