Реферат: Математичне моделювання економічних систем
Міністерство освіти і науки України
Черкаський національний університет імені Богдана Хмельницького
Ф акультет інформаційних технологій і
біомедичної кібернетики
РОЗРАХУНКОВА РОБОТА
з курсу „Математичне моделювання економічних систем”
студента 4-го курсу спеціальності
«інтелектуальні системи прийняття рішень»
Валяєва Олександра В’ячеславовича
Черкаси – 2006 р.
Зміст
Завдання 1. Задача лінійного програмування
Завдання 2. Задача цілочислового програмування
Завдання 3. Задача дробово-лінійного програмування
Завдання 4. Транспортна задача
Завдання 5. Задача квадратичного програмування
Список використаної літератури
Завдання 1 . Задача лінійного програмування
Для заданої задачі лінійного програмування побудувати двоїсту задачу. Знайти розв’язок прямої задачі геометричним методом і симплекс-методом. Знайти розв’язок двоїстої задачі, використовуючи результати розв’язування прямої задачі симплекс-методом:
3. ,
Розв ′язання г еометричним методом
Побудуємо прямі, рівняння яких одержуються внаслідок заміни в обмеженнях знаків нерівностей на знаки рівностей.
| I: | 6 | |
| 9 |
| II: | -6 | |
| 6 |
| III: | 4 | |
| 4 |
Визначимо півплощини, що задовольняють нашим нерівностям.
Умовам невід’ємності та відповідає перша чверть.
Заштрихуємо спільну частину площини, що задовольняє всім нерівностям.
Побудуємо вектор нормалі .
Максимального значення функція набуває в точці перетину прямих I та II .
Знайдемо координати цієї точки.
Приведемо систему до канонічного вигляду
|
|
|
Відповідь:
Розв ′язання симплекс-методом
Приведемо систему рівнянь до канонічного вигляду
x(0) =(0,0,18,6,0,4)
Цільова функція
Побудуємо симплекс-таблицю
| I | базис | Cб | P0 | 2 | 3 | -M | |
| P1 | P2 | P3 | P4 | P5 | P6 | ||
| 1 | P3 | 18 | 3 | 2 | 1 | ||
| 2 | P4 | 6 | -1 | 1 | 1 | ||
| 3 | P6 | -M | 4 | 1 | 1 | -1 | 1 |
| 4 | -2 | -3 | |||||
| 5 | -4 | -1 | -1 | 1 |
Отриманий план не оптимальний
Обраний ключовий елемент (3,2)
| I | базис | Cб | P0 | 2 | 3 | -M | |
| P1 | P2 | P3 | P4 | P5 | P6 | ||
| 1 | P3 | 10 | 1 | 1 | 2 | -2 | |
| 2 | P4 | 2 | -2 | 1 | 1 | -1 | |
| 3 | P2 | 3 | 4 | 1 | 1 | -1 | -1 |
| 4 | 12 | 1 | -3 | -3 | |||
| 5 | -1 |
Отриманий план не оптимальний
Обраний ключовий елемент (2,5)
| I | базис | Cб | P0 | 2 | 3 | -M |
| P1 | P2 | P3 | P4 | P5 | P6 | |
| 1 | P3 | 6 | 5 | 1 | -2 | |
| 2 | P5 | 2 | -2 | 1 | 1 | -1 |
| 3 | P2 | 3 | 6 | -1 | 1 | 1 |
| 4 | 18 | -5 | 3 | |||
| 5 | -1 |
Отриманий план не оптимальний
Обраний ключовий елемент (1,1)
| I | базис | Cб | P0 | 2 | 3 | -M |
| P1 | P2 | P3 | P4 | P5 | P6 | |
| 1 | P1 | 2 | 6/5 | 1 | 1/5 | -2/5 |
| 2 | P5 | 22/5 | 2/5 | 1/5 | 1 | -1 |
| 3 | P2 | 3 | 36/5 | 1 | 1/5 | 3/5 |
| 4 | 24 | 1 | 1 | |||
| 5 | 1 |
План оптимальний
Розв’язок: X* (,) F* =24;
Розв’язок двоїстої задач
Побудуємо двоїсту функцію
3. ,
Система обмежень
Скористаємось теоремою
Якщо задача лінійного програмування в канонічній формі (7)-(9) має оптимальний план , то є оптимальним планом двоїстої задачі
,,
Розв’язок:
Fmin* = 9,6;
Завдання 2. Задача цілочислового програмування
Для задачі із завдання 1, як для задачі цілочислового програмування, знайти розв’язки геометричним методом і методом Гоморі.
Розв ′язання геометричним методом
,
Відповідь:
Розв ′язання методом Гомор і
Наведемо останню симплекс-таблицю
| I | базис | Cб | P0 | 2 | 3 | -M |
| P1 | P2 | P3 | P4 | P5 | P6 | |
| 1 | P1 | 2 | 6/5 | 1 | 1/5 | -2/5 |
| 2 | P5 | 22/5 | 2/5 | 1/5 | 1 | -1 |
| 3 | P2 | 3 | 36/5 | 1 | 1/5 | 3/5 |
| 4 | 24 | 1 | 1 | |||
| 5 | 1 |
Побудуємо нерівність Гоморі за першим аргументом.
| I | базис | Cб | P0 | 2 | 3 | |
| P1 | P2 | P3 | P4 | P5 | P7 | |
| 1 | P1 | 2 | 6/5 | 1 | 1/5 | -2/5 |
| 2 | P5 | 22/5 | 2/5 | 1/5 | 1 | |
| 3 | P2 | 3 | 36/5 | 1 | 1/5 | 3/5 |
| 4 | P7 | -1/5 | -1/5 | -3/5 | 1 | |
| 5 | 24 | 1 | 1 |
Обраний розв’язковий елемент (4,4)
| I | базис | Cб | P0 | 2 | 3 |
| P1 | P2 | P3 | P4 | P5 | P7 |
| 1 | P1 | 2 | 1 | 1 | -1 |
| 2 | P5 | 4 | 11/5 | 1 | |
| 3 | P2 | 3 | 7 | 1 | |
| 4 | P4 | 2 | 1 | 3 | 1 |
| 5 | 14 | 2 |
Отриманий план являється оптимальним і цілочисельним.
Розв’язок: 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 .
| Пункти | Пункти споживання | Запаси | ||
| постачання | B1 | B2 | B3 | |
| A1 | 3 | 5 | 7 | 270 |
| A2 | 6 | 9 | 4 | 180 |
| A3 | 11 | 8 | 10 | 300 |
| Потреби | 260 | 280 | 300 |
Для даної транспортної задачі не виконується умова балансу , тому введемо додатковий пункт постачання з запасами 840-750=90 і тарифами С4s =0 (i=1,2,3). Тоді одержимо замкнену транспортну задачу, яка має розв’язок. Її математична модель має вигляд:
хi,
j ³ 0, 1£i£4, 1£j£3.
| Пункти | Пункти споживання | Запаси | ||
| постачання | B1 | B2 | B3 | |
| A1 | 3 | 5 | 7 | 270 |
| A2 | 6 | 9 | 4 | 180 |
| A3 | 11 | 8 | 10 | 300 |
| A4 | 90 | |||
| Потреби | 260 | 280 | 300 | 840 840 |
За методом північно-західного кута знайдемо опорний план
| Пункти | Пункти споживання | Запаси | ||
| постачання | B1 | B2 | B3 | |
| A1 | 3 260 | 5 10 | 7 | 270 |
| A2 | 6 | 9 180 | 4 | 180 |
| A3 | 11 | 8 90 | 10 210 | 300 |
| A4 | 90 | 90 | ||
| Потреби | 260 | 280 | 300 | 840 840 |
За методом північно-західного кута опорний план має вигляд:
.
F=3*260+5*10+9*180+8*90+10*210+0*90=5270
Перевіримо чи буде він оптимальним.
Знаходимо потенціали для пунктів постачання
Для тих клітинок, де, розв’яжемо систему рівнянь
Знаходимо з системи:
.
Для тих клітинок, де, знайдемо числа
Оскільки , то план Х1 не є оптимальним. Будуємо цикл перерахунку
| Пункти | Пункти споживання | Запаси | ||||
| постачання | B1 | B2 | B3 | |||
| A1 | 3 | 5 | 7 | 270 | ||
| 260 | 10 | |||||
| A2 | 6 | 1 | 9 | 4 | 7 | 180 |
| - | 180 | + | ||||
| A3 | 11 | -5 | 8 | 10 | 300 | |
| + | 90 | - | 210 | |||
| A4 | -4 | -2 | 90 | |||
| 90 | ||||||
| Потреби | 260 | 280 | 300 | 840 840 |
В результаті перерахунку отримаємо
| Пункти | Пункти споживання | Запаси | ||
| постачання | B1 | B2 | B3 | |
| A1 | 3 260 | 5 10 | 7 | 270 |
| A2 | 6 | 9 | 4 180 | 180 |
| A3 | 11 | 8 270 | 10 30 | 300 |
| A4 | 90 | 90 | ||
| Потреби | 260 | 280 | 300 | 840 840 |
Наступний опорний план
F=3*260+5*10+9*180+8*90+10*210+0*90=4010
Для тих клітинок, де, розв’яжемо систему рівнянь
Знаходимо з системи:
.
Для тих клітинок, де, знайдемо числа
Отже план є оптимальним F =4010
Завдання 5. Задача квадратичного програмування
Розв’язати задачу квадратичного програмування геометричним методом та аналітичним методом, використовуючи функцію Лагранжа і теорему Куна-Таккера:
Розв’язання графічним методом
,
Графік кола має центр в точці (-1, 4)
X * (0, 4); F * ( X * )=-16
Розв’язання аналітичним методом
,
Складемо функцію Лагранжа:
Система обмежень набуде вигляду:
Перенесемо вільні члени вправо, і при необхідності домножимо на -1
Зведемо систему обмежень до канонічного вигляду
Введемо додаткові змінні для утворення штучного базису
Розв’яжемо задачу лінійного програмування на знаходження мінімуму.
Введемо додаткові прямі обмеження на змінні.
,
Векториз коефіцієнтів при невідомих:
Розв’язуємо отриману задачу звичайним симплекс-методом
| I | базис | Cб | P0 | M | M | ||||||
| Px1 | Px2 | Py1 | Py2 | Py3 | Pu1 | Pu2 | Pv1 | Pv2 | Pv3 | Pz1 | Pz2 |
| 1 | Pz1 | M | 2 | -2 | -3 | 1 | 1 | -1 | 1 | ||
| 2 | Pu2 | 8 | 2 | 2 | 1 | -1 | 1 | ||||
| 3 | Pv1 | 18 | -3 | -2 | 1 | ||||||
| 4 | Pv2 | 6 | -1 | 1 | 1 | ||||||
| 5 | Pz2 | M | 4 | 1 | 1 | -1 | 1 | ||||
| 5 | -M | M | -3M | M | M | -M | -M |
Обраний розв’язковий елемент (5,2)
| I | базис | Cб | P0 | M | M | ||||||
| Px1 | Px2 | Py1 | Py2 | Py3 | Pu1 | Pu2 | Pv1 | Pv2 | Pv3 | Pz1 | Pz2 |
| 1 | Pz1 | M | 2 | -2 | -3 | 1 | 1 | -1 | 1 | ||
| 2 | Pu2 | -2 | 2 | 1 | -1 | 1 | 2 | ||||
| 3 | Pv1 | 26 | -1 | 1 | -2 | ||||||
| 4 | Pv2 | 2 | -2 | 1 | 1 | ||||||
| 5 | Px2 | 4 | 1 | 1 | -1 | 1 | |||||
| 5 | 2М | -2М | -3М | М | M | -М |
Обраний розв’язковий елемент (2,4)
| I | базис | Cб | P0 | M | M | ||||||
| Px1 | Px2 | Py1 | Py2 | Py3 | Pu1 | Pu2 | Pv1 | Pv2 | Pv3 | Pz1 | Pz2 |
| 1 | Pz1 | M | 2 | -5 | 2 | -1 | -1 | -2 | 1 | ||
| 2 | Py2 | -2 | 2 | 1 | -1 | 1 | 2 | ||||
| 3 | Pv1 | 26 | -1 | 1 | -2 | ||||||
| 4 | Pv2 | 2 | -2 | 1 | 1 | ||||||
| 5 | Px2 | 4 | 1 | 1 | -1 | ||||||
| 5 | 2M | -5M | 2M | -M | -M | -2M |
Обраний розв’язковий елемент (1,5)
| I | базис | Cб | P0 | M | M | ||||||
| Px1 | Px2 | Py1 | Py2 | Py3 | Pu1 | Pu2 | Pv1 | Pv2 | Pv3 | Pz1 | Pz2 |
| 1 | Py3 | 1 | -5/2 | 1 | -1/2 | -1/2 | -1 | ||||
| 2 | Py2 | 1 | -2 | -1/2 | 1 | -1/2 | -1/2 | 1 | |||
| 3 | Pv1 | 26 | -1 | 1 | -2 | ||||||
| 4 | Pv2 | 2 | -2 | 1 | 1 | ||||||
| 5 | Px2 | 4 | 1 | 1 | -1 | ||||||
| 5 |
План отриманий в результаті розв’язування задачі симплекс-методом, не є оптимальним так як він не задовольняє умови:
Отже перерахуємо симплекс-таблицю ще раз.
Обраний розв’язковий елемент (2,7)
| I | базис | Cб | P0 | ||||||
| Px1 | Px2 | Py1 | Py2 | Py3 | Pu1 | Pu2 | Pv1 | Pv2 | Pv3 |
| 1 | Py3 | 10 | 2 | -3 | 1 | 1 | -1 | -2 | |
| 2 | Pu2 | 18 | 4 | -1 | 2 | -1 | 1 | -2 | |
| 3 | Pv1 | 30 | 1 | 1 | -3 | ||||
| 4 | Pv2 | 10 | 2 | 1 | -1 | ||||
| 5 | Px2 | 4 | 1 | 1 | -1 | ||||
| 5 |
Отриманий план оптимальнийX* (0,4); F* (X* )=-16
Список використаної літератури
1. Карманов В. Г. Математическое программирование: Учеб. пособие. — 5-е издание., стереотип. — М.: ФИЗМАТЛИТ, 2001. — 264 с.
2. Моисеев Н. Н., Иванилов Ю. П., Столярова Е. М. Методы оптимизации —М.: Наука, 1978. — 352 с.