Як визначити, що виробництво продукції є рентабельним (нерентабельним)?

Як визначити, що виробництво продукції є рентабельним (нерентабельним)?

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

Ліва частина кожного обмеження двоїстої задачі є вартістю відповідних ресурсів, які використовують для виробництва одиниці j -ї продукції. Якщо ця величина перевищує ціну одиниці продукції (с_j), то виготовляти таку продукцію невигідно, вона нерентабельна і в оптимальному плані прямої задачі відповідна їй змінна х_j = 0. Якщо ж загальна оцінка всіх ресурсів дорівнює ціні одиниці продукції, то виготовляти таку продукцію доцільно, вона рентабельна і в оптимальному плані прямої задачі відповідна змінна х_j > 0.

6. Що означає «правильне відтинання»? Допустимо, що необхідно розв’язувати задачу лінійного програмування, всі або частина змінних якої мають бути цілочисловими. Можливо, якщо розв’язувати задачу, не враховуючи умову цілочисловості, випадково одразу буде отримано потрібний розв’язок. Однак така ситуація малоймовірна. Переваж­но розв’язок не задовольнятиме умову цілочисловості. Тоді накладають додаткове обмеження, яке не виконується для отриманого плану задачі, проте задовольняє будь-який цілочисловий розв’язок. Таке додаткове обмеження називають правильним відтинанням. Система лінійних обмежень задачі доповнюється новою умовою і далі розв’язується отримана задача лінійного програмування. Якщо її розв’язок знову не задовольняє умови цілочисловості, то будується нове лінійне обмеження, що відтинає отриманий розв’язок, не зачіпаючи цілочислових планів. Процес приєднання додаткових обмежень повторюють доти, доки не буде знайдено цілочислового оптимального плану, або доведено, що його не існує.

                                                                                                                                                                                                                                                                                                                                               

У чому сутність теорії двоїстості у лінійному програмуванні?

Зв’язок між оптимальними розв’язками прямої та двоїстої задач встановлюють леми та теореми двоїстості

Лема 3.1 (основна нерівність теорії двоїстості). Якщо  та  — допустимі розв’язки відповідно прямої та двоїстої задач, то виконується нерівність

Лема 3.2 (достатня умова оптимальності). Якщо  та  — допустимі розв’язки відповідно прямої та двоїстої задач, для яких виконується рівність

                                                                                                                                                                     (3.10)

то X ^*, Y ^* — оптимальні розв’язки відповідних задач.

 або .                                                                              (3.7)

Які зваємоспряжені задачі називаються симетричними,а які несиметричними.Чим вони відрізняються

Суть методу Жордана Гаусса

У різноманітних галузях людських знань (наука, виробництво, економіка, теорія масового обслуговування, тощо) часто виникають задачі, розв’язування яких приводить до систем лінійних рівнянь, в яких кількість рівнянь не обов’язково дорівнює кількості невідомих. Невідомих може бути більше або менше від кількості рівнянь. Для розв’язування таких систем розроблено ряд методів, у тому числі й за допомогою визначників. Але найпоширеніший з них - метод Жордана-Гаусса, який не потребує попередніх досліджень на сумісність або несумісність. У процесі розв’язування завжди стає ясно, має система розв’язки чи не має, єдиний її розв’язок чи ні. Оскільки для розв’язування системи рівнянь методом Жордана-Гаусса потрібно на порядок менше математичних операцій, ніж при розв’язуванні за формулами Крамера, то метод Жордана-Гаусса став основним при побудові стандартних програм для сучасних комп’ютерів.

Метод Жордана-Гаусса полягає в послідовному виключенні невідомих за допомогою елементарних перетворень:
1) множення рівняння на деяке число;
2)заміна одного з рівнянь системи сумою з іншим рівнянням
тієї ж системи, помножимо на деяке число;
3) видалення з системи рівнянь тотожностей.
З допомогою перетворення 2) можна виключити деяке невідоме із усіх рівнянь системи, крім одного.           

Виберемо для цього рівняння з номером 1), що містить невідоме:
 Це рівняння будемо називати ведучим, а - ведучим невідомим. Для виключення ведучого невідомого з рівняння з номером
додамо до нього ведуче рівняння, помножене на деяке число. Щоб виключити невідоме, прирівняємо до нуля коефіцієнт при, тобто Тоді рівняння матиме вигляд
одержимо систему рівнянь, в якій невідоме міститиметься тільки в -му рівнянні, а в інших рівняннях невідомого не буде. Таким самим способом, приймаючи в ролі ведучого інше рівняння, можна з усієї решти рівнянь виключити ведуче вибране невідоме. Продовжуючи цей процес доти, поки кожне рівняння побуде ведучим тільки один раз, прийдемо до системи рівнянь вигляду
У ролі ведучого послідовно бралися рівняння 1-ше та -те, а в ролі ведучого невідомого бралися послідовно. Якщо при цьому жодне рівняння не перетворювалося в тотожність, то зрозуміло, вони далі в процесі перетворення не беруть участі і тому виключаються з системи.

У цьому випадку в системі кількість рівнянь буде меншою, ніж.
Якщо описаний процес проводився в іншому порядку, то після його закінчення члени в рівняннях завжди можна переставити так, щоб система набрала вигляду
У випадку, коли в процесі розв’язування системи рівнянь де-небудь ліва частина якогось рівняння перетворюється в нуль, а права-не дорівнює нулю, то це означає, що система несумісна і тому обчислення треба припинити.
У рівнянні невідомі називаються базисними, а решта змінних - небазисними. Базисний розв’язок складається з базисних змінних і нулів, причому нулям відповідають небазисні змінні. Якщо в базисі є стільки змінних, скільки рівнянь, то такий базис називається невиродженим. Якщо базисних змінних менше, ніж, то такий базис називається виродженим.

 

 

41. Назвіть умови оптимальності транспортної задачі.

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

Теорема (умова існування розв’язку транспортної задачі): необхідною і достатньою умовою існування розв’язку транспортної задачі є її збалансованість: .

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

Друга умова: Сумарний обсяг продукції, який ввезений кожному j-му споживачу має дорівнювати його потребам.

Третя умова: Сумарна вартість перевезень повинна бути мінімальна.

Як обчислюють потенціали?

Алгоритм методу потенціалів складається з таких етапів:

· Визначення типу транспортної задачі (відкрита чи закрита). За необхідності слід звести задачу до закритого типу.

· Побудова першого опорного плану транспортної задачі одним з відомих методів.

· Перевірка опорного плану задачі на виродженість. За необхідності вводять нульові постачання.

· Перевірка плану транспортної задачі на оптимальність.

1. Визначення потенціалів для кожного рядка і стовпчика таблиці транспортної задачі. Потенціали опорного плану визначають із системи рівнянь ui + vj = cij, які записують для всіх заповнених клітинок транспортної таблиці, кількість яких дорівнює , а кількість невідомих —  . Кількість рівнянь на одне менша, ніж невідомих, тому система є невизначеною, і одному з потенціалів надають нульове значення. Після цього всі інші потенціали розраховують однозначно.

2. Перевірка виконання умови оптимальності для пустих клітин. За допомогою розрахованих потенціалів перевіряють умову оптимальності ui + vj ≤ cij для незаповнених клітинок таблиці. Якщо хоча б для однієї клітини ця умова не виконується, тобто ui + vj > cij, то поточний план є неоптимальним, і від нього необхідно перейти до нового опорного плану.

3. Вибір змінної для введення в базис на наступному кроці. Загальне правило переходу від одного опорного плану до іншого полягає в тому, що з попереднього базису виводять певну змінну (вектор), а на її місце вводять іншу змінну (вектор), яка має покращити значення цільової функції. Аналогічна операція здійснюється і в алгоритмі методу потенціалів.

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

 

4. Побудова циклу і перехід до наступного опорного плану. Вибрана порожня клітина разом з іншими заповненими становить , отже, з цих клітин обов’язково утвориться цикл (теореми та наслідок § 5.2). У межах даного циклу здійснюють перерахування, які приводять до перерозподілу постачань продукції. Кожній вершині циклу приписують певний знак, причому вільній клітинці — знак «+», а всім іншим — за черговістю знаки «–» та «+». У клітинках зі знаком «–» вибирають значення q  і переносять його у порожню клітинку. Одночасно це число додають до відповідних чисел, які містяться в клітинках зі знаком «+», та віднімають від чисел, що позначені знаком «–». Якщо значенню q відповідає кілька однакових перевезень, то при відніманні залишаємо у відповідних клітинках нульові величини перевезень у такій кількості, що дає змогу зберегти невиродженість опорного плану.

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

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

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

 5. Перевірка умови оптимальності наступного опорного плану. Якщо умова оптимальності виконується — маємо оптимальний план транспортної задачі, інакше необхідно перейти до наступного опорного плану (тобто повернутися до пункту 3 даного алгоритму).

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

Як визначити, що виробництво продукції є рентабельним (нерентабельним)?

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

Ліва частина кожного обмеження двоїстої задачі є вартістю відповідних ресурсів, які використовують для виробництва одиниці j -ї продукції. Якщо ця величина перевищує ціну одиниці продукції (с_j), то виготовляти таку продукцію невигідно, вона нерентабельна і в оптимальному плані прямої задачі відповідна їй змінна х_j = 0. Якщо ж загальна оцінка всіх ресурсів дорівнює ціні одиниці продукції, то виготовляти таку продукцію доцільно, вона рентабельна і в оптимальному плані прямої задачі відповідна змінна х_j > 0.

6. Що означає «правильне відтинання»? Допустимо, що необхідно розв’язувати задачу лінійного програмування, всі або частина змінних якої мають бути цілочисловими. Можливо, якщо розв’язувати задачу, не враховуючи умову цілочисловості, випадково одразу буде отримано потрібний розв’язок. Однак така ситуація малоймовірна. Переваж­но розв’язок не задовольнятиме умову цілочисловості. Тоді накладають додаткове обмеження, яке не виконується для отриманого плану задачі, проте задовольняє будь-який цілочисловий розв’язок. Таке додаткове обмеження називають правильним відтинанням. Система лінійних обмежень задачі доповнюється новою умовою і далі розв’язується отримана задача лінійного програмування. Якщо її розв’язок знову не задовольняє умови цілочисловості, то будується нове лінійне обмеження, що відтинає отриманий розв’язок, не зачіпаючи цілочислових планів. Процес приєднання додаткових обмежень повторюють доти, доки не буде знайдено цілочислового оптимального плану, або доведено, що його не існує.