Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
КН
Кафедра:
Кафедра будівельної механіки
Інформація про роботу
Рік:
2014
Тип роботи:
Розрахунково - графічна робота
Предмет:
БЖД
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Національний університет « Львівська політехніка»
кафедра будівельної механіки
/
Розрахунково-графічна робота №3
з дисципліни: « Основи системного анілізу»
Варіант №1
Львів 2013
Задано:
Необхідно знайти мінімальне значення функції F = -2x1+2x2 → min, при такій системі обмежень:
2x1+4x2≤8 (1)
-6x1-3x2≤-4 (2)
x1-2x2≤2 (3)
3x1+x2≤6 (4)
x1≥0 (5)
x2≥0 (6)
Графічний метод розв’язку задачі.
Будуємо графіки прямих вище заданих рівнянь.
/
Перетин півплощин буде являти собою область, всі точки якої є розв’язками відповідної нерівності.
Розглянемо функцію F = -2x1+2x2 → min. Побудуємо пряму, яка відповідає значенню функції F = 0, F = -2x1+2x2 = 0. Так утворилась лінія рівня яка паралельно пересувається в напрямку вектора до збігу з крайньою точкою многокутника. Початок вектора – точка (0; 0), кінець – точка (-2; 2).На графіку ця пряма позначена пунктирною лінією.
/ /
Пряма F(x) = const перетинає область в точці F. Так як точка F отримана в результаті перетину прямих. То її координати задовольняє система рівнянь цих прямих: x1-2x2≤2 3x1+x2≤6 Розв’язуємо цю систему рівнянь і отримуємо координати точки: x1 = 2, x2 = 0
Звідси знаходимо мінімальне значення цільової функції:
Fmin(X) = -2*2 + 2*0 = -4
Відповідь: Fmin= -4.
Симплекс метод
Для побудови першого опорного плану систему нерівностей приведемо до системи рівнянь шляхом введення додаткових змінних ( перехід до канонічної форми ) .
У 1 -му нерівність сенсу ( ≤ ) вводимо базисну змінну x3 . У 2 -му нерівність сенсу ( ≥) вводимо базисну змінну x4 зі знаком мінус. У 3 -му нерівність сенсу ( ≤ ) вводимо базисну змінну x5 . У 4 -му нерівність сенсу ( ≤ ) вводимо базисну змінну x6 .
2x1 + 4x2 + 1x3 + 0x4 + 0x5 + 0x6 = 8 6x1 + 3x2 + 0x3-1x4 + 0x5 + 0x6 = 4 1x1-2x2 + 0x3 + 0x4 + 1x5 + 0x6 = 2 3x1 + 1x2 + 0x3 + 0x4 + 0x5 + 1x6 = 6
Введемо штучні змінні x : в 2 -му рівність вводимо змінну x7 ;
2x1 + 4x2 + 1x3 + 0x4 + 0x5 + 0x6 + 0x7 = 8 6x1 + 3x2 + 0x3-1x4 + 0x5 + 0x6 + 1x7 = 4 1x1-2x2 + 0x3 + 0x4 + 1x5 + 0x6 + 0x7 = 2 3x1 + 1x2 + 0x3 + 0x4 + 0x5 + 1x6 + 0x7 = 6
Для постановки задачі на мінімум цільову функцію запишемо так :
F(X) = -2x1+2x2+Mx7 → min
Отриманий базис називається штучним , а метод рішення називається методом штучного базису .
З рівнянь виводимо штучні змінні:
x7 = 4-6x1-3x2+x4, які підставимо в цільову функцію:
F(X) = -2x1 + 2x2 + M(4-6x1-3x2+x4) → min, або
F(X) = (-2-6M)x1+(2-3M)x2+(M)x4+(4M) → min
Вирішимо систему рівнянь щодо базисних змінних:
x3 , x7 , x5 , x6 ,
Базис
B
x1
x2
x3
x4
x5
x6
x7
x3
8
2
4
1
0
0
0
0
x7
4
6
3
0
-1
0
0
1
x5
2
1
-2
0
0
1
0
0
x6
6
3
1
0
0
0
1
0
F(X0)
4M
2+6M
-2+3M
0
-M
0
0
0
Переходимо до основного алгоритму симплекс - методу .
Ітерація №0
1 . Перевірка критерію оптимальності .
Поточний опорний план неоптимальний , тому що в індексному рядку знаходяться позитивні коефіцієнти .
2 . Визначення нової базисної змінної.
В якості ведучого виберемо стовпець , відповідний змінної x1 , так як це найбільший коефіцієнт .
3 . Визначення нової вільної змінної.
Обчислимо значення Di по рядках як частка від ділення : bi / ai1
і з них виберемо найменше :
min (8 : 2 , 4 : 6 , 2 : 1 , 6 : 3 ) = 2/3
Отже , 2 - ий рядок є ведучий.
Базис
B
x1
x2
x3
x4
x5
x6
x7
min
x3
8
2
4
1
0
0
0
0
4
x7
4
6
3
0
-1
0
0
1
x5
2
1
-2
0
0
1
0
0
2
x6
6
3
1
0
0
0
1
0
2
F(X1)
4M
2+6M
-2+3M
0
-M
0
0
0
0
4 . Перерахунок симплекс - таблиці.
Формуємо наступну частину симплексного таблиці.
Замість змінної x7 в план 1 увійде змінна x1.
Рядок , відповідна змінної x1 в плані 1 , отримана в результаті поділу всіх елементів рядка x7 плану 0 на дозволяючий елемент РЕ = 6
На місці дозволяє елемента в плані 1 отримуємо 1 .
В інших клітинах стовпця x1 плану 1 записуємо нулі .
Таким чином, у новому плані 1 заповнені рядок x1 і стовпець x1.
Всі інші елементи нового плану 1 , включаючи елементи індексного рядка , визначаються за правилом прямокутника.
Отримуємо нову симплекс-таблицю:
Базис
B
x1
x2
x3
x4
x5
x6
x7
x3
62/3
0
3
1
1/3
0
0
-1/3
x1
2/3
1
1/2
0
-1/6
0
0
1/6
x5
11/3
0
-21/2
0
1/6
1
0
-1/6
x6
4
0
-1/2
0
1/2
0
1
-1/2
F(X1)
-11/3
0
-3
0
1/3
0
0
-1/3-M
Ітерація №1
1 . Перевірка критерію оптимальності .
Поточний опорний план неоптимальний , тому що в індексному рядку знаходяться позитивні коефіцієнти .
2 . Визначення нової базисної змінної.
В якості ведучого виберемо стовпець , відповідний змінної x4 , так як це найбільший коефіцієнт .
3 . Визначення нової вільної змінної.
Обчислимо значення Di по рядках як частка від ділення : bi / ai4
і з них виберемо найменше :
min (62/3 : 1/3 , - , 11/3 : 1/6 , 4 : 1/2 ) = 8
Отже , 3 - ий рядок є ведучий.
Базис
B
x1
x2
x3
x4
x5
x6
x7
min
x3
62/3
0
3
1
1/3
0
0
-1/3
20
x1
2/3
1
1/2
0
-1/6
0
0
1/6
-
x5
11/3
0
-21/2
0
1
0
-1/6
8
x6
4
0
-1/2
0
1/2
0
1
-1/2
8
F(X2)
-11/3
0
-3
0
0
0
-1/3-M
0
4 . Перерахунок симплекс - таблиці.
Формуємо наступну частину симплексного таблиці.
Замість змінної x6 в план 2 увійде змінна x4.
Рядок , відповідна змінної x4 в плані 2 , отримана в результаті поділу всіх елементів рядка x6 плану 1 на дозволяючий елемент РЕ = 1/6
На місці дозволяє елемента в плані 2 отримуємо 1 .
В інших клітинах стовпця x4 плану 2 записуємо нулі .
Таким чином, у новому плані 2 заповнені рядок x4 і стовпець x4.
Всі інші елементи нового плану 2 , включаючи елементи індексного рядка , визначаються за правилом прямокутника.
Отримуємо нову симплекс-таблицю:
Базис
B
x1
x2
x3
x4
x5
x6
x7
x3
4
0
31/3
1
0
0
-2/3
0
x1
2
1
1/3
0
0
0
1/3
0
x5
0
0
-21/3
0
0
1
-1/3
0
x4
8
0
-1
0
1
0
2
-1
F(X3)
-4
0
-22/3
0
0
0
-2/3
-M
Оптимальне рішення можна записати так:
x1 = 2
Fmin(X) = -2•2 = -4
24.01.2014 19:18
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора