Главная Учебники - Разные Лекции (разные) - часть 33
Міністерство освіти і науки України
Черкаський
національний
університет імені Богдана Хмельницького
Ф
акультет інформаційних технологій і
біомедичної кібернетики
РОЗРАХУНКОВА РОБОТА
з курсу „Математичне моделювання економічних систем”
студента 4-го курсу спеціальності «інтелектуальні системи прийняття рішень» Валяєва Олександра В’ячеславовича Черкаси – 2006 р.
Зміст Завдання 1. Задача лінійного програмування Завдання 2. Задача цілочислового програмування Завдання 3. Задача дробово-лінійного програмування Завдання 4. Транспортна задача Завдання 5. Задача квадратичного програмування Список використаної літератури
Завдання 1
. Задача лінійного програмування
Для заданої задачі лінійного програмування побудувати двоїсту задачу. Знайти розв’язок прямої задачі геометричним методом і симплекс-методом. Знайти розв’язок двоїстої задачі, використовуючи результати розв’язування прямої задачі симплекс-методом: 3. Розв
′язання г
еометричним методом
Побудуємо прямі, рівняння яких одержуються внаслідок заміни в обмеженнях знаків нерівностей на знаки рівностей. Визначимо півплощини, що задовольняють нашим нерівностям. Умовам невід’ємності Заштрихуємо спільну частину площини, що задовольняє всім нерівностям. Побудуємо вектор нормалі Максимального значення функція набуває в точці перетину прямих I
та II
. Знайдемо координати цієї точки. Приведемо систему до канонічного вигляду Відповідь:
Розв
′язання
симплекс-методом
Приведемо систему рівнянь до канонічного вигляду Цільова функція Побудуємо симплекс-таблицю Отриманий план не оптимальний Обраний ключовий елемент (3,2) Отриманий план не оптимальний Обраний ключовий елемент (2,5) Отриманий план не оптимальний Обраний ключовий елемент (1,1) План оптимальний Розв’язок
: X*
( Розв’язок двоїстої задач
Побудуємо двоїсту функцію 3. Система обмежень Скористаємось теоремою Якщо задача лінійного програмування в канонічній формі (7)-(9) має оптимальний план Розв’язок:
Fmin
*
= 9,6;
Завдання 2. Задача цілочислового програмування
Для задачі із завдання 1, як для задачі цілочислового програмування, знайти розв’язки геометричним методом і методом Гоморі. Розв
′язання
геометричним методом
Відповідь:
Розв
′язання
методом Гомор
і
Наведемо останню симплекс-таблицю Побудуємо нерівність Гоморі за першим аргументом. Обраний розв’язковий елемент (4,4) Отриманий план являється оптимальним і цілочисельним. Розв’язок
: X*
(1,7) Fmax
*
=23; Відповідь: цілочисельною точкою максимуму даної задачі є точка (1,7)
Завдання 3. Задача дробово-лінійного програмування
Для задачі дробово-лінійного програмування знайти розв’язки геометричним методом і симплекс-методом: Розв
′язання
геометричним методом
Визначимо, в яку сторону потрібно обертати пряму навколо початку координат, щоб значення цільової функції збільшувалось. Таким чином ми визначимо яка з крайніх точок є точкою максимуму. f
(1;0) = 2/3 f
(0;1) = 3/7 Тобто при крутінні прямої проти годинникової стрілки значення цільової функції зменшується. Використаємо результати обчислень і геометричних побудов з попереднього завдання. З графіка очевидно, що розв’язок лежить на перетині двох прямих. Для визначення точки перетину прямої І
та ІІ
розв′яжемо систему з двох рівнянь. Відповідь: функція набуває максимального значення при x
1
=6/5, x
2
=36/5. Розв
′язання симплекс-методом
Перейдемо від задачі дробово-лінійного програмування до задачі лінійного програмування. Вводим заміну: Вводим ще одну заміну: Після замін наша задача має такий вигляд: Приведемо її до канонічної форми і доповнимо її базисами: Повернемось до заміни: x1
=0 x2
=6 Завдання 4. Транспортна задача
Для заданих транспортних задач скласти математичну модель і розв’язати їх методом потенціалів, використавши для визначення початкового плану метод мінімального елемента або північно-західного кута. 1. Запаси деякого однорідного продукту знаходяться на трьох пунктах постачання (базах) A1, A2, A3 і цей продукт потрiбно доставити в три пункти споживання (призначення) B1, B2, B3. Задача полягає в тому, щоб визначити, яку кiлькiсть продукту потрiбно перевезти з кожного пункту постачання (бази) до кожного пункту споживання (призначення) так, щоб забезпечити вивезення всього наявного продукту з пунктів постачання, задовільнити повністю потреби кожного пункту споживання і при цьому сумарна вартiсть перевезень була б мiнiмальною (зворотні перевезення виключаються). Вартість перевезеньс
ij
(у грн.) з бази А
i
до пункту призначення Bj
вказана в таблиці, де також наведені дані про запаси ai
(у тонанх) продукту і його потреби (у тонах) bj
. Для даної транспортної задачі не виконується умова балансу j
³ 0, 1£i£4, 1£j£3. 840 840 За методом північно-західного кута знайдемо опорний план 3 260 5 10 7 270 6 9 180 4 180 11 8 90 10 210 300 0 0 0 90 90 840 840 За методом північно-західного кута опорний план має вигляд: F=3*260+5*10+9*180+8*90+10*210+0*90=5270 Перевіримо чи буде він оптимальним. Знаходимо потенціали для пунктів постачання Для тих клітинок, де Знаходимо з системи: Для тих клітинок, де Оскільки 270 180 300 90 840 840 В результаті перерахунку отримаємо 3 260 5 10 7 270 6 9 4 180 180 11 8 270 10 30 300 0 0 0 90 90 840 840 Наступний опорний план F=3*260+5*10+9*180+8*90+10*210+0*90=4010 Для тих клітинок, де Знаходимо з системи: Для тих клітинок, де Отже план
Завдання 5. Задача квадратичного програмування
Розв’язати задачу квадратичного програмування геометричним методом та аналітичним методом, використовуючи функцію Лагранжа і теорему Куна-Таккера: Розв’язання графічним методом
Графік кола має центр в точці (-1, 4) X
*
(0 , 4);
F
*
(
X
*
)=-16
Розв’язання аналітичним методом
Складемо функцію Лагранжа: Система обмежень набуде вигляду: Перенесемо вільні члени вправо, і при необхідності домножимо на -1 Зведемо систему обмежень до канонічного вигляду Введемо додаткові змінні для утворення штучного базису Розв’яжемо задачу лінійного програмування на знаходження мінімуму. Введемо додаткові прямі обмеження на змінні. Векториз коефіцієнтів при невідомих: Розв’язуємо отриману задачу звичайним симплекс-методом Обраний розв’язковий елемент (5,2) Обраний розв’язковий елемент (2,4) Обраний розв’язковий елемент (1,5)
|