26
Міністерство освіти і науки України
Черкаський національний університет імені Богдана Хмельницького
Факультет інформаційних технологій і
біомедичної кібернетики
РОЗРАХУНКОВА РОБОТА
з курсу „Математичне моделювання економічних систем”
студента 4-го курсу спеціальності
«інтелектуальні системи прийняття рішень»
Валяєва Олександра Вячеславовича
Черкаси - 2006 р.
Зміст
Для заданої задачі лінійного програмування побудувати двоїсту задачу. Знайти розвязок прямої задачі геометричним методом і симплекс-методом. Знайти розвязок двоїстої задачі, використовуючи результати розвязування прямої задачі симплекс-методом:
|
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
Тобто при крутінні прямої проти годинникової стрілки значення цільової функції зменшується.
Використаємо результати обчислень і геометричних побудов з попереднього завдання.
З графіка очевидно, що розвязок лежить на перетині двох прямих. Для визначення точки перетину прямої І та ІІ розв?яжемо систему з двох рівнянь.
Відповідь: функція набуває максимального значення при 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.
|
Пункти |
Пункти споживання |
Запаси |
|||
|
постачання |
B1 |
B2 |
B3 |
||
|
A1 |
3 |
5 |
7 |
270 |
|
|
A2 |
6 |
9 |
4 |
180 |
|
|
A3 |
11 |
8 |
10 |
300 |
|
|
Потреби |
260 |
280 |
300 |
||
Для даної транспортної задачі не виконується умова балансу , тому введемо додатковий пункт постачання з запасами 840-750=90 і тарифами С4s=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 |
Px2 |
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 |
Px2 |
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 |
Px2 |
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 |
|
| Контрольная работа | Концепция информатизации Российской Федерации |
| Контрольная работа | Причины агрессивного поведения. Методы работы с агрессивными детьми |
| Контрольная работа | Алгоритм выбора и реализации предпринимательской идеи |
| Контрольная работа | Системы управления взаимоотношения с клиентами |
| Контрольная работа | Учет материальных затрат в бухгалтерском учете |
| Контрольная работа | Геополитическое положение России |
| Контрольная работа | Особенности вознаграждения работников в организации |
| Контрольная работа | Виды запасов |
| Контрольная работа | Психоанализ |
| Контрольная работа | Экономико-географическая характеристика Печорского угольного бассейна 2 |
| Контрольная работа | Развитие познавательных интересов у дошкольников в процессе ознакомления с природой |
| Контрольная работа | Индивидуальное развитие организмов (онтогенез) |
| Контрольная работа | Общественные движения России в первой четверти 19 века |
| Контрольная работа | Особенности разработки и принятия Конституции России 1993 года |
| Контрольная работа | Математические методы в психологии |