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

Завдання 1

Цех випускає валиі втулки. На виробництво одного вала робочий витрачає 3 год., однієї втулки – 2год. Від реалізації одного вала підприємство одержує прибуток 80 грн., а відреалізації однієї втулки – 60 грн. Цех має випустити не менше 100 валів і неменше 200 втулок. Скільки валів і скільки втулок має випустити цех, щободержати найбільший прибуток, якщо фонд робочого часу робітників становить 900людино-годин?

Ресурс Вироби Фонд робочого часу Вали Втулки Робітник, год. од. 3 2 900 Вартість, грн. од. 80 60

Розв’язок

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

∫= 80х1+60х2.

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

CI=3х1+2х2,

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

3х1+2х2≤900

Окрім того, валівпотрібно виготовити не менше 100 штук, а втулок – 200 шт., тобто повинні виконуватисьще нерівності: х1≥ 100,х2≥200.

Такимчином, приходимо до математичної моделі:

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

/>

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

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

3x1+ 2x2 + 1x3 + 0x4 + 0x5 + 0x6 + 0x7 = 900

1x1+ 0x2 + 0x3-1x4 + 0x5 + 1x6 + 0x7 = 100

0x1+ 1x2 + 0x3 + 0x4-1x5 + 0x6 + 1x7 = 200

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

F(X)= 80 x1 +60 x2 — M x6 — M x7 => max

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

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

Зметою формулювання задачі для вирішення її в табличній формі скористаємосявиразами з системи рівнянь для штучних змінних:

x6= 100-x1 +x4

x7= 200-x2 +x5

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

F(X)= 80x1 + 60x2 — M(100-x1 +x4 ) — M(200-x2 +x5 ) => max

або

F(X)= (80+1M)x1 +(60+1M)x2 +(-1M)x4 +(-1M)x5 +(-300M) => max

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

3 2 1 1 -1 1 1 -1 1

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

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

x3, x6, x7

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

X1 = (0,0,900,0,0,100,200)

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

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

План Базис В x1 x2 x3 x4 x5 x6 x7 min 1 x3 900 3 2 1 300 x6 100 1 -1 1 100 x7 200 1 -1 1 Індексний рядок F(X1) -30000000 -100080 -100060 100000

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

План Базис В x1 x2 x3 x4 x5 x6 x7 min 2 x3 600 2 2 3 -3 300 x1 100 1 -1 1 x7 200 1 1 1 200 Індексний рядок F(X2) -19992000 -100060 -80 100080

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

План Базис В x1 x2 x3 x4 x5 x6 x7 min 3 x3 200 1 3 2 -3 -2 66,67 x1 100 1 -1 1 x2 200 1 -1 1 Індексний рядок F(X3) 20000 -80 -60 100080 100060

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

План Базис В x1 x2 x3 x4 x5 x6 x7 min 4 x4 66,67 0,33 1 0,67 -1 -0,67 100 x1 166,67 1 0,33 0,67 -0,67 250 x2 200 1 -1 1 Індексний рядок F(X4) 25333,33 26,67 -6,67 100000 100006,67

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

План Базис В x1 x2 x3 x4 x5 x6 x7 min 5 x5 100 0,5 1,5 1 -1,5 -1 100 x1 100 1 -1 1 250 x2 300 1 0,5 1,5 -1,5 Індексний рядок F(X5) 26000 30 10 99990 100000

Оскількивсі оцінки >0, то знайдено оптимальний план, що забезпечує максимальнийприбуток: х1=100, х2=300. Прибуток, при випуску продукції за цим планом, становить26000 грн.

/>

Завдання 2

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

/>

/>

Розв’язок

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

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

x1+2x2≤6

-5x1+4x2≤2

7x1+5x2≥35

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

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

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

7x1+ 5x2+ 0x3+ 0x4-1x5= 35

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

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

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

7x1+ 5x2+ 0x3+ 0x4-1x5+ 1x6= 35

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

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

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

X1= (0,0,6,2,0,35)

План Базис В x1 x2 x3 x4 x5 х6 х3 6 1 2 1 x4 2 -5 4 1 х6 35 7 5 -1 1 Індексний рядок F(X0)

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

План Базис В x1 x2 x3 x4 x5 x6 min 1 х3 6 1 2 1 6 x4 2 -5 4 1 х6 35 7 5 -1 1 5 Індексний рядок F(X1)

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

План Базис В x1 x2 x3 x4 x5 x6 min 2 х3 1 1,29 1 0,1429 -0,1429 7 x4 27 7,57 1 -0,7143 0,7143 х1 5 1 0,7143 -0,1429 0,1429 Індексний рядок F(X2)

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

План Базис В x1 x2 x3 x4 x5 x6 3 х5 7 9 7 1 -1 x4 32 14 5 1 х1 6 1 2 1 Індексний рядок F(X3)

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

x5 = 7

x4 = 32

x1 = 6

F(X) = 3*6 = 18

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

y1+5y2+7y3≥3

2y1-4y2+5y3≥1

6y1-2y2+35y3=> min

y1≥ 0

y2≤ 0

y3≤ 0

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

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

/>

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

/>

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

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

Запишемооптимальний план двоїстої задачі:

y1= 3

y2= 0

y3= 0

Z(Y)= 6*3+-2*0+35*0 = 18

Завдання 3

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

2 4 5 8 6 180 7 3 6 4 5 300 8 5 6 5 3 230 110 140 220 190 120

Розв’язок

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

/>

/>

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

/>

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

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

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

В1 В2 В3 В4 В5 Запаси А1 2 4 5 8 6 180 А2 7 3 6 4 5 300 А3 8 5 6 5 3 230 А4 70 Потреби 110 140 220 190 120

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

/>

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

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

/>

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

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

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

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

за умов:

/>

/> 

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

Ai Bj ui b1 = 110 b2 = 140 b3 = 220 b4=190 b5=120 а1 = 180

2

110

4

70

5 8 6 u1 = 0 а2 = 300 7

3

70

6

[-] 220

4

[+] 10

5 u2 = -1 а3 = 230 8 5 6

5

[-] 180

3

[+] 50

u3 = 0 а4 = 70

[+]

[-] 70

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

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

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

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

u1=0, u2=-1, u3=0,u4=-3, v1=2, v2=4, v3=7 v4=5, v5=3

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

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

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

(1;3): 0 + 7 > 5

(3;3): 0 + 7 > 6

(4;2): -3 + 4 > 0

(4;3): -3 + 7 > 0

(4;4): -3 + 5 > 0

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

Тепер необхідноперемістити продукцію в межах побудованого циклу.

З вантажів хijщо стоять в мінусових клітинах, вибираємо найменше, тобто у = min (4;5) = 70.

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

Для цього упорожню клітинку А4B3 переносимо менше з чисел хij, які розміщені в клітинкахзі знаком «–».

Одночасно цесаме число хij додаємо до відповідних чисел, що розміщені в клітинках зі знаком«+», та віднімаємо від чисел, що розміщені в клітинках, позначених знаком «–».

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

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

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

Ai Bj ui b1 = 110 b2 = 140 b3 = 220 b4=190 b5=120 а1 = 180

2

110

4

[-] 70

5

[+]

8 6 u1 = 0 а2 = 300 7

3

[+] 70

6

[-] 150

4

80

5 u2 = -1 а3 = 230 8 5 6

5

110

3

120

u3 = 0 а4 = 70

70

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

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

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

(1;3): 0 + 7 > 5

(3;3): 0 + 7 > 6

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

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

Цикл наведено втаблиці.

З вантажів хijщо стоять в мінусових клітинах, вибираємо найменше, тобто у = min (А1B2) = 70.

Додаємо 70 дообсягів вантажів, що стоять в плюсових клітинах і віднімаємо 70 з Хij, щостоять в мінусових клітинах.

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

Ai Bj ui b1 = 110 b2 = 140 b3 = 220 b4=190 b5=120 а1 = 180

2

110

4

5

70

8 6 u1 = 0 а2 = 300 7

3

140

6

[-] 80

4

[+] 80

5 u2 = 1 а3 = 230 8 5

6

[+]

5

[-] 110

3

120

u3 = 2 а4 = 70

70

u4 = -5 vj v1 = 2 v2 = 2 v3 = 5 v4 = 3 v5 = 1

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

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

(3;3): 2 + 5 > 6

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

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

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

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

Ai Bj ui b1 = 110 b2 = 140 b3 = 220 b4=190 b5=120 а1 = 180

2

110

4

5

70

8 6 u1 = 0 а2 = 300 7

3

140

6

4

160

5 u2 = 0 а3 = 230 8 5

6

80

5

30

3

120

u3 = 1 а4 = 70

70

u4 = -5 vj v1 = 2 v2 = 3 v3 = 5 v4 = 4 v5 = 2

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

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

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

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

F(x)= 2*110 + 5*70 + 3*140 + 4*160 + 6*80 + 5*30 + 3*120 + 0*70 = 2620

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

Завдання 4

Знайти графічнимметодом екстремуми функцій в області, визначеній нерівностями.

/>

/> 

/> 

/>

/>.

Розв’язок

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

/>

Межі області

/>

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

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

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

/>

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

/>

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

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

x1+x2≥1

x1=0

Вирішившисистему рівнянь, одержимо

x1 = 0, x2 = 1

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

F(X) = 9*0 + 8*1= 8