Міністерство освіти і науки України
Черкаський
національний
університет імені Богдана Хмельницького
Ф
акультет інформаційних технологій і
біомедичної кібернетики
РОЗРАХУНКОВА РОБОТА
з курсу „Математичне моделювання економічних систем”
студента 4-го курсу спеціальності
«інтелектуальні системи прийняття рішень»
Валяєва Олександра В’ячеславовича
Черкаси – 2006 р.
Зміст
Зміст
Завдання 1. Задача лінійного програмування
Завдання 2. Задача цілочислового програмування
Завдання 3. Задача дробово-лінійного програмування
Завдання 4. Транспортна задача
Завдання 5. Задача квадратичного програмування
Список використаної літератури
Завдання 1
. Задача лінійного програмування
Для заданої задачі лінійного програмування побудувати двоїсту задачу. Знайти розв’язок прямої задачі геометричним методом і симплекс-методом. Знайти розв’язок двоїстої задачі, використовуючи результати розв’язування прямої задачі симплекс-методом:
3.
,
Розв
′язання г
еометричним методом
Побудуємо прямі, рівняння яких одержуються внаслідок заміни в обмеженнях знаків нерівностей на знаки рівностей.
Визначимо півплощини, що задовольняють нашим нерівностям.
Умовам невід’ємності
та
відповідає перша чверть.
Заштрихуємо спільну частину площини, що задовольняє всім нерівностям.
Побудуємо вектор нормалі
.
Максимального значення функція набуває в точці перетину прямих 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 с.
|