Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Розв`язування задач лінійного програмування за допомогою симплекс методу
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
АСУ
Інформація про роботу
Рік:
2024
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Математичні методи дослідження операцій
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки, молоді та спорту України
Національний Університет «Львівська Політехніка»
кафедра АСУ
Звіт
до лабораторної роботи №3-4
на тему «Розв`язування задач лінійного програмування за допомогою симплекс методу»
з дисципліни:
«Математичні методи дослідження операцій»
Лабораторна робота №3-4
Тема: Розв`язування задач лінійного програмування за допомогою симплекс методу.
Мета: Навчитись розв`язувати задачі лінійнго програмування з застосуванням симплекс методу.
Хід роботи
1.Короткі теоретичні відомості:
Симплекс-метод - це метод розв'язання задачі лінійного програмування, в якому здійснюється скерований рух по опорних планах до знаходження оптимального розв'язку. Досить часто симплекс-метод ще називають методом покращення плану. Реальні задачі лінійного програмування містять дуже велику кількість обмежень та невідомих і виконуються на ЕОМ. Симплекс-метод - найбільш загальний алгоритм, що використовується для рішення таких задач. Даний метод був розроблений американським математиком Джорджем Данцігом у 1947 році.
Основна ідея симплекс-метода полягає в тому, що екстремум цільової функції завжди досягається в кутових точках області допустимих рішень. Симплекс-метод, званий також методом послідовного поліпшення плану, реалізує перебір кутових точок області допустимих рішень у напрямі поліпшення значення цільової функції. Основна ідея цього методу наступна.
Перш за все, знаходиться яке-небудь допустиме початкове (опорне) рішення, тобто яка-небудь кутова точка області допустимих рішень.
Процедура методу дозволяє відповісти на питання, чи є це рішення оптимальним. Якщо "так", то завдання вирішене. Якщо "ні", то виконується перехід до суміжної кутової точки області допустимих рішень, де значення цільової функції поліпшується, тобто до негіршого допустимого рішення.
Застосування симплекс-методу для задачі лінійного програмування передбачає попереднє приведення її формальної постановки до канонічної форми з n невід'ємними змінними: (X 1, ..., X n), де потрібно мінімізація лінійної цільової функції при m лінійних обмеженнях типу рівностей. Серед змінних завдання вибирається початковий базис з m змінних, для визначеності (X 1, ..., X m), які повинні мати невід'ємні значення, коли решта (nm) вільні змінні рівні 0. Цільова функція та обмеження рівності перетворяться до діагональної формі щодо базисних змінних, змінних, де кожна базисна змінна входить лише в одне рівняння з коефіцієнтом 1.
1.2 Алгоритм симплекс методу
Перетворення стандартної форми задачі лінійного програмування в канонічну форму шляхом додавання невід'ємних змінних до кожної нерівності типу менше рівне (≤) обмежень:
Побудова і заповнення початкової симплекс таблиці. Симплекс таблиця є зручним інструментом для представлення канонічної форми лінійної задачі.Щоб заповнити початкову симплекс таблицю необхідно переписати цільову функцію F у вигляді аналогічному до системи обмежень,
Перевірка на оптимальність. Якщо всі коефіцієнти в рядку F є невід'ємними, то отриманий розв'язок є оптимальним, якщо хоча б один коефіцієнт є від'ємний, то необхідно продовжити симплекс ітерацію (заповнити наступну симплекс таблицю).
Вибір ведучого стовпця. Ведучим називається стовпець в якому міститься найбільший за модулем від'ємний коефіцієнт в рядку F.
Вибір ведучого рядка та ведучого елемента /, щоб вибрати ведучий рядок (а отже зміну, яка залишає базис) необхідно скористатись MRT тестом (мінімальне відношення). Для цього необхідно записати у відповідному рядку відношення змінної зі стовпця "план" до змінної з ведучого стовпця і визначити мінімальне з цих відношень. Рядок з мінімальним значенням з відношення буде ведучим рядком.
Після цього йде перевірка на основні правила та модифікація симплекс таблиці.
В кінцевому результаті отримуємо оптимальний розв`язок поставленої перед нами задачі.
2. Розв`язування задачі
2.1 Графічний метод
Завдання:(63)
F(x1,x2) = 6x1 -4x2 -> max;
5x1 + 2x2 >=10,
2x1 + 5x2 >=10,
-2x1 + x2 <=4,
x1 0, x2 0.
Перетворення:
y=5-5/2x
y= 2-2/5x
y=4+2x
/
2.2 Симплекс метод
Крок 0
Базис
БП
x 1
x 2
x 3
x 4
x 5
x 6
x 7
z 1
z 2
z1
10
5
2
-1
0
0
0
0
1
0
z2
10
2
5
0
-1
0
0
0
0
1
x5
4
-2
1
0
0
1
0
0
0
0
x6
6
1
0
0
0
0
1
0
0
0
x7
6
0
1
0
0
0
0
1
0
0
ІР
-20M
-7M-6
-7M+4
M
M
0
0
0
0
0
Крок 1
Базис
БП
x 1
x 2
x 3
x 4
x 5
x 6
x 7
z 1
z 2
x1
2
1
2/5
-1/5
0
0
0
0
1/5
0
z2
6
0
21/5
2/5
-1
0
0
0
-2/5
1
x5
8
0
9/5
-2/5
0
1
0
0
2/5
0
x6
4
0
-2/5
1/5
0
0
1
0
-1/5
0
x7
6
0
1
0
0
0
0
1
0
0
ІР
-6M+12
0
-21/5M+32/5
-2/5M-6/5
M
0
0
0
7/5M+6/5
0
Крок 2
Базис
БП
x 1
x 2
x 3
x 4
x 5
x 6
x 7
z 1
z 2
x1
10/7
1
0
-5/21
2/21
0
0
0
5/21
-2/21
x2
10/7
0
1
2/21
-5/21
0
0
0
-2/21
5/21
x5
38/7
0
0
-4/7
3/7
1
0
0
4/7
-3/7
x6
32/7
0
0
5/21
-2/21
0
1
0
-5/21
2/21
x7
32/7
0
0
-2/21
5/21
0
0
1
2/21
-5/21
ІР
20/7
0
0
-38/21
32/21
0
0
0
M+38/21
M-32/21
Крок 3
Базис
БП
x 1
x 2
x 3
x 4
x 5
x 6
x 7
z 1
z 2
x1
5
1
5/2
0
-1/2
0
0
0
0
1/2
x3
15
0
21/2
1
-5/2
0
0
0
-1
5/2
x5
14
0
6
0
-1
1
0
0
0
1
x6
1
0
-5/2
0
1/2
0
1
0
0
-1/2
x7
6
0
1
0
0
0
0
1
0
0
ІР
30
0
19
0
-3
0
0
0
M
M+3
Крок 4
Базис
БП
x 1
x 2
x 3
x 4
x 5
x 6
x 7
z 1
z 2
x1
6
1
0
0
0
0
1
0
0
0
x3
20
0
-2
1
0
0
5
0
-1
0
x5
16
0
1
0
0
1
2
0
0
0
x4
2
0
-5
0
1
0
2
0
0
-1
x7
6
0
1
0
0
0
0
1
0
0
ІР
36
0
4
0
0
0
6
0
M
M
2.3 Симплекс метод з введенням штучних змінних
Введемо штучні змінні x8 та x9.
Отримаємо: 5x1+2x2-x3+x4+x8=10;
2x1+5x2-x4+x9=10;
-2x1+x2+x5=4;
x1+x6=6;
x2+x7=6;
Зведемо рівняння до канонічної форми:
F(x)=6x1-4x2-Mx8-Mx9 - > max
З рівняння виведемо штучні змінні:
x8=10-5x1+2x2+x3;
x9==10-2x1-5x2+x4;
Підставимо в цільову функцію:
F(x)=(6+7M)x1+(-4+7M)x2+(-M)x3+(-M)x4 – (20M) -> max
x1=(0,0,0,0,4,6,6,10,10)
Базис
B
x1
x2
x3
x4
x5
x6
x7
x8
x9
x8
10
2
5
-1
0
0
0
0
1
0
x9
10
5
2
0
-1
0
0
0
0
1
x5
4
-2
1
0
0
1
0
0
0
0
x6
6
1
0
0
0
0
1
0
0
0
x7
6
0
1
0
0
0
0
1
0
0
F(X0)
-20M
-6-7M
4-7M
M
M
0
0
0
0
0
Базис
B
x1
x2
x3
x4
x5
x6
x7
x8
x9
x8
6
0
2/5
-1
2/5
0
0
0
1
-2/5
x1
2
1
41/5
0
-1/5
0
0
0
0
1/5
x5
8
0
14/5
0
-2/5
1
0
0
0
2/5
x6
4
0
-2/5
0
1/5
0
1
0
0
-1/5
x7
6
0
1
0
0
0
0
1
0
0
F(X1)
12-6M
0
62/5-41/5M
M
-11/5-2/5M
0
0
0
0
11/5+12/5M
Базис
B
x1
x2
x3
x4
x5
x6
x7
x8
x9
x2
13/7
0
1
-5/21
2/21
0
0
0
5/21
-2/21
x1
13/7
1
0
2/21
-5/21
0
0
0
-2/21
5/21
x5
53/7
0
0
3/7
-4/7
1
0
0
-3/7
4/7
x6
44/7
0
0
-2/21
5/21
0
1
0
2/21
-5/21
x7
44/7
0
0
5/21
-2/21
0
0
1
-5/21
2/21
F(X2)
26/7
0
0
111/21
-117/21
0
0
0
-111/21+M
117/21+M
Базис
B
x1
x2
x3
x4
x5
x6
x7
x8
x9
x4
15
0
101/2
-21/2
1
0
0
0
21/2
-1
x1
5
1
21/2
-1/2
0
0
0
0
1/2
0
x5
14
0
6
-1
0
1
0
0
1
0
x6
1
0
-21/2
1/2
0
0
1
0
-1/2
0
x7
6
0
1
0
0
0
0
1
0
0
F(X3)
30
0
19
-3
0
0
0
0
3+M
M
Базис
B
x1
x2
x3
x4
x5
x6
x7
x8
x9
x4
20
0
-2
0
1
0
5
0
0
-1
x1
6
1
0
0
0
0
1
0
0
0
x5
16
0
1
0
0
1
2
0
0
0
x3
2
0
-5
1
0
0
2
0
-1
0
x7
6
0
1
0
0
0
0
1
0
0
F(X4)
36
0
4
0
0
0
6
0
M
M
3.Висновок:
На цій лабораторній роботі я навчився розв’язувати задачі лінійного програмування за допомогою симплекс метода та методом застосування штучних змінних.
06.12.2015 15:12-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора