Рефетека.ру / Информатика и програм-ие

Контрольная работа: Математичне моделювання економічних систем

Міністерство освіти і науки України

Черкаський національний університет імені Богдана Хмельницького


Факультет інформаційних технологій і

біомедичної кібернетики


РОЗРАХУНКОВА РОБОТА

з курсу „Математичне моделювання економічних систем”


студента 4-го курсу спеціальності

«інтелектуальні системи прийняття рішень»

Валяєва Олександра В’ячеславовича


Черкаси – 2006 р.

Зміст


Зміст

Завдання 1. Задача лінійного програмування

Завдання 2. Задача цілочислового програмування

Завдання 3. Задача дробово-лінійного програмування

Завдання 4. Транспортна задача

Завдання 5. Задача квадратичного програмування

Список використаної літератури

Завдання 1. Задача лінійного програмування


 Для заданої задачі лінійного програмування побудувати двоїсту задачу. Знайти розв’язок прямої задачі геометричним методом і симплекс-методом. Знайти розв’язок двоїстої задачі, використовуючи результати розв’язування прямої задачі симплекс-методом:


3. Математичне моделювання економічних систем,

Математичне моделювання економічних систем

Математичне моделювання економічних систем


Розв′язання геометричним методом


Побудуємо прямі, рівняння яких одержуються внаслідок заміни в обмеженнях знаків нерівностей на знаки рівностей.


I: Математичне моделювання економічних систем

Математичне моделювання економічних систем

6 0

Математичне моделювання економічних систем

0 9

II: Математичне моделювання економічних систем

Математичне моделювання економічних систем

0 -6

Математичне моделювання економічних систем

6 0

III: Математичне моделювання економічних систем

Математичне моделювання економічних систем

0 4

Математичне моделювання економічних систем

4 0

Визначимо півплощини, що задовольняють нашим нерівностям.

Умовам невід’ємності Математичне моделювання економічних систем та Математичне моделювання економічних систем відповідає перша чверть.

Заштрихуємо спільну частину площини, що задовольняє всім нерівностям.

Побудуємо вектор нормалі Математичне моделювання економічних систем.


Максимального значення функція набуває в точці перетину прямих I та II.

Знайдемо координати цієї точки.


Приведемо систему до канонічного вигляду

Математичне моделювання економічних систем


Математичне моделювання економічних систем

Математичне моделювання економічних систем

Математичне моделювання економічних систем

Математичне моделювання економічних систем Математичне моделювання економічних систем


Математичне моделювання економічних системМатематичне моделювання економічних систем

Математичне моделювання економічних системМатематичне моделювання економічних систем

Математичне моделювання економічних системМатематичне моделювання економічних систем

Математичне моделювання економічних систем


Математичне моделювання економічних систем


Математичне моделювання економічних систем

Математичне моделювання економічних систем

Відповідь: Математичне моделювання економічних систем Математичне моделювання економічних систем


Розв′язання симплекс-методом


Приведемо систему рівнянь до канонічного вигляду


Математичне моделювання економічних систем

Математичне моделювання економічних систем

Математичне моделювання економічних систем Математичне моделювання економічних систем Математичне моделювання економічних систем Математичне моделювання економічних систем Математичне моделювання економічних систем Математичне моделювання економічних систем

Математичне моделювання економічних систем Математичне моделювання економічних систем x(0)=(0,0,18,6,0,4)


Цільова функція Математичне моделювання економічних систем

Побудуємо симплекс-таблицю

I базис P0 2 3 0 0 0 -M




P1 P2 P3 P4 P5 P6
1 P3 0 18 3 2 1 0 0 0
2 P4 0 6 -1 1 0 1 0 0
3 P6 -M 4 1 1 0 0 -1 1
4

0 -2 -3 0 0 0 0
5

-4 -1 -1 0 0 1 0

Отриманий план не оптимальний

Обраний ключовий елемент (3,2)

I базис P0 2 3 0 0 0 -M




P1 P2 P3 P4 P5 P6
1 P3 0 10 1 0 1 0 2 -2
2 P4 0 2 -2 0 0 1 1 -1
3 P2 3 4 1 1 0 0 -1 -1
4

12 1 0 0 0 -3 -3
5

0 0 0 0 0 0 -1

Отриманий план не оптимальний


Обраний ключовий елемент (2,5)

I базис P0 2 3 0 0 0 -M




P1 P2 P3 P4 P5 P6
1 P3 0 6 5 0 1 -2 0 0
2 P5 0 2 -2 0 0 1 1 -1
3 P2 3 6 -1 1 0 1 0 0
4

18 -5 0 0 3 0 0
5

0 0 0 0 0 0 -1

Отриманий план не оптимальний


Обраний ключовий елемент (1,1)

I базис P0 2 3 0 0 0 -M




P1 P2 P3 P4 P5 P6
1 P1 2 6/5 1 0 1/5 -2/5 0 0
2 P5 0 22/5 0 0 2/5 1/5 1 -1
3 P2 3 36/5 0 1 1/5 3/5 0 0
4

24 0 0 1 1 0 0
5

0 0 0 0 0 0 1

План оптимальний

Розв’язок: X*(Математичне моделювання економічних систем,Математичне моделювання економічних систем) F*=24;


Розв’язок двоїстої задач

Побудуємо двоїсту функцію


3. Математичне моделювання економічних систем,


Система обмежень


Математичне моделювання економічних систем


Скористаємось теоремою

Якщо задача лінійного програмування в канонічній формі (7)-(9) має оптимальний план Математичне моделювання економічних систем, то Математичне моделювання економічних систем є оптимальним планом двоїстої задачі


Математичне моделювання економічних систем, Математичне моделювання економічних систем,Математичне моделювання економічних систем

Математичне моделювання економічних системМатематичне моделювання економічних системМатематичне моделювання економічних систем


Розв’язок:


Математичне моделювання економічних системМатематичне моделювання економічних систем

Fmin*= 9,6;


Завдання 2. Задача цілочислового програмування


Для задачі із завдання 1, як для задачі цілочислового програмування, знайти розв’язки геометричним методом і методом Гоморі.

Розв′язання геометричним методом

Математичне моделювання економічних систем,

Математичне моделювання економічних систем

Математичне моделювання економічних систем

Математичне моделювання економічних системМатематичне моделювання економічних системМатематичне моделювання економічних системМатематичне моделювання економічних систем


Відповідь: Математичне моделювання економічних систем Математичне моделювання економічних систем


Розв′язання методом Гоморі


Наведемо останню симплекс-таблицю

I базис P0 2 3 0 0 0 -M




P1 P2 P3 P4 P5 P6
1 P1 2 6/5 1 0 1/5 -2/5 0 0
2 P5 0 22/5 0 0 2/5 1/5 1 -1
3 P2 3 36/5 0 1 1/5 3/5 0 0
4

24 0 0 1 1 0 0
5

0 0 0 0 0 0 1

Побудуємо нерівність Гоморі за першим аргументом.


Математичне моделювання економічних систем

Математичне моделювання економічних систем

Математичне моделювання економічних систем

Математичне моделювання економічних систем

Математичне моделювання економічних систем

Математичне моделювання економічних систем

Математичне моделювання економічних систем

Математичне моделювання економічних систем

Математичне моделювання економічних систем


I базис P0 2 3 0 0 0 0




P1 P2 P3 P4 P5 P7
1 P1 2 6/5 1 0 1/5 -2/5 0 0
2 P5 0 22/5 0 0 2/5 1/5 1 0
3 P2 3 36/5 0 1 1/5 3/5 0 0
4 P7 0 -1/5 0 0 -1/5 -3/5 0 1
5

24 0 0 1 1 0 0

Обраний розв’язковий елемент (4,4)

I базис P0 2 3 0 0 0 0




P1 P2 P3 P4 P5 P7
1 P1 2 1 1 0 0 -1 0 0
2 P5 0 4 0 0 0 11/5 1 0
3 P2 3 7 0 1 0 0 0 0
4 P4 0 2 0 0 1 3 0 1
5

14 0 0 0 2 0 0

Отриманий план являється оптимальним і цілочисельним.

Розв’язок: X*(1,7) Fmax*=23;


Відповідь: цілочисельною точкою максимуму даної задачі є точка (1,7)

Завдання 3. Задача дробово-лінійного програмування


Для задачі дробово-лінійного програмування знайти розв’язки геометричним методом і симплекс-методом:


Математичне моделювання економічних систем,

Математичне моделювання економічних систем

Математичне моделювання економічних систем


Розв′язання геометричним методом


Математичне моделювання економічних систем

Математичне моделювання економічних систем

Математичне моделювання економічних систем

Математичне моделювання економічних систем

Математичне моделювання економічних систем


Визначимо, в яку сторону потрібно обертати пряму навколо початку координат, щоб значення цільової функції збільшувалось. Таким чином ми визначимо яка з крайніх точок є точкою максимуму.

f(1;0) = 2/3 f(0;1) = 3/7

Тобто при крутінні прямої проти годинникової стрілки значення цільової функції зменшується.

Використаємо результати обчислень і геометричних побудов з попереднього завдання.

Математичне моделювання економічних систем




З графіка очевидно, що розв’язок лежить на перетині двох прямих. Для визначення точки перетину прямої І та ІІ розв′яжемо систему з двох рівнянь.


Математичне моделювання економічних систем

Математичне моделювання економічних систем

Математичне моделювання економічних систем

Математичне моделювання економічних систем

Математичне моделювання економічних систем


Відповідь: функція набуває максимального значення при x1=6/5, x2=36/5.

Розв′язання симплекс-методом


Перейдемо від задачі дробово-лінійного програмування до задачі лінійного програмування.


Вводим заміну: Математичне моделювання економічних систем

Математичне моделювання економічних систем


Вводим ще одну заміну: Математичне моделювання економічних систем Математичне моделювання економічних систем Математичне моделювання економічних систем

Після замін наша задача має такий вигляд:


Математичне моделювання економічних систем

Математичне моделювання економічних систем



Математичне моделювання економічних систем

Математичне моделювання економічних систем

Математичне моделювання економічних систем


Приведемо її до канонічної форми і доповнимо її базисами:

Математичне моделювання економічних систем

Математичне моделювання економічних систем

Математичне моделювання економічних систем

Математичне моделювання економічних систем

Математичне моделювання економічних систем


Математичне моделювання економічних систем

Математичне моделювання економічних систем

Математичне моделювання економічних систем

Математичне моделювання економічних систем


Математичне моделювання економічних систем

Математичне моделювання економічних систем

Математичне моделювання економічних систем

Математичне моделювання економічних систем


Повернемось до заміни:

x1=0 x2=6


Завдання 4. Транспортна задача


Для заданих транспортних задач скласти математичну модель і розв’язати їх методом потенціалів, використавши для визначення початкового плану метод мінімального елемента або північно-західного кута.

Запаси деякого однорідного продукту знаходяться на трьох пунктах постачання (базах) 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 0 0 0 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

0


0


0

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 0

270




260
10


A2 6 1 9
4 7

180





- 180 +

A3 11 -5 8
10

300





+ 90 - 210
A4 0 -4 0 -2 0

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

0


0


0

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 базис P0 0 0 0 0 0 0 0 0 0 0 M M




Px1 Px2 Py1 Py2 Py3 Pu1 Pu2 Pv1 Pv2 Pv3 Pz1 Pz2
1 Pz1 M 2 -2 0 -3 1 1 -1 0 0 0 0 1 0
2 Pu2 0 8 0 2 2 1 -1 0 1 0 0 0 0 0
3 Pv1 0 18 -3 -2 0 0 0 0 0 1 0 0 0 0
4 Pv2 0 6 -1 1 0 0 0 0 0 0 1 0 0 0
5 Pz2 M 4 1 1 0 0 0 0 0 0 0 -1 0 1
5


-M M -3M M M -M 0 0 0 -M 0 0

Обраний розв’язковий елемент (5,2)

I базис P0 0 0 0 0 0 0 0 0 0 0 M M




Px1 Px2 Py1 Py2 Py3 Pu1 Pu2 Pv1 Pv2 Pv3 Pz1 Pz2
1 Pz1 M 2 -2 0 -3 1 1 -1 0 0 0 0 1 0
2 Pu2 0 0 -2 0 2 1 -1 0 1 0 0 2 0 0
3 Pv1 0 26 -1 0 0 0 0 0 0 1 0 -2 0 0
4 Pv2 0 2 -2 0 0 0 0 0 0 0 1 1 0 0
5 Px2 0 4 1 1 0 0 0 0 0 0 0 -1 0 1
5

-2М 0 -3М М M 0 0 0 0 0 0

Обраний розв’язковий елемент (2,4)

I базис P0 0 0 0 0 0 0 0 0 0 0 M M




Px1 Px2 Py1 Py2 Py3 Pu1 Pu2 Pv1 Pv2 Pv3 Pz1 Pz2
1 Pz1 M 2 0 0 -5 0 2 -1 -1 0 0 -2 1
2 Py2 0 0 -2 0 2 1 -1 0 1 0 0 2 0
3 Pv1 0 26 -1 0 0 0 0 0 0 1 0 -2 0
4 Pv2 0 2 -2 0 0 0 0 0 0 0 1 1 0
5 Px2 0 4 1 1 0 0 0 0 0 0 0 -1 0
5

2M 0 0 -5M 0 2M -M -M 0 0 -2M 0

Обраний розв’язковий елемент (1,5)

I базис P0 0 0 0 0 0 0 0 0 0 0 M M




Px1 Px2 Py1 Py2 Py3 Pu1 Pu2 Pv1 Pv2 Pv3 Pz1 Pz2
1 Py3 0 1 0 0 -5/2 0 1 -1/2 -1/2 0 0 -1

2 Py2 0 1 -2 0 -1/2 1 0 -1/2 -1/2 0 0 1

3 Pv1 0 26 -1 0 0 0 0 0 0 1 0 -2

4 Pv2 0 2 -2 0 0 0 0 0 0 0 1 1

5 Px2 0 4 1 1 0 0 0 0 0 0 0 -1

5

0 0 0 0 0 0 0 0 0 0 0


План отриманий в результаті розв’язування задачі симплекс-методом, не є оптимальним так як він не задовольняє умови:


Математичне моделювання економічних систем


Отже перерахуємо симплекс-таблицю ще раз.

Обраний розв’язковий елемент (2,7)


I базис P0 0 0 0 0 0 0 0 0 0 0




Px1 Px2 Py1 Py2 Py3 Pu1 Pu2 Pv1 Pv2 Pv3
1 Py3 0 10 0 2 -3 1 1 -1 0 0 0 -2
2 Pu2 0 18 0 4 -1 2 0 -1 1 0 0 -2
3 Pv1 0 30 0 1 0 0 0 0 0 1 0 -3
4 Pv2 0 10 0 2 0 0 0 0 0 0 1 -1
5 Px2 0 4 1 1 0 0 0 0 0 0 0 -1
5

0 0 0 0 0 0 0 0 0 0 0

Отриманий план оптимальний X* (0,4); F*(X*)=-16

Список використаної літератури


Карманов В. Г. Математическое программирование: Учеб. пособие. — 5-е издание., стереотип. — М.: ФИЗМАТЛИТ, 2001. — 264 с.

Моисеев Н. Н., Иванилов Ю. П., Столярова Е. М. Методы оптимизации —М.: Наука, 1978. — 352 с.

Похожие работы:

  1. Економіко-математичне моделювання в управлінні ...
  2. • Економіко-математичне моделювання діяльності кредитних спілок
  3. • Основні положення статистичного моделювання систем зв'язку
  4. • Моделювання оптимального ...
  5. • Економіко-математичне моделювання
  6. • Моделювання економіки
  7. • Макроекономічне моделювання та прогнозування валютного курсу ...
  8. • Вимоги до написання дисертації. Математичне ...
  9. • Моделювання технологічних процесів в рибництві
  10. • Моделювання як метод наукового пізнання
  11. • Моделювання біофізичних процесів зорової системи
  12. • Економіко-математичне моделювання процесу ціноутворення на ...
  13. • Математичне моделювання руху поїзда
  14. • Моделювання процесу надходження до ЕОМ повідомлень
  15. • Моделювання на ЕОМ випадкових величин і випадкових процесів
  16. • Моделювання управлінських систем
  17. • Моделювання систем управлiння iнновацiйних структур
  18. • Моделювання економічних та виробничих процесів
  19. • Моделювання надходження ...
Рефетека ру refoteka@gmail.com