Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
аришевський С.О „Лінійне програмування” 3
Лекція №7
Тема: Рішення задачі симплекс-методом.
Задача про використання ресурсів.
Модель задачі:
Обмеження на трудові ресурси, напівфабрикати, верстатне устаткування.
Переводимо задачу на min.
І обмеження до канонічного виду:
– додаткові змінні і вони є кращими.
Опорний базисний план .
Будуємо симплексну таблицю відповідно базисному планові.
|
БЗ |
ВБ |
В |
х1 |
х2 |
х3 |
х4 |
х5 |
х6 |
х7 |
|
-40 |
-50 |
-100 |
-80 |
0 |
0 |
0 |
|||
|
x5 |
0 |
100 |
2,5 |
2,5 |
2 |
1,5 |
1 |
0 |
0 |
|
x6 |
0 |
260 |
4 |
10 |
4 |
6 |
0 |
1 |
0 |
|
x7 |
0 |
370 |
8 |
7 |
4 |
10 |
0 |
0 |
1 |
|
Оценки |
ЦФ |
0 |
40 |
50 |
100 |
80 |
0 |
0 |
0 |
|
о |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
Перевіряємо чи є план оптимальним.
Оптимальність плану визначається за допомогою показника оцінки цільової функції , тобто якщо , то план є оптимальним.
Тому що існує оцінки цільової функції , то план не є оптимальним.
У такий спосіб нам необхідно перейти до не гіршого базисного плану , перетворюючи нашу симплексну таблицю.
Виділяємо дозволяючий стовпець.
Критерій вибору рядка, що дозволяє, має вигляд
У такий спосіб дозволяючий рядок буде .
Виділяємо дозволяючий рядок.
|
БЗ |
ВБ |
В |
Х1 |
х2 |
х3 |
х4 |
х5 |
х6 |
х7 |
|
|
-40 |
-50 |
-100 |
-80 |
0 |
0 |
0 |
||||
|
x5 |
0 |
100 |
2,5 |
2,5 |
2 |
1,5 |
1 |
0 |
0 |
50 |
|
x6 |
0 |
260 |
4 |
10 |
4 |
6 |
0 |
1 |
0 |
65 |
|
x7 |
0 |
370 |
8 |
7 |
4 |
10 |
0 |
0 |
1 |
92,5 |
|
Оценки |
ЦФ |
0 |
40 |
50 |
100 |
80 |
0 |
0 |
0 |
У такий спосіб дозволяючим елементом є =2.
А тепер складемо нову симплекс таблицю. Розраховуючи елементи використовуючи правило прямокутника.
І т. д., отримуємо.
|
|
ВБ |
В |
х1 |
х2 |
х3 |
х4 |
х5 |
х6 |
х7 |
|
|
-40 |
-50 |
-100 |
-80 |
0 |
0 |
0 |
||||
|
x3 |
-100 |
50 |
1,25 |
1,25 |
1 |
0,75 |
0,5 |
0 |
0 |
66,6 |
|
x6 |
0 |
60 |
-1 |
5 |
0 |
3 |
-2 |
1 |
0 |
20 |
|
x7 |
0 |
170 |
3 |
2 |
0 |
7 |
-2 |
0 |
1 |
24,3 |
|
Оценки |
ЦФ |
-5000 |
-85 |
-75 |
0 |
5 |
-50 |
0 |
0 |
|
|
о |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
У такий спосіб одержали новий план . Тепер перевіряємо на оптимальність отриманий план .
Тому що , то значить план не оптимальний.
Тепер знайдемо дозволяючий стовпець, це .
А дозволяючий рядком є .
|
|
ВБ |
В |
х1 |
х2 |
х3 |
х4 |
х5 |
х6 |
х7 |
|
-40 |
-50 |
-100 |
-80 |
0 |
0 |
0 |
|||
|
x3 |
-100 |
35 |
1,5 |
0 |
1 |
0 |
1 |
-0,25 |
0 |
|
x4 |
-80 |
20 |
-1/3 |
5/3 |
0 |
1 |
-2/3 |
1/3 |
0 |
|
x7 |
0 |
30 |
16/3 |
29/3 |
0 |
0 |
8/3 |
-7/3 |
1 |
|
Оценки |
ЦФ |
-5100 |
-83,3 |
-83,3 |
0 |
0 |
-46,6 |
-7/3 |
0 |
|
о |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
У такий спосіб ми одержали план .
Перевіряємо його на оптимальність. Звідси випливає, що знайдений план є оптимальним планом.
Перевіримо наше рішення на відповідність нашим обмеженням:
Підставляємо в 1 нерівність , обмеження виконується.
Підставляємо в наступне рівняння , і це обмеження виконується.
І перевіряємо 3 обмеження, , воно виконується.
У такий спосіб рішенням даної задачі є план .
PAGE 1