Міністерство освіти і науки України
Черкаський
національний
університет імені Богдана Хмельницького
Ф
акультет інформаційних технологій і
біомедичної кібернетики
РОЗРАХУНКОВА РОБОТА
з курсу „Математичне моделювання економічних систем”
студента 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 | базис | 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М | -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 с.