Графический метод решения задачи ЛП

Решение задачи линейного программирования графическим методом включает следующие этапы:

1. На плоскости X₁0X₂ строят прямые.

2. Определяются полуплоскости.

3. Определяют многоугольник решений;

4. Строят вектор N(c₁,c₂), который указывает направление целевой функции;

5. Передвигают прямую целевую функцию c₁x₂ + c₂x₂ = 0 в направлении вектора N до крайней точки многоугольника решений.

6. Вычисляют координаты точки и значение целевой функции в этой точке.

Общая и основная задача ЛП. Возможные варианты результата решения задачи ЛП

Общей задачей для линейного программирования является нахождение неотрицательного решения системы линейных ограничений, которое оптимизирует линейную целевую функцию:

 

f(x₁,x₂,…,x_n)=c₁x₁+c₂x₂+…+c_nx_n→ max (min)

 

Выделяют две формы задач линейного программирования:

1.стандартная форма

2.каноническая форма

Планом называется вектор x=(x₁,x₂,…,x_n)Rⁿ, удовлетворяющий условиям (1)-(3). Множество всех допустимых решений задачибудем обозначать через X .допустимое решение xX, при котором целевая функция достигает наибольшего (max) или наименьшего значения (min), называется оптимальным решением задачи линейного программирования. Базисное неотрицательное решение x=(x₁,x₂,…,x_r,0,…,0), где r- ранг системы ограничений, называется опорным решением.

---

Дата добавления: 2018-02-15; просмотров: 515; Мы поможем в написании вашей работы!

Поделиться с друзьями:

---

---

Мы поможем в написании ваших работ!