Розв’язання задачі лінійного програмування графічним методом – як проілюстрир
БлогNot. Розв'язання задачі лінійного програмування графічним методом – як проілюстрир.
Розв'язання задачі лінійного програмування графічним методом – як проілюструвати у Mathcad?
Теорію наведено, наприклад, тут (лекція 3). Зазначимо, що найпростішим графічним методом вирішується завдання лише для двох невідомих із лінійною цільовою функцією. Але малювати на папері, що вийшло, мені особисто було б ліньки.
Можна зробити хитрішим і поавтоматизованішим, ніж у прикладі, наприклад, спробувати автоматично штрихувати область допустимих рішень (ОДР), але не ускладнюватимемо просту річ.
Ось яким алгоритмом зробити найзрозуміліше. Візьмемо класичне завдання лінійного програмування (ЛП):
Обмеження на неотрицательность x1 , x2 тривіальні, інші визначимо як функції 2 змінних r1 , r2 , r3 . Для побудови графіків прямих, відповідних цим трьом обмеженням, вирішимо їх щодо змінної x2 як рівності, вийдуть функції f1(x1) , . f3(x1) :
Цільову функцію поставимо як z (x1, x2), визначимо для неї 2 будь-яких різних тестових значення, Level1 і Level2. Вони знадобляться, щоб побачити на графіку напрям зростання функції (векторградієнта, перпендикулярний обом лініям і спрямований від z(x1,x2)=Level1 до z(x1,x2)=Level2) :
Щоб було наочніше, переберемо попарно комбінації обмежень-прямих f1, f2, f3 і підготуємо точки їх перетину P12, P13, P23 для відображення на графіку:
Наступний етап, насправді, буде виконаний після побудови графіка - потрібно підібрати відповідний для відображення області допустимих рішень інтервал [a,b] по осі X, а також будь-яку точку Seed, що лежить усередині багатокутника, утвореного всіма прямими-обмеженнями. Потім для надійності перевіримо, чи всеЧи обмеження нерівності виконуються всередині багатокутника ОДР. Якщо щось виконується, вихідне нерівність дасть значення не 1, а 0, отже, потрібно штрихувати протилежну від Seed бік прямий, багатокутник ОДР виявиться розімкненим. Це ще не означає, що рішення немає, докладніше див. у лекції з першого посилання:
Все готове для побудови графіка, ось яким наочним він може бути:
На першій вкладці властивостей графіка (увійти до цього вікна можна подвійним клацанням за графіком) виставлені лінії сітки, прапорець "В однаковому масштабі" та опція "Відображення осей по центру". Другу вкладку ("Трасування") довелося налаштувати детальніше: криві 1 і 2 - червоні лінії, з товщиною 1 і 2 відповідно, щоб було видно напрям градієнта. Якби завдання було на мінімум, потрібно було б рухатися перпендикулярно до червоних ліній від товстої до тонкої, у нас максимум, значить - від тонкої до товстої. Криві 3-5 – чорні лінії, вони відповідають нашим трьом обмеженням. Графіки 6-8 - крапки із символом "кружок" розміром 3, вони покажуть кути багатокутника ОДР. Графік 9 теж точка, вона зображена фіолетовим квадратиком і контролює, чи правильно ми вибрали Seed. За графіком видно, що рішення - точка P13 = (2,3).
Завантажити цей приклад в архіві .zip з документом Mathcad 15 .xmcd (44 Кб)