Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Розв’язування задач лінійного праграмування симплекс-методом
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Інститут комп’ютерних наук та інформаційних технологій
Факультет:
УІ
Кафедра:
Кафедра САПР
Інформація про роботу
Рік:
2024
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Математичні методи дослідження операцій
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Національний університет «Львівська політехніка»
Інститут комп’ютерних наук та інформаційних технологій
Кафедра САПР
/
Звіт
до лабораторної роботи №2
на тему :
«Розв’язування задач лінійного праграмування симплекс-методом»
з дисципліни «Математичні методи дослідження операцій»
Мета роботи: Ознайомитись на практиці із основними поняттями теорії лінійного програмування, навчитись знаходити оптимальні плани задач лінійного програмування графічно, за допомогою симплекс методу і двоїстого симплекс методу
Варіант 14
Короткі теоретичні відомості:
Лінійне програмування – це галузь математичного програмування, який вивчає підходи до побудови математичних моделей оптимізаційних задач, що характеризуються лінійною функцією мети та лінійними залежностями між змінними, та методи їх розв’язування.
Під задачею лінійного програмування (ЗЛП) в загальному розуміють задачу знаходження мінімуму (максимуму) лінійної функції від n змінних на множині розв’язків системи лінійних нерівностей або лінійних рівнянь.
Розв’язати задачу ЛП означає знайти її оптимальний план та обчислити максимальне (мінімальне) значення цільової функції або показати, що оптимального плану не існує.
Під час розв’язку задачі ЛП можливі три випадки:
Існує оптимальний план (єдиний або нескінченна множина оптимальних планів).
Оптимальний план не існує, хоча плани даної задачі існують, але на непустій множині планів цільова функція не обмежена (зверху – в задачі максимізації, знизу – в задачі мінімізації).
Оптимального плану не існує, тому що в задачі не існує жодного плану.
Окрім того, існує три форми задачі лінійного програмування:
Загальна задача, коли система обмежень містить хоча б одну нерівність.
Основна задача – це випадок задачі ЛП, коли всі обмеження системи є рівняннями.
Канонічна задача – це частковий випадок основної задачі у тому розумінні, що система рівнянь – канонічна, а цільова функція виражена тільки через вільні невідомі.
Система лінійних рівнянь називають канонічною системою, якщо вона задовольняє такі дві умови:
У кожному рівнянні є одна невідома змінна з коефіцієнтом, що дорівнює 1, яка відсутня у решті рівнянь. Таку невідому називають базисною.
Вільні члени усіх рівнянь системи невід’ємні.
Невідомі змінні, що не є базисними, називають вільними. Завдання 1. Для виробництва двох видів високопробної нержавіючої сталі А і В використовується три види добавок до руди. Для виробництва 1 т сталі виду А треба затратити 12 кг добавок першого виду, 10 кг добавок другого виду і 3 кг добавок третього виду. Для виробництва 1 т сталі виду В треба затратити добавок першого виду 3 кг, добавок другого виду 5 кг, добавок третього виду 6 кг. Завод забезпечений добавками першого виду кількістю 684 кг, добавками другого виду кількістю 690 кг, третього виду – 558 кг. Обидва види сталі використовуються для виробництва нових різців при модернізації виробництва. Економія металу (за рахунок збільшення строку служби нових різців) при обробці новими різцями зі сталі виду А на 1 тис. виробів складає 6 т, зі сталі виду В – 2 т. Скласти план виробництва сталі видів А і В, який забезпечує максимальну економію металу.
Створення таблиці відповідно до завдання:
Види добавок
A
B
Забезпечення добавками
1
12
3
684
2
10
5
690
3
3
6
558
6
2
Математична модель задачі:
12?
1
+
3?
2
≤684
10?
1
+
5?
2
≤690
3?
1
+
6?
2
≤558
За змістом задачі змінні задовільняють умови невід’ємності:
?
1
,
?
2
≥0
Економія металу при обробці новими при обробці новими різцями рівна:
?−
6?
1
−
2?
2
=0
Розширена система:
12?
1
+
3?
2
+
?
3
=684
10?
1
+
5?
2
+
?
4
=690
3?
1
+
6?
2
+
?
5
=558
?−
6?
1
−
2?
2
=0
Знаходимо оціночні відношення:
684/12=57
690/10=69
558/3=186
Базис
Вільний член
Змінні
Оціночні відношення
Основні
Додаткові
x1
x2
x3
x4
x5
x3
684
12
3
1
0
0
57
x4
690
10
5
0
1
0
69
x5
558
3
6
0
0
1
186
F
0
-6
-2
0
0
0
Симплекс-таблиця 1
Новий базисний розв’язок системи знайдемо за правилом прямокутника
?
1
=
684
12
=57
?
2
=690−
684∗10
12
=120
?
3
=558−
684∗3
12
=387
?
4
=0−
684∗(−6)
12
=342
?
12
=
3
12
=
1
4
,
?
13
=
1
12
?
22
=5−
10∗3
12
=2,5 ,
?
23
=0−
10∗1
12
=−
5
6
?
32
=6−
3∗3
12
=5,25 ,
?
33
=0−
3∗1
12
=0,25
?
42
=−2−
3∗
−6
12
=−0,5 ,
?
43
=0−
1∗
−6
12
=0,5
Знаходимо оціночні відношення за новим ведучим стовпчиком:
57/0,25=228
120/2,5=48
387/5,25=73
5
7
Базис
Вільний член
Змінні
Оціноцні відношення
x1
x2
x3
x4
x5
x1
57
1
1
4
1
12
0
0
228
x4
120
0
2,5
−
5
6
1
0
48
x5
387
0
5,25
0,25
0
1
73
5
7
F
342
0
−0,5
0,5
0
0
Симплекс-таблиця 2
У СТ-2 в останньому рядку існують від’ємні числа, що свідчить про те, що план не є оптимальним. Аналогічно, можна побудувати СТ-3
?
2
=
120
2,5
=48
?
1
=57−
120∗0,25
2,5
=45
?
3
=387−
120∗5,25
2,5
=135
?
4
=342−
120∗(−0,5)
2,5
=366
?
13
=
1
6
,
?
14
=−
1
10
?
23
=
−
5
6
2,5
=−
1
3
,
?
24
=
1
2,5
=0,4
?
33
=0,25−
5,25∗(−
5
6
)
2,5
=2 ,
?
34
=0−
5,25∗1
2,5
=−2,1
?
43
=0,5−
−0,5∗
−
5
6
2,5
=
1
3
,
?
44
=0−
1∗
−0,5
2,5
=0,2
Базис
Вільний член
Змінні
x1
x2
x3
x4
x5
x1
45
1
0
1
6
−
1
10
0
x2
48
0
1
−
1
3
0,4
0
x5
135
0
0
2
−2,1
1
F
366
0
0
1
3
0,2
0
Опорний план Х*=(45, 48, 0, 0, 135) є оптимальним та max f = 366.
Знайдений опорний план показує, що для досягнення максимальної економії металу потрібно виробляти 45 тонн сталі A, 48 тонн сталі B.
Максимальне значення функції економії металу досягає 366, що означає, що за допомогою знайденого оптимального плану можна отримати максимальну економію металу у виробництві сталі. Такий план виробництва забезпечує оптимальне використання наявних ресурсів та досягнення максимального результату в умовах обмежених обсягів добавок.
Програма для обчислення даної задачі лінійного програмування симплекс-методом:
import numpy as np
def simplex_method(tableau):
num_vars = tableau.shape[1] - 1
num_constraints = tableau.shape[0] - 1
while np.any(tableau[-1, :-1] < 0):
entering_column = np.where(tableau[-1, :-1] < 0)[0][0]
if np.all(tableau[:-1, entering_column] <= 0):
raise Exception("Метод не збігається: не можна ввести нову змінну.")
ratios = tableau[:-1, -1] / tableau[:-1, entering_column]
leaving_row = np.argmin(ratios)
pivot_element = tableau[leaving_row, entering_column]
tableau[leaving_row, :] /= pivot_element
for i in range(num_constraints + 1):
if i != leaving_row:
multiplier = tableau[i, entering_column]
tableau[i, :] -= multiplier * tableau[leaving_row, :]
return tableau
# Початкова симплекс-таблиця
initial_tableau = np.array([
[12, 3, 1, 0, 0, 684],
[10, 5, 0, 1, 0, 690],
[3, 6, 0, 0, 1, 558],
[-6, -2, 0, 0, 0, 0]
], dtype=float)
optimal_tableau = simplex_method(initial_tableau)
# Максимальне значення функції економії металу
max_metal_savings = optimal_tableau[-1, -1]
print("Максимальне значення функції економії металу:", int(max_metal_savings))
# Оптимальний план виробництва
production_plan = optimal_tableau[:-1, -1]
print(f'План виробництва сталі видів А і В: {int(production_plan[0])}, {int(production_plan[1])} відповідно')
Вивід програми:
/
Рис. 1 Вивід програми максимального значення функції економії металу та оптимальний план виробництва
Завдання 2.
Цільова функія ?
?
1
,
?
2
=
3?
1
+
2?
2
→???
Обмеження:
?
1
≤40;
?
2
≤70;
−
?
1
+
3?
2
≥−20;
?
1
+
?
2
≤90;
−3?
1
+
?
2
≤0;
?
1
≥0;
?
2
≥0.
Програма розв’язування задачі ЛП:
# Задаємо цільову функцію та обмеження
def objective(x1, x2):
return 3 * x1 + 2 * x2
# Обмеження
constraints = [
lambda x1, x2: x1 <= 40,
lambda x1, x2: x2 <= 70,
lambda x1, x2: -x1 + 3 * x2 >= -20,
lambda x1, x2: x1 + x2 <= 90,
lambda x1, x2: -3 * x1 + x2 <= 0,
lambda x1, x2: x1 >= 0,
lambda x1, x2: x2 >= 0
]
# Функція для перевірки, чи задовольняє точка всім обмеженням
def is_feasible(x1, x2):
return all(constraint(x1, x2) for constraint in constraints)
# Пошук оптимального розв'язку
max_val = float('-inf')
best_solution = None
for x1 in range(91): # Знаходимо всі можливі значення x1 та x2
for x2 in range(91):
if is_feasible(x1, x2): # Перевіряємо, чи точка задовольняє всім обмеженням
current_val = objective(x1, x2)
if current_val > max_val: # Перевіряємо, чи поточне значення краще за максимальне
max_val = current_val
best_solution = (x1, x2)
# Вивід результатів
if best_solution is not None:
print("Максимальне значення функції:", max_val)
print("Значення змінних:", best_solution)
else:
print("Оптимальний розв'язок не знайдено")
/
Рис. 2 Вивід програми максимального значення функції та значення змінних
/ Рис. 3 Графічний метод розв’язання задачі ЛП.
Розв’язок задачі лінійного програмування: х1=40; x2=50 (остання точка перетину прямої, що відповідає функції мети, з багатокутником)
?
?
1
,
?
2
=
3?
1
+
2?
2
→???
?
?
1
,
?
2
=3∗40+2∗50=220
Отже, задана функція має в точці (40;50) максимальне значення рівне 220.
Висновок: Під час виконання даної лабораторної роботи я ознайомилася з основними поняттями та методами теорії лінійного програмування, а саме графічним методом, симплекс методом та двоїстим симплекс методом.
В процесі роботи було опановано принципи побудови та аналізу графічного методу, що дозволяє знаходити оптимальні рішення в задачах лінійного програмування за допомогою графічного представлення обмежень та цільової функції. Крім того, було вивчено та застосовано симплекс метод та двоїстий симплекс метод для розв'язання задач лінійного програмування більш складними методами, особливо коли кількість змінних і обмежень стає значною.
Результатом виконання лабораторної роботи стала можливість знаходити оптимальні плани у задачах лінійного програмування з використанням різних методів та порівнювати їх ефективність у різних ситуаціях. Такий досвід є важливим для подальшої роботи в області оптимізації процесів та прийняття рішень в умовах обмежень. Відповіді на контрольні запитання: 1. Сформулюйте задачу лінійного програмування. Задача лінійного програмування - це математична задача оптимізації, яка полягає у мінімізації або максимізації лінійної функції при обмеженнях, що задаються лінійними нерівностями. 2. Що таке цільова функція? Цільова функція - це математична функція, яка визначається у задачі оптимізації і виражає те, що потрібно мінімізувати або максимізувати. 3. Як задачу мінімізації звести до задачі максимізації цільової функції? Щоб звести задачу мінімізації до задачі максимізації цільової функції, потрібно помножити її на -1. Це змінить напрямок оптимізації з мінімума на максимум і навпаки. 4. Який план називається опорним?
Опорний план - це той допустимий план, який містить базисні змінні, які відповідають ненульовим значенням у рядках цільової функції. 5. Що таке допустимий план?
Допустимий план - це такий розв'язок системи лінійних рівнянь або нерівностей, який задовольняє всім обмеженням. 6. Які є три форми задачі ЛП?
Три форми задачі ЛП: канонічна, стандартна і загальна. 7. Яка система називається канонічною?
Система називається канонічною, якщо всі змінні неот'ємні і в обмеженнях входять тільки рівності. 8. Яка різниця між вільними та базисними змінними?
Вільні змінні - це змінні, які не входять у базис допустимого плану, а базисні змінні - це ті, які входять у базис. 9. Опишіть алгоритм симлекс-методу.
Алгоритм симплекс-методу полягає у пошуку оптимального розв'язку лінійної програми шляхом переходу від одного допустимого плану до іншого в напрямку, що зменшує значення цільової функції. 10. На якій ідеї ґрунтується симплекс-метод?
Симплекс-метод ґрунтується на ідеї пошуку кращого розв'язку шляхом переходу від одного вершини полігону обмежень до іншої. 11. У чому суть правила прямокутників?
Правило прямокутників - це метод виявлення базисних змінних у симплекс-методі за допомогою знаходження максимального допустимого приросту цільової функції при зміні вільних змінних. 12. Який елемент симплекс таблиці називається головним
Головним елементом симплекс-таблиці називається елемент, який знаходиться у рядку цільової функції та стовпці базисної змінної, що входить у базис.
08.04.2025 12:04-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора