Рефераты Предметные области Типы работ

База рефератов » Контрольная работа » Информатика и программирование

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

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

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

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

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

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


студента 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базис

P0

23000-M

P1

P2

P3

P4

P5

P6

1

P3

018321000
2

P4

06-110100
3

P6

-M41100-11
40-2-30000
5-4-1-10010

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


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

Iбазис

P0

23000-M

P1

P2

P3

P4

P5

P6

1

P3

01010102-2
2

P4

02-20011-1
3

P2

341100-1-1
4121000-3-3
5000000-1

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

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

Iбазис

P0

23000-M

P1

P2

P3

P4

P5

P6

1

P3

06501-200
2

P5

02-20011-1
3

P2

36-110100
418-500300
5000000-1

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

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

Iбазис

P0

23000-M

P1

P2

P3

P4

P5

P6

1

P1

26/5101/5-2/500
2

P5

022/5002/51/51-1
3

P2

336/5011/53/500
424001100
50000001

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

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

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

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

3. ,

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

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

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

, ,

Розв’язок:

Fmin*= 9,6;

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

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

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

,


Відповідь:              

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

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

Iбазис

P0

23000-M

P1

P2

P3

P4

P5

P6

1

P1

26/5101/5-2/500
2

P5

022/5002/51/51-1
3

P2

336/5011/53/500
424001100
50000001

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

 

 

Iбазис

P0

230000

P1

P2

P3

P4

P5

P7

1

P1

26/5101/5-2/500
2

P5

022/5002/51/510
3

P2

336/5011/53/500
4

P7

0-1/500-1/5-3/501
524001100

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

Iбазис

P0

230000

P1

P2

P3

P4

P5

P7

1

P1

21100-100
2

P5

0400011/510
3

P2

37010000
4

P4

02001301
514000200

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

Розв’язок: 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. Транспортна задача

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

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

7270
A26

9

180

4180
A311

8

90

10

210

300
A400

0

90

90
Потреби260280300

840

840

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

.

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

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

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

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

          

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

.


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

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

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

постачанняB1B2B3

A13570270
26010
A261947180
-180+
A311-5810300
+90-210
A40-40-2090
90
Потреби260280300

840

840

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

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

3

260

5

10

7270
A269

4

180

180
A311

8

270

10

30

300
A400

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

P0

0000000000MM

Px1

Px2

Py1

Py2

Py3

Pu1

Pu2

Pv1

Pv2

Pv3

Pz1

Pz2

1

Pz1

M2-20-311-1000010
2

Pu2

080221-10100000
3

Pv1

018-3-20000010000
4

Pv2

06-110000001000
5

Pz2

M4110000000-101
5-MM-3MMM-M000-M00

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

Iбазис

P0

0000000000MM

Px1

Px2

Py1

Py2

Py3

Pu1

Pu2

Pv1

Pv2

Pv3

Pz1

Pz2

1

Pz1

M2-20-311-1000010
2

Pu2

00-2021-10100200
3

Pv1

026-100000010-200
4

Pv2

02-200000001100
5

Px2

04110000000-101
5-2М0-3ММM000000

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

Iбазис

P0

0000000000MM

Px1

Px2

Py1

Py2

Py3

Pu1

Pu2

Pv1

Pv2

Pv3

Pz1

Pz2

1

Pz1

M200-502-1-100-21
2

Py2

00-2021-1010020
3

Pv1

026-100000010-20
4

Pv2

02-20000000110
5

Px2

04110000000-10
52M00-5M02M-M-M00-2M0

 


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

Iбазис

P0

0000000000MM

Px1

Px2

Py1

Py2

Py3

Pu1

Pu2

Pv1

Pv2

Pv3

Pz1

Pz2

1

Py3

0100-5/201-1/2-1/200-1
2

Py2

01-20-1/210-1/2-1/2001
3

Pv1

026-100000010-2
4

Pv2

02-2000000011
5

Px2

04110000000-1
500000000000

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

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

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

Iбазис

P0

0000000000

Px1

Px2

Py1

Py2

Py3

Pu1

Pu2

Pv1

Pv2

Pv3

1

Py3

01002-311-1000-2
2

Pu2

01804-120-1100-2
3

Pv1

030010000010-3
4

Pv2

010020000001-1
5

Px2

04110000000-1
500000000000

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


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

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

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


© 2010-2024 Бесплатные рефераты скачать бесплатно. скачать бесплатно реферат на тему