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

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

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

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

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

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

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

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

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

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

Черкаси – 2006 р.

Зміст

Зміст

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

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

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

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

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

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

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

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

3. ,

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

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

I: 60
09
II: 0-6
60
III: 04
40

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

Умовам невід’ємності та відповідає перша чверть.

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

Побудуємо вектор нормалі .

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

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

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

X2
X*
X1

Відповідь:

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

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

X(0) =(0,0,18,6,0,4)

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

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

IБазисP023000-M
P1P2P3P4P5P6
1P3018321000
2P406-110100
3P6-M41100-11
40-2-30000
5-4-1-10010

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

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

IБазисP023000-M
P1P2P3P4P5P6
1P301010102-2
2P402-20011-1
3P2341100-1-1
4121000-3-3
5000000-1

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

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

IБазисP023000-M
P1P2P3P4P5P6
1P306501-200
2P502-20011-1
3P236-110100
418-500300
5000000-1

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

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

IБазисP023000-M
P1P2P3P4P5P6
1P126/5101/5-2/500
2P5022/5002/51/51-1
3P2336/5011/53/500
424001100
50000001

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

Розв’язок : X* (,) F* =24;

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

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

3. ,

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

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

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

,,

Розв’язок:

Fmin* = 9,6;

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

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

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

,

Відповідь:

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

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

IБазисP023000-M
P1P2P3P4P5P6
1P126/5101/5-2/500
2P5022/5002/51/51-1
3P2336/5011/53/500
424001100
50000001

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

IБазисP0230000
P1P2P3P4P5P7
1P126/5101/5-2/500
2P5022/5002/51/510
3P2336/5011/53/500
4P70-1/500-1/5-3/501
524001100

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

IБазисP0230000
P1P2P3P4P5P7
1P121100-100
2P50400011/510
3P237010000
4P402001301
514000200

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

Розв’язок : 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.

ПунктиПункти споживанняЗапаси
ПостачанняB1B2B3
A1357270
A2694180
A311810300
Потреби260280300

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

Хi,

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

ПунктиПункти споживанняЗапаси
ПостачанняB1B2B3
A1357270
A2694180
A311810300
A400090
Потреби260280300

840

840

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

ПунктиПункти споживанняЗапаси
ПостачанняB1B2B3
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

Потреби260280300

840

840

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

.

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

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

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

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

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

.

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

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

ПунктиПункти споживанняЗапаси
ПостачанняB1B2B3
A13570

270

26010
A261947

180

180+
A311-5810

300

+90210
A40-40-20

90

90
Потреби260280300

840

840

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

ПунктиПункти споживанняЗапаси
ПостачанняB1B2B3
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

Потреби260280300

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БазисP00000000000MM
Px1Px2Py1Py2Py3Pu1Pu2Pv1Pv2Pv3Pz1Pz2
1Pz1M2-20-311-1000010
2Pu2080221-10100000
3Pv1018-3-20000010000
4Pv206-110000001000
5Pz2M4110000000-101
5-MM-3MMM-M000-M00

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

IБазисP00000000000MM
Px1Px2Py1Py2Py3Pu1Pu2Pv1Pv2Pv3Pz1Pz2
1Pz1M2-20-311-1000010
2Pu200-2021-10100200
3Pv1026-100000010-200
4Pv202-200000001100
5Px204110000000-101
5-2М0-3ММM000000

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

IБазисP00000000000MM
Px1Px2Py1Py2Py3Pu1Pu2Pv1Pv2Pv3Pz1Pz2
1Pz1M200-502-1-100-21
2Py200-2021-1010020
3Pv1026-100000010-20
4Pv202-20000000110
5Px204110000000-10
52M00-5M02M-M-M00-2M0

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

IБазисP00000000000MM
Px1Px2Py1Py2Py3Pu1Pu2Pv1Pv2Pv3Pz1Pz2
1Py30100-5/201-1/2-1/200-1
2Py201-20-1/210-1/2-1/2001
3Pv1026-100000010-2
4Pv202-2000000011
5Px204110000000-1
500000000000

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

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

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

IБазисP00000000000
Px1Px2Py1Py2Py3Pu1Pu2Pv1Pv2Pv3
1Py301002-311-1000-2
2Pu201804-120-1100-2
3Pv1030010000010-3
4Pv2010020000001-1
5Px204110000000-1
500000000000

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

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

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

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


1 Star2 Stars3 Stars4 Stars5 Stars (No Ratings Yet)
Loading...
Математичне моделювання економічних систем