МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ Чернігівський державний технологічний університет Кафедра вищої математики Контрольна робота з дисципліни: Математичне програмування
Варіант 06
Чернігів 2009
Зміст
Завдання №1
Завдання №2
Завдання №3
Завдання №4
Завдання №5
Список використаних джерел
Завдання №1 Звести до канонічної форми задачу лінійного програмування:
Дана задача лінійного програмування задана в симетричній формі запису: умови, при яких функція F буде максимальною, задані у вигляді нерівностей. Для того, щоб отримати канонічну форму задачі лінійного програмування необхідно нерівності перетворити у рівності, використовуючи теорему, за якою нерівність
еквівалентна рівнянню
і нерівності
а нерівність вигляду
еквівалентна рівнянню
, в якому
Враховуючи наведене вище дану задачу запишемо у наступній канонічній формі:
Завдання №2 Визначити оптимальний план задачі лінійного програмування графічним методом (знайти максимум і мінімум функції):
Для задач з двома змінними можна використовувати графічний спосіб розв’язку задач лінійного програмування. Побудуємо область допустимих розв’язків системи лінійних нерівностей. Для цього будуємо відповідні даним нерівностям граничні прямі:
Потім знаходимо напівплощини, в яких виконуються задані нерівності (рисунок1).
Рисунок1– Графічне визначення максимального і мінімального значення функції
Область допустимих рішень визначається як загальна частина напівплощин, відповідних даним нерівностям, які при цьому знаходяться в першій четвертині, тобто обмежуються прямими і . З малюнку 1 видно, що функція не має рішення, оскільки напівплощина, утворена прямими
не співпадає з площиною, утвореною обмеженнями
.
Завдання №3 Побудувати двоїсту задачу. Симплексним методом знайти оптимальний план початкової задачі. Використовуючи першу теорему двоїстості, визначити план другої задачі.
Для перетворення нерівностей в рівності вводимо змінні одиничні матриці х3, х4 і х5. Для розв’язку задачі симплексним методом необхідно мати три одиничних матриці при невід’ємних правих частинах рівнянь. Для отримання одиничної матриці в першій і третій нерівностях вводимо введемо штучні змінну х6 і х7 та отримаємо одиничні матриці А6 і А7. Де
і
В результаті наведених перетворень отримаємо наступну задачу:
У виразі функції величину М вважаємо достатньо великим додатнім числом, оскільки задача розв’язується на знаходження мінімального значення функції.
Запишемо задачу у векторній формі:
де
В якості базису вибираємо одиничні вектори А6, А4, А7. Вільні невідомі прирівнюємо нулю . В результаті отримаємо початковий опорний план розширеної задачі
,
якому відповідає розкладення
Для перевірки початкового опорного плану складаємо першу симплексну таблицю (таблиця1) і підраховуємо значення функції і оцінок Маємо:
тобто оскільки М попередньо не фіксовано, то оцінки є лінійними функціями величини М, причому функція складається з двох доданків, одне з яких залежить від М, інше не залежить. ............
