Задача лінійного програмування

Задача використання ресурсів

Для виготовлення різних виробів А, В і С підприємство використовує три види сировини (І, ІІ і ІІІ). Норми витрати сировини на виробництво одного виробу, ціна одного виробу А, В і С, а також загальна кількість сировини кожного виду, яка може бути використана підприємством, навені в таблиці.

Вид сировиниНорми витрат сировини (кг) на один вирібЗагальна кількість сировини, кгАВСІ16025ІІ83460ІІІ56296Ціна одного виробу, у.о.1053-

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

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

Розвязок:

Введемо позначення:

Нехай X1, X2, Х3 - це відповідно кільсть плит А, В і С, що потрібно виготивити підприємству.- сумарний прибуток від реалізації всієї продукції.

Складемо матеметичну модель задачі:

Приведемо дану задачу до канонічної форми запису, з цією метою введемо три додаткові змінні (Х4, Х5, Х6) які означатимуть залишкі сировини трьох видів, після виговлення усіх плит.

Для розвяку даної задачі утворимо утворимо початковий оптимальний початковий план. Для цього надаємо:

Х1=Х2=Х3=0 ? отримаємо значення базисних змінних: Х4=25 Х5=60 Х6=196, а сам опорний план буде мати такій виляд:

Хо(0; 0; 0; 25; 60; 96)

Розвязок задачі продовжимо з використанням симплекс-таблиць

№ сим. табл Б СБ А0С1=10С2=5С3=3С4=0С5=0С6=0QijА1А2А3А4А5А61А402516010025А50608340107,5А609656200119,2m+10-10-5-30002А4017,505,625-0,51-0,12503,11А1107,510,3750,500,125020А6058,504,125-0,50-0,625114,18m+1750-1,25201,2503А253,1101-0,080,17-0,020А1106,33100,53-0,060,130А6045,6600-0,13-0,73-0,531m+178,88001,880,221,220

Умова оптимальності розвязку задачі максимізації:

Zj - сума добутків

Економічне пояснення розвязку задачі:

В результаті розвязку задачі отримали оптимальний план

З цього плану досягається максимальне значення цільової функції: F=78,88

Висновок: Для того щоб отримати максимальний прибуток в кількості 78,8 в умовах постановки даної задачі необхідно виготовляти: 6,33 виробів І типу, 3,11 виробів ІI типу, при цьому залишається не використаною сировина ІII-го виду в кількості 45,66.

вартість виготовлення перевезення будівельний

Транспортна задача

Для будівництва обєктів В1,…, Вn використовується цегла, що виготовляється на заводах А1,…, А3. Щоденно кожен із заводів може виготовляти а1,…, а3 ум. од. цегли. Щоденні потреби в цеглі на кожному із будівельних обєктів відповідно рівні b1,…, b4. Тарифи перевезень 1 ум. од. цегли від кожного із заводів до кожного з обєктів (год.) задаються матрицею Т.класти такий план перевезень цегли до будівелтних обєктів, при якому загальна вартість перевезень є мінімальною.

Розрахунок:

. Визначаємо вид транспортної задачі

Визначаємо сумарні запаси і сумарні потреби

І для її розвязку приведемо транспортну задачу до закритої.

Для цього введемо фіктивного постачальника , запаси вантажів у якого складатимуть

Матриця тарифів перевезень буде мати такий вигляд

2. Складемо опорний план перевезень вантажів

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

Для кожного з опорних планів повинна виконуватися умова не виродженості:

Кількість заповнених клітинок таблиці перевезень (маршрутів перевезень) повинна складатись

Опорний план за методом Півн. Зх. кута

J іСпоживачіЗапаси В1В2В3В4ПостачальникиA119723030---A2315540535--A3683470-4525-A4231360--060A5000010---10Потреби35802570210

Визначимо сумарні затрати на перевезення вантажів.

т.км

Опорний план за методом мінімального елементу

J іСпоживачіЗапасиВ1В2В3В4ПостачальникиA1 19723030--0A2 315540-40--A3 683470---70A4 23136053025-A5000010-10--Потреби35802570210

Сумарні затрати на перевезення для даного опорного плану

т/км

Опорний план за методом подвійної переваги

J іСпоживачіЗапасиВ1В2В3В4ПостачальникиA1 19723030--0A2 315540-40--A3 683470---70A4 23136053025-A5000010-10--Потреби35802570210

Сумарні затра

ти на перевезення для даного опорного плану

т.км.

Умови оптимальності плану перевезеньтранспортної задачі:

- для всіх заповнених клітинок

для всіх порожніх клітинок

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

Перевіримо порожні клітинки на умову оптимальності

U1 +V2 =2<91 +V3 =0<72 +V1 =0<32 +V3 =-1<52 +V4 =1<53 +V1 =3<63 +V2 =4<83 +V3 =2<34 +V4 =3=35 +V1=-1<05 +V3=-2<05 +V5=0=0

Оскільки умова оптимальності для порожніх клітинок виконується, то даний опорний план є оптимальним.

Затрати на перевезення вантажів за планом 2.2 будуть мінімальними і складуть:

т.км.

Матриця перевезень оптимального плану матиме вигляд

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