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

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

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

 

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

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

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

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

студента 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.

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

 

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

                

 

X2

 

X*

X1

Відповідь:              

 

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

 

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

                                

                    x⁽⁰⁾=(0,0,18,6,0,4)

Цільова функція

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

I	базис	Cб	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	базис	Cб	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	базис	Cб	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	базис	Cб	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) має оптимальний план , то                є оптимальним планом двоїстої задачі

 

, ,

Розв^язок:

 

F_min^*= 9,6;

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

 

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

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

,

 

Відповідь:              

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

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

I	базис	Cб	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	базис	Cб	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	базис	Cб	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) F_max^*=23;

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

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

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

 

,

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

 

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

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

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

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

 

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

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

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

 

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

Вводим заміну:

Вводим ще одну заміну:   

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

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

 

 

 

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

x₁=0 x₂=6

 

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

 

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

1.  Запаси деякого однорідного продукту знаходяться на трьох пунктах постачання (базах) A1, A2, A3 і цей продукт потрiбно доставити в три пункти споживання (призначення) B1, B2, B3. Задача полягає в тому, щоб визначити, яку кiлькiсть продукту потрiбно перевезти з кожного пункту постачання (бази) до кожного пункту споживання (призначення) так, щоб забезпечити вивезення всього наявного продукту з пунктів постачання, задовільнити повністю потреби кожного пункту споживання і при цьому сумарна вартiсть перевезень була б мiнiмальною (зворотні перевезення виключаються). Вартість перевезень сij (у грн.) з бази Аi до пункту призначення Bj вказана в таблиці, де також наведені дані про запаси ai (у тонанх) продукту і його потреби (у тонах) bj.

Для даної транспортної задачі не виконується умова балансу , тому введемо додатковий пункт постачання з запасами 840-750=90 і тарифами С_4s=0 (i=1,2,3). Тоді одержимо замкнену транспортну задачу, яка має розв^язок. Її математична модель має вигляд:

  х_i,

_j ³ 0, 1£ i £4, 1£ j £3.

 

За методом північно-західного кута знайдемо опорний план

За методом північно-західного кута опорний план має вигляд:

.

F=3*260+5*10+9*180+8*90+10*210+0*90=5270

Перевіримо чи буде він оптимальним.

Знаходимо потенціали для пунктів постачання

Для тих клітинок, де, розв^яжемо систему рівнянь

          

Знаходимо з системи:

.

Для тих клітинок, де, знайдемо числа  

Оскільки , то план Х₁ не є оптимальним. Будуємо цикл перерахунку

В результаті перерахунку отримаємо

Наступний опорний план

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	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	базис	Cб	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М	-2М	0	-3М	М	M	-М	0	0	0	0	0	0

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

I	базис	Cб	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	базис	Cб	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	базис	Cб	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

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

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

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