Образовательная программа: Вычислительная техника и программное обеспечение 8D06104
жүктеу/скачать 221,11 Kb.
|
- Бұл бет үшін навигация:
- Алгоритм геометрического метода: 1)
| Геометрический метод решения задачи линейного программирования является самым простым и используется в случае, если задача содержит не более двух переменных или может быть сведена к таковой.
Каждое из неравенств системы ограничений геометрически определяет полуплоскость допустимых значений переменных с граничными прямыми. Алгоритм геометрического метода: 1) в системе ограничений знаки неравенств заменяются на знаки точных равенств и по полученным уравнениям строятся прямые на плоскости x1Ox2; 2) определяются полуплоскости – области решения неравенств, и строится многоугольник решений, который получается в результате пересечения полуплоскостей и является ОДР. Стороны этого многоугольника являются прямыми уравнений системы ограничений; 3) из точки (0; 0) строится вектор (c1,c2), направление которого определяет направление возрастания целевой функции ; 4) строится начальная прямая (линия уровня) целевой функции , которую передвигают в направлении вектора до крайней угловой точки многоугольника решений. В этой точке целевая функция принимает max значение; 5) определяются координаты точки максимума целевой функции (x1*, x2*) как точки пересечения соответствующих прямых и вычисляется значение целевой функции в этой точке Fmax(x1*, x2*). В нашем случае для задачи определения оптимального плана производства система уравнений будет иметь вид: Построим по полученным уравнениям прямые и пронумеруем их (рисунок 1). ОДР будет выпуклый многоугольник АBCDEF, каждая вершина которого является опорным планом. Рисунок 1. Иллюстрация графического метода решения задачи ЛП Из точки (0; 0) построим вектор , (c1 , c2 ) = , (4, 5). Начальная линия уровня будет иметь вид: F( ) =4x1 + 3x2 = 0. Перемещая линию уровня вдоль вектора ,, получим, что функция F принимает max значение в точке D – самой крайней справа вершине многоугольника ОДР. Точка D является точкой пересечения прямых (2) и (3). Находим координаты точки D, решая систему уравнений этих прямых: Решением системы будут значения x1 = 9, x2 = 6, то есть D(9; 6). Таким образом, решением задачи будет оптимальный план = (9; 6), дающий максимальное значение функции Fmax( ) = 4x9 + 3x6 = 54 д.ед.. Максимальная прибыль 54 д.ед. достигается при изготовлении 9 единиц изделий I вида и 6 единиц изделий II вида. В данной задаче ОДР является выпуклый многоугольник. Однако возможны и следующие случаи: 1) ОДР – пустое множество. В этом случае задача линейного программирования не имеет решения из-за несовместности системы ограничений; 2) ОДР – единственная точка, которая и будет единственным и оптимальным решением; 3) ОДР – выпуклая неограниченная область. В задаче на max оптимальное решение не существует, если целевая функция не ограничена сверху (Fmax = ∞). В задаче на min оптимальное решение не существует, если целевая функция не ограничена снизу (Fmin = – ∞); 4) может оказаться, что линия уровня целевой функции совпадает с одной из сторон многоугольника ОДР (экстремум целевой функции достигается на всем отрезке между двумя соседними вершинами ОДР). Тогда имеет место Альтернативный оптимум: , где t є [0;1] – параметр. Например, пусть линия уровня функции F(x1,x2) = 2x1+x2 совпадает с границей ОДР – отрезком, координаты вершин которого равны (0; 4) и (2; 0). Тогда решением задачи на min будут два оптимальных решения = (2; 0) , = (0; 4) . При этом = t(2; 0) + (1- t) (0; 4) ; Fmin( = 4 . Рассмотрим еще один пример решения задач геометрическим методом. Математическая постановка основной задачи ЛП состоит в следующем: определение максимального значения функции при условии Запишем задачу в векторной форме. Введем вектора С = (c1, c2, …, cn), X = (x1, x2, …, xn). P0 = (b1, b2, …, bm)т, Р1 = (а11, а21, …, аm1)т, Р2 = (а12, а22, …, аm2)т, … Рn = (a1n, a2n, …, amn)т и скалярное произведение СХ, тогда векторная запись основной задачи состоит в следующем. Найти максимум функции F = CX, (6.5) при условиях х1р1 + х2р2 + … + хnрn = P0 (6.6) x ≥ 0 (6.7) жүктеу/скачать 221,11 Kb. Достарыңызбен бөлісу:
|