регистрация / вход

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

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

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

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

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

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

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

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

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

,,

Розв’язок:

Fmin * = 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) 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 .


Пункти Пункти споживання Запаси
постачання B1 B2 B3
A1 3 5 7 270
A2 6 9 4 180
A3 11 8 10 300
Потреби 260 280 300

Для даної транспортної задачі не виконується умова балансу , тому введемо додатковий пункт постачання з запасами 840-750=90 і тарифами С4 s =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 базис Cб P0 0 0 0 0 0 0 0 0 0 0 M M
Px1 Px 2 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 Px 2 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 Px 2 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 базис Cб P0 0 0 0 0 0 0 0 0 0 0 M M
Px1 Px 2 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 Px 2 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 Px 2 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 Px 2 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 Px 2 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 Px 2 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 с.

ОТКРЫТЬ САМ ДОКУМЕНТ В НОВОМ ОКНЕ

ДОБАВИТЬ КОММЕНТАРИЙ  [можно без регистрации]

Ваше имя:

Комментарий