Реферат: Математичне моделювання економічних систем
Міністерство освіти і науки України
Черкаський національнийуніверситет імені Богдана Хмельницького
Факультет інформаційних технологій і
біомедичної кібернетики
РОЗРАХУНКОВА РОБОТА
з курсу „Математичне моделювання економічних систем”
студента 4-го курсу спеціальності
«інтелектуальні системи прийняття рішень»
Валяєва Олександра В’ячеславовича
Черкаси – 2006 р.
Зміст
Зміст
Завдання 1. Задача лінійного програмування
Завдання 2. Задача цілочислового програмування
Завдання 3. Задача дробово-лінійного програмування
Завдання 4. Транспортна задача
Завдання 5. Задача квадратичного програмування
Список використаної літератури
Завдання 1. Задача лінійного програмування
Для заданої задачі лінійного програмування побудувати двоїсту задачу. Знайти розв’язок прямої задачі геометричним методом і симплекс-методом. Знайти розв’язок двоїстої задачі, використовуючи результати розв’язування прямої задачі симплекс-методом:
3. />,
/>
/>
Розв′язання геометричним методом
Побудуємопрямі, рівняння яких одержуються внаслідок заміни в обмеженнях знаків нерівностей на знаки рівностей.
I: />
/>
6
/>
9
II: />
/>
-6
/>
6
III: />
/>
4
/>
4
Визначимо півплощини, що задовольняють нашим нерівностям.
Умовам невід’ємності /> та /> відповідає перша чверть.
Заштрихуємо спільну частину площини, що задовольняє всім нерівностям.
Побудуємо вектор нормалі />.
Максимального значення функція набуває в точці перетину прямих Iта II.
Знайдемо координати цієї точки.
Приведемо систему до канонічного вигляду
/>
/>
/>
/>
/>/>
/>/>
/>/>
/>/>
/>
/>
/>
/>
Відповідь: />/>
Розв′язаннясимплекс-методом
Приведемо систему рівнянь до канонічного вигляду
/>
/>
/>/>/>/>/>/>
--PAGE_BREAK--/>/>x(0)=(0,0,18,6,0,4)
Цільова функція />
Побудуємо симплекс-таблицю
I
базис
Cб
P
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б
P
2
3
-M
P1
P2
P3
P4
P5
P6
1
P3
продолжение--PAGE_BREAK----PAGE_BREAK--
3
5
-1
Отриманий план не оптимальний
Обраний ключовий елемент (1,1)
I
базис
Cб
P
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;
продолжение--PAGE_BREAK--
Завдання 2. Задача цілочислового програмування
Для задачі із завдання 1, як для задачі цілочислового програмування, знайти розв’язки геометричним методом і методом Гоморі.
Розв′язаннягеометричним методом
/>,
/>
/>
/>/>/>/>
Відповідь: />/>
Розв′язанняметодом Гоморі
Наведемо останню симплекс-таблицю
I
базис
Cб
P
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б
P
2
3
P1
продолжение--PAGE_BREAK----PAGE_BREAK----PAGE_BREAK----PAGE_BREAK----PAGE_BREAK----PAGE_BREAK--
7
270
A2
6
9
4
180
180
A3
11
8
270
10
30
300
A4
90
90
Потреби
260
280
3
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
/>
Зведемо систему обмежень до канонічного вигляду
/>
продолжение--PAGE_BREAK--
Введемо додаткові змінні для утворення штучного базису
/>
Розв’яжемо задачу лінійного програмування на знаходження мінімуму.
Введемо додаткові прямі обмеження на змінні.
/>,
/>
/>
Вектори з коефіцієнтів при невідомих:
/>
/>
/>/>
Розв’язуємо отриману задачу звичайним симплекс-методом
I
базис
Cб
P
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
продолжение--PAGE_BREAK----PAGE_BREAK----PAGE_BREAK----PAGE_BREAK----PAGE_BREAK--
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
Список використаної літератури
Карманов В. Г. Математическое программирование: Учеб. пособие. — 5-е издание., стереотип. — М.: ФИЗМАТЛИТ, 2001. — 264 с.
Моисеев Н. Н., Иванилов Ю. П., Столярова Е. М. Методы оптимизации—М.: Наука, 1978. — 352 с.