РОСІЙСЬКА ФЕДЕРАЦІЯ
МІНІСТЕРСТВО ОСВІТИ І НАУКИ
МІНІСТЕРСТВО ОСВІТИ
ДЕРЖАВНЕ Освітні установи
ВИЩОЇ НАУКИ
В«ТЮМЕНСЬКИЙ ДЕРЖАВНИЙ УНІВЕРСИТЕТ В»
ІНСТИТУТ ДИСТАНЦІЙНОГО ОСВІТИ
СПЕЦІАЛЬНІСТЬ В«Менеджмент організацій В»
До Про М Т Р О Л Ь Н А Я Р А Б Про Т А
По предмету: Економіко-математичний практикум
В
Виконав:
Студент 2 курсу
4 семестр
Рахімова Лідія Рустамовна
Ташкент, 2009
Завдання № 1
Умовно стандартна задача лінійного програмування
Необхідно виконати в зазначеному порядку наступні завдання.
1. Знайти оптимальний план прямої задачі:
а) графічним методом;
б) симплекс-методом (для побудови вихідного опорного плану рекомендується використовувати метод штучного базису).
2. Побудувати двоїсту задачу.
3. Знайти оптимальний план двоїстої завдання з графічного рішення прямої, використовуючи умови доповнює нежорсткої.
4. Знайти оптимальний план двоїстої завдання по першій теоремі подвійності, використовуючи остаточну симплекс-таблицю, отриману при вирішенні прямої задачі (див. п. 1б). Перевірити твердження В«значення цільових функцій пари двоїстих завдань на своїх оптимальних рішеннях збігаються В».
5. Двоїсту завдання вирішити симплекс-методом, потім, використовуючи остаточну симплекс-таблицю двоїстої завдання знайти оптимальний план прямої задачі по першій теоремі подвійності. Порівняти результат з результатом, який був отриманий графічним методом (див. п. 1а).
6. Знайти оптимальне цілочисельне рішення:
а) графічним методом;
б) Методом Гоморі.
Порівняти значення функцій цілочисельного і нецілочисельне рішень
4
В
Рішення задачі 1
1. Знайдемо оптимальний план вирішення графічним методом:
;
В
Побудуємо на координатній площині Ох 1 х 2 граничні прямі області допустимих рішень (номери прямих відповідають їх порядковому номеру в системі):
В
Область допустимих рішень визначається багатокутником ОАВС D (див. графік 1).
Для ліній рівня х 1 - 3 х 2 = h ( H - const) будуємо нормальний вектор. Перпендикулярно нормальному вектору побудуємо одну з ліній рівня (на рис. 1 вона проходить через початок координат) Оскільки завдання на мінімум, то переміщаємо лінію рівня в напрямку вектора до опорної прямої. У даному випадку опорної прямої є пряма, що проходить через точку перетину граничних прямих L 3 і L 4 , тобто через крапку. Для визначення координат точки P вирішуємо систему рівнянь
.
Отримуємо х 1 = 5,3, х 2 = 0,6. Це і буде оптимальним рішенням даної завдання, якому відповідає мінімальне значення цільової функції Z min = 3,5
В
10
br/>
6
p>
4
br/>
P
p>
2
br/>
В
В В В
(4)
В В
(
3) В В В В В В В
(2)
В
Графік № 1
1б) Перейдемо до розширеної задачі:
В
Дана розширена задача має початкове опорне рішення з базисом. Обчислюємо оцінки векторів умов по базису опорного рішення і значення цільової функції на опорному рішенні:
В
Розрахунки...