Розв’язання лінійних задач методами лінійного програмування (стр. 1 из 6)
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
Чернігівський державний технологічний університет
Кафедра вищої математики
Контрольна робота
з дисципліни: Математичне програмування
Варіант 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) і підраховуємо значення функції
і оцінок 
Маємо: 
тобто оскільки М попередньо не фіксовано, то оцінки
є лінійними функціями величини М, причому функція складається з двох доданків, одне з яких залежить від М, інше не залежить. Для зручності розрахунків в (F-C) рядок запишемо доданок, незалежний від М, а в (М) рядок – тільки коефіцієнти при М, які і дозволяють порівняти оцінки між собою. Для векторів базису оцінки дорівнюють нулю.Таблиця1– Перша симплексна таблиця
| Базис | С базису | А0 |  |  |  |  |  |  |  |
| х1 | х2 | х3 | х4 | х5 | х6 | х7 | |||
| х6 | М | 8 | 1 |  | -1 | 0 | 0 | 1 | 0 |
| х4 | 0 | 20 | 3 | 4 | 0 | 1 | 0 | 0 | 0 |
| х7 | М | 6 | 3 | 1 | 0 | 0 | -1 | 0 | 1 |
| F-C | – | 0 | -5 | -2 | 0 | 0 | 0 | 0 | 0 |
| М | – | 14 | 4 | 4 | -1 | 0 | -1 | 0 | 0 |
В (М) рядку є додатні оцінки, тому опорний план Х0 не є оптимальним і його можна покращити, включивши в базис вектор, якому відповідає
. Оскільки у нас максимальне значення 4 належить двом векторам, то в базис включаємо вектор, якому відповідає мінімальне Сj. Розв’язувальним рядком вибирається той, в якому найменше відношення 
Серед коефіцієнтів розкладання векторів А1 і А2 по базису є додатні, тому хоча б один з векторів існує.. Знайдемо ці значення: 
; 
Таким чином підтвердилося, що розв’язувальним стовпчиком буде другий, і визначилося, що розв’язувальним рядком буде перший. Тобто розв’язувальний елемент – число 3. Тоді вектор А2 включаємо в базис, а вектор А6 виключаємо з нього.
Складаємо другу симплексну таблицю (таблиця2). При цьому елементи першого (розв’язувального) рядка ділимо на 3. Елементи інших рядків визначаємо використовуючи формули повного виключення Йордана-Гауса.
Таблиця2– Друга симплексна таблиця
| Базис | С базису | А0 | | | | | | | |
| х1 | х2 | х3 | х4 | х5 | х6 | х7 | |||
| х2 | 2 | 2,67 | 0,33 | 1 | -0,33 | 0 | 0 | 0,33 | 0 |
| х4 | 0 | 9,33 | 1,67 | 0 | 1,33 | 1 | 0 | -1,33 | 0 |
| х7 | М | 3,33 |  | 0 | 0,33 | 0 | -1 | -0,33 | 1 |
| F-C | – | 5,33 | -4,33 | 0 | -0,67 | 0 | 0 | 0,67 | 0 |
| М | – | 3,33 | 2,67 | 0 | 0,33 | 0 | -1 | -1,33 | 0 |
В (М) рядку є додатні оцінки, тому план, зображений в таблиці2 не є оптимальним і його можна покращити, включивши в базис вектор, якому відповідає
. Тобто за розв’язувальний стовпчик вибираємо перший. Мінімальне відношення