Общая постановка задачи линейного программирования. Постановки задачи линейного программирования

Постановки задачи линейного программирования

Линейное программирование

Для изучения данного раздела дисциплины необходимо знание темы 2.

Изучив тему, студент должен:

- знать формы записи ЗЛП, основные определения и свойства ЗЛП;

- уметь использовать графический, симплекс-метод, Р-метод, двухэтапный симплекс-метод решения ЗЛП;

- приобрести навыки решения ЗЛП с помощью MS Excel;

- уметь определять интервалы изменения коэффициентов целевой функции, при которых структура оптимального плана остается неизменной;

- уметь определять интервалы изменения значений констант в правой части ограничений, при которых структура оптимального плана остается неизменной.

Цель изучения –изучение темы «Линейное программирование» должно дать достаточно полное представление о возможностях применения методов линейного программирования и интерпретации получаемых с их помощью результатов.

Линейное программирование – область математики, разрабатывающая теорию и численные методы решения задач нахождения экстремума (максимума или минимума) линейной функции многих переменных при наличии линейных ограничений, т.е. линейных равенств или неравенств, связывающих эти переменные. К задачам линейного программирования приводится широкий круг вопросов планирования экономических и технико-экономических процессов, где ставится задача поиска наилучшего (оптимального) решения; само возникновение и развитие линейного программирования непосредственно связано с экономической проблематикой.

Как показывают приведенные в теме 1 примеры, левая и правая части ограничений линейной модели могут быть связаны знаками «£», «=», «³». Также и переменные, фигурирующие в линейных моделей, могут быть неотрицательными, отрицательными или не иметь ограничений в знаке, поэтому задачи линейного программирования имеют несколько вариантов постановки.

Общая задача линейного программирования (ОЗЛП) может быть сформулирована следующим образом: найти значения переменных Х₁, Х₂,…,Х_n, максимизирующие линейную форму

(x₁,x₂,…,x_n) = c₁x₁+…+c_nx_n (3.1)

при условиях

i = 1,…, m₁ (m₁ £ m), (3.2)

i = m₁ + 1,…, m,

x_j ³ 0, j = 1,…, p (p £ n). (3.3)

Соотношения (3.2) и (3.3) будем называть соответственно функциональными и прямыми ограничениями задачи линейного программирования (ЗЛП).

Значения переменных Х_j (j = 1, 2,…, n) можно рассматривать как компоненты некоторого вектора = (Х₁, Х₂,…, Х_n) пространства Е_n.

Определение. Планом, или допустимым решением, задачи линейного программирования будем называть вектор пространства Е_n, компоненты которого удовлетворяют функциональным и прямым ограничениям задачи.

Множество всех планов задачи линейного программирования (3.1) – (3.3) будем обозначать Р.

Теорема 3.1. Множество планов Р задачи линейного программирования (ЗЛП) есть замкнутое выпуклое множество.

Множество Р может быть как ограниченным, так и неограниченным, кроме того оно может оказаться пустым.

Напомним, что множество точек Р пространства E_n есть выпуклое множество, если вместе с любыми двумя его точками и ему принадлежит и любая выпуклая линейная комбинация этих точек, то есть если , , то и любая точка

, 0 ≤ λ ≤ 1

также принадлежит множеству Р.

Множество точек = (Х₁, Х₂,…, Х_n) пространства E_n, компоненты которых удовлетворяют условию

C₁X₁ + C₂X₂ +…+ C_nX_n = b,

называется гиперплоскостью пространства E_n.

Множество точек = (Х₁, Х₂,…, Х_n) пространства E_n, компоненты которых удовлетворяют условию

C₁X₁ + C₂X₂ +…+ C_nX_n ≤ b (≥ b),

называется полупространством пространства E_n.

Очевидно, что гиперплоскость и полупространство являются выпуклыми множествами пространства E_n.

Напомним, что точка выпуклого множества К является крайней, если в К не существует таких точек и , ≠ , что

, при некотором .

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

Определение. План = (Х₁^*,…Х_n^*) будем называть решением задачи линейного программирования, или ее оптимальным планом, если

.

Определение. Будем говорить, что задача линейного программирования разрешима, если она имеет хотя бы один оптимальный план.

Дата добавления: 2014-12-29