Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Двоїстість задач лінійного програмування
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
АСУ
Інформація про роботу
Рік:
2024
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Математичні методи дослідження операцій
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки, молоді та спорту України
Національний Університет «Львівська Політехніка»
кафедра АСУ
Звіт
до лабораторної роботи №5
на тему: Двоїстість задач лінійного програмування
з дисципліни:
«Математичні методи дослідження операцій»
Лабораторна робота №5
Тема: Двоїстість задач лінійного програмування
Мета: Навчитись складати та розв’язувати двоїсті задачі лінійного програмування симплекс методом.
Хід роботи
1.Короткі теоретичні відомості:
1.1 Двоїстий симплекс метод
Для переходу до двоїстої задачі позначимо y1, y2, y3 – ціну одиниці часу роботи на токарному, фрезерному і свердлильному станках: (yi>0).
Тоді
витрати на виробництво Fmin(y) при умові, що сумарні затрати на одиницю продукції не менше вартості товару.
Обмеження
1.2 Алгоритм запису двоїстої задачі:
1. Коефіцієнти цільової функції прямої задачі с1,с2,…,сn стають вільними членами обмежень двоїстої задачі.
Вільні члени обмежень прямої задачі b1,b2,…,bn стають коефіцієнтами цільової функції двоїстої задачі.
Матрицю обмежень двоїстої задачі отримують транспонуванням матриці обмежень прямої задачі.
Число змінних двоїстої задачі рівне числу обмежень прямої, а число обмежень двоїстої рівне числу змінних прямої, і навпаки.
Взаємно однозначна відповідність між змінними прямої задачі і обмеженнями двоїстої:
j-е обмеження двоїстої задачі буде нерівністю, якщо на j-у змінну прямої задачі накладена вимога невід’ємності, а в іншому випадку – j-е обмеження буде рівністю.
1.3 Приклади запису двоїстих умов
№1
№2
2. Розв`язування задачі
2.1 Індивідуальне завдання
Завдання:(83)
F(x1,x2) = 6x1 -4x2 -> max;
5x1 + 2x2 >=10,
2x1 + 5x2 >=10,
-2x1 + x2 <=4,
6<=x1>= 0, 6<=x2 >= 0.
2.2 Графічний метод рішення прямої задачі (ОДЗ, градієнт, мах(х1,х2), мін(х1,х2))
/
/
2.3 Симплекс-метод рішення прямої задачі (пакет SimplexWin)
Крок 0
Базис
БП
x1
x2
x3
x4
x5
x6
x7
z1
z2
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
Базис
БП
x1
x2
x3
x4
x5
x6
x7
z1
z2
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
Базис
БП
x1
x2
x3
x4
x5
x6
x7
z1
z2
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
Базис
БП
x1
x2
x3
x4
x5
x6
x7
z1
z2
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
Базис
БП
x1
x2
x3
x4
x5
x6
x7
z1
z2
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
X=(6,0,20,2,16,0,6);
F(max)=6*6=36;
2.4 Запис умов двоїстої задачі і її рішення симплекс-методом (пакет SimplexWin)
Умова двоїстої задачі буде виглядати так:
-5y1-2y2-2y3+y4>=6;
2y1+5y2-y3-y5,=4;
-10y1-10y2+4y3+6y4+6y5 -> min
Крок 0
Базис
БП
y 1
y 2
y 3
y 4
y 5
y 6
y 7
y 8
y8
6
-5
-2
-2
1
0
-1
0
1
y7
4
2
5
-1
0
-1
0
1
0
КР
6M
10-5M
10-2M
-4-2M
-6+M
-6
-M
0
0
Оскільки немає від`ємних елементів в кінцевому рядку, значить план оптимальний
Y=(0,0,0,6,0)
F(Y)=6*6=36;
3.Висновок:
На даній лабораторній роботі я навчився складати та розв’язувати двоїсту задачу лінійного програмування.
06.12.2015 15:12-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора