КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Симплекс-метод розв’язку задачі ЛП
Лекція 2 Тема 1. Лінійне програмування (8 г. – 4 лекції) (2 г.) 2.2.2 Симплекс-метод розв’язку задачі ЛП 2.2.3 Метод штучного базису 2.2.4 Модифікований симплекс-метод(на самопідготовку)* Сенс симплекс-методу полягає в переході від одного базисного рішення до іншого, при якому значення цільової функції зростає (за умови, що дана задача має оптимальний план і кожний її опорний план є невиродженим). Такий перехід можливий за умови відомості будь-якого опорного плану. Запишемо умову задачі: за умов (). Тут , та () – задані константи (та ). Або у векторній формі: за умов (15) , (16) (), де (17) ,,,, …,,. Так як , то за визначенням опорного плану є опорним планом даної задачі (останні компонент вектора дорівнюють нулю). Даний план визначається системою одиничних векторів , , …, , які створюють базис вимірного простору. Тому кожен з векторів, а також вектор можуть бути представлені у вигляді лінійної комбінації векторів даного базису. Нехай (). Положимо (); (). Так як вектори , , …, - одиничні, то і , а . Теорема 5. (Ознака оптимальності опорного плану). Опорний план задачі (15)-(17) є оптимальним, якщо для . Теорема 6. Якщодля деякого і серед чисел нема позитивних , то цільова функція (15) задачі (15)-(17) необмежена на множині її планів. Теорема 7. Якщо опорний план задачі (15)-(17) не вироджений та , але серед чисел є позитивні (не всі ), то існує опорний план такий, що . Сформульовані теореми дозволяють перевірити наявний план на оптимальність та виявити доцільність переходу до нового опорного плану. Приклад 3 [3]. Для виготовлення різних типів виробів А, В та С підприємство використовує три різних типи сировини. Норми витрат сировини на виробництво одного виробу кожного виду, ціна одного виробу А, В та С, а також загальна кількість сировини кожного виду, яке може бути використано підприємством, наведені у табл.:
Скласти план виробництва, при якому загальна ціна всієї виробленої продукції є максимальною. Розв’язок. 1. Складаємо математичну модель задачі.
(18) . 2. Запишемо задачу (15) у канонічній формі.
(19) . Додаткові змінні за економічним смислом означають кількість сировини того, чи іншого типу, що не використовується при даному плані виробництва. Наприклад, – кількість сировини 1-го виду, що не використовується при виробництві. Перетворену систему рівнянь запишемо у векторній формі: де ; ; ; ; ; ; . Оскільки серед векторів є три одиничних, то для даної задачі можна безпосередньо записати опорний план: 3. Складаємо симплекс-таблицю для 1-ї ітерації. 3.1 Розраховуємо значення , де : ,, 3.2 Розраховуємо , . ; ; 3.3 Розраховуємо оцінки . ; ; . Для векторів базису . Так як для всіх змінних , то план не є оптимальним. 4. Вибираємо роздільний стовпчик за правилом для визначення змінної, яку буде включено до базису. . Це означає, якщо включити в план випуску продукцію виду С, то загальна ціна на продукцію збільшиться на 16 ум.од. Таким чином, до базису вводимо вектор . 5. Вибираємо роздільний рядок для визначення базисної змінної, яку буде виключено з базису. Для цього находимо для . Тобто . Тобто, роздільним рядком є другий. Таким чином, з базису виключається вектор , а вектор вводиться до базису. 6. Переписуємо симплекс-таблицю і перераховуємо її елементи наступним чином: 6.1 Елементи роздільного рядка отримуємо з елементів попередньої таблиці шляхом ділення їх на роздільний елемент. При цьому у стовпчику записується коефіцієнт , що стоїть у стовпчику вектору, який вводиться у базис. 6.2 Заповнюємо елементи стовпчиків для векторів, що входять до нового базису. В цих стовпчиках на перетині рядка та стовпчика однойменних векторів проставляємо одиниці, а всі інші заповнюємо нулями. 6.3 Всі інші елементи обчислюємо за правилом прямокутника (або за рекурентними формулами).
На третій ітерації отримуємо оптимальний план при якому ум.од. Аналіз розв’язку дає можливість зробити наступні висновки: оптимальний план випуску продукції передбачає випуск 8 виробів В та 20 виробів С. При цьому повністю використовується сировина 1-го та 2-го видів і залишається невикористаним 96 кг сировини 3-го виду.
Дата добавления: 2014-01-13; Просмотров: 686; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |