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

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

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

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

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

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

Розв’язок:

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

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

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

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

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

Х₁=Х₂=Х₃=0 → отримаємо значення базисних змінних: Х₄=25 Х₅=60 Х₆=196, а сам опорний план буде мати такій виляд:

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

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

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

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

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

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

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

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

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

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

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

Розрахунок:

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

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

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

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

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

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

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

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

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

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

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

 т.км

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

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

 т/км

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

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

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

 т.км.

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

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

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

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

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

U₁ +V₂ =2<9₁ +V₃ =0<7₂ +V₁ =0<3₂ +V₃ =-1<5₂ +V₄ =1<5₃ +V₁ =3<6₃ +V₂ =4<8₃ +V₃ =2<3₄ +V₄ =3=3₅ +V₁=-1<0₅ +V₃=-2<0₅ +V₅=0=0

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

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

т.км.

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

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