Общая формулировка задач линейного программирования

Общая формулировка задачи линейного программирования

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

Ряд практических задач сводится к смешанным условиям: часть ограничений — линейные уравнения, другие — линейные неравенства. Такое разнообразие форм записи условий задач затрудняет создание и использование общих методов и вычислительных алгоритмов их решения. Поэтому естественно рассмотреть метод и алгоритм решения основной (стандартной) задачи линейного программирования и способы сведения любой задачи линейного программирования к основной форме, которая состоит в следующем. Задана система m линейных алгебраических уравнений с n неизвестными:

(7)

и линейная функция относительно переменных х₁, х₂, ¼, х_n:

(8)

Требуется найти такие неотрицательные значения переменных х₁, х₂, ¼, х_n, которые бы удовлетворяли системе линейных уравнений (7) и, кроме того, обращали в максимум линейную функцию (8).

Заметим, что если по условиям задачи требуется отыскать минимум функции L, записанной в виде (8), то задачу можно свести к задаче максимизации функции L¢, связанной с функцией L так:

L¢ = — L = —c₁x₁ — c₂x₂ — ¼ — c_nx_n. (9)

Максимум функции (9) и минимум функции (8) будут достигаться при одном и том же наборе переменных (х₁, х₂, ¼, х_n), удовлетворяющих условиям неотрицательности переменных и уравнениям (7), областью определения задачи.

Допустимым решением задачи линейного программирования будем называть любую совокупность переменных

х₁ ³ 0, х₂ ³ 0, ¼ , х_n ³ 0, (10)

удовлетворяющих уравнениям (7).

Оптимальным решением будем называть то из допустимых решений, для которого линейная форма L обращается в максимум (минимум).

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

Если число неизвестных в задаче линейного программирования равно двум, т.е. n = 2, то ее можно решить графическим методом. Кроме того, графический метод дает геометрическую интерпретацию решения ЗЛП. В качестве примера рассмотрим частный случай задачи 1, когда комбинат выпускает 2 вида продукции, например, j = 1,2:

1. Булки
2. Пирожные.

Тогда система ограничений на ресурсы будет иметь следующий вид: а₁₁х₁ + а₁₂х₂ £ b₁— ограничение по муке а₂₁х₁+ а₂₂х₂ £ b₂— ограничение по сахару а₃₁х₁+ а₃₂х₂ £ b₃— ограничение по маслу а₄₁х₁+ а₄₂х₂ £ b₄— ограничение по творогу а₅₁х₁+ а₅₂х₂ £ b₅— ограничение по яйцам Используя численные данные а_ij и b_i таблиц 3.2 и 3.3, получим следующую систему неравенств: 0,1×х₁+ 0,04×х₂ £ 200 (1) 0,01×х₁+ 0,05×х₂ £ 50 (2) 0×х₁+ 0,05×х₂ £ 50 (3) 0×х₁+ 0×х₂ £ 50 (4) 0,1×х₁ + 0,2×х₂ £ 500 (5) Так как а₄₁ = 0 и а₄₂ = 0, то вместо пяти осталось четыре неравенства. Превратим эти неравенства в равенства и построим в системе координат х₁, х₂ прямые (1), (2), (3), (5) ограничивающие область допустимых значений неизвестных х₁, х₂, представленную на рис.3.1. Рис. 1 Графическое решение ЗЛП при числе неизвестных n = 2 Для построения прямых (1), (2), (3), (5) используется обычно такой прием. Сначала полагают х₁ = 0 и определяют на оси х₂. Затем полагают х₂ = 0 и определяют на оси х₁. После этого через точки х₁ и х₂ на этих осях проводят прямые. Так для прямой (1) получим: х₁ = 0, , х₂ = 0, . Аналогично построим прямые (2) и (5). Прямая (3) идет параллельно оси х₁ со значением . Из рис.1 следует, что область допустимых значений х₁ и х₂ ограничена многоугольником с вершинами 0,1,2,3, образованного осями координат х₁ и х₂, а также прямыми (1) и (2), т.е. ресурсами мукой и сахаром. Прямые (3) и (5) в данном примере на область допустимых значений х₁ и х₂ не влияют. Целевая функция в задаче 1 при двух видах продукции (булки и пирожное) примет вид D = с₁х₁+ с₂х₂= 0,84х₁+ 3,2х₂ = mах. Для определения оптимальных значений х_1оп и х_2оп, при которых величина D= mах, используем следующий прием: зададим произвольно величину D > 0, например D = 2000, и построим прямую 0,84х₁ + 3,2х₂ = 2000. Она пройдет через точки и на осях x₁ и x₂. На рис. 3.1 эта прямая показана пунктиром. Отметим, что прямая D = 2000 идет круче прямой (2). Если теперь увеличить значение D, например, D = 2500, тогда прямая D = 2500 переместится вверх параллельно прямой D = 2000. Увеличивая таким образом D, мы будем перемещать прямую параллельно самой себе до тех пор, пока она не достигнет верхней точки допустимой области. В данной задаче этой точкой является точка 2 пересечения прямых (1) и (2). Координаты этой точки определим, решив совместно систему из двух уравнений (1) и (2). 0,1×х₁ + 0,04×х₂ = 200 (1) 0,01×х₁ + 0,05×х₂ = 50 (2) Решение этой системы таково х_1оп = 1739, х_2оп = 652. Доход фирмы при таком плане выпуска продукции (в точке 2) составит: D₃ = с₁х_1оп + с₂х_2оп = 0,84×1739 + 3,2×652 = 1460,76 + 2086,4 = 3547,16 (руб). При этом полностью будут израсходованы мука и сахар. Отметим, что при других ценах с₁ и с₂ на продукцию фирмы прямая D= с₁х₁ + с₂х₂ имела бы другой наклон, тогда оптимальное решение могло быть в точках 1 или 3 на рис. 3.1. Однако при ценах с₁ = 0,84 руб и с₂ = 3,2 руб доход фирмы в точках 1 и 3 составит:

• в точке 1, когда изготовляются только пирожные

D₁ = 3,2 × 1000 = 3200 руб.

• в точке 2, когда изготовляются только булки

D₃ = 0,84 × 2000 = 1680 руб. Из приведенных расчетов следует, что доход в точке 2 D₂ = max = 3547,16 руб >D₁ >D₃ , то есть доход фирмы в точке 2 наибольший. Если бы наклон прямой D = с₁х₁ + с₂х₂ совпал бы с наклоном прямой (2), тогда оптимальных планов выпуска продукции было бы множество, а именно: во всех точках на прямой (2) в интервале между точками 1 и 2, включая эти две точки. Попытка решить эту задачу методом производных приведут к следующему абсурдному результату: , т.е. булки и пирожные надо продавать бесплатно, при этом получим D = 0. При трех неизвестных в ЗЛП, когда n = 3, строится трехмерная система координат с взаимно перпендикулярными осями х₁, х₂ и х₃. При этом система неравенств образует трехмерную объемную фигуру — многогранник, а выражение целевой функции D = с₁х₁ + с₂х₂ + с₃х₃ описывает плоскость, наклон которой зависит от значений коэффициентов с₁, с₂ и с₃. Перемещение этой плоскости вверх параллельно самой себе до верхней точки допустимой области определит координаты вершины многогранника х_1оп, х_2оп и х_3оп, где выполняется условие оптимизационной задачи D = max. В принципе можно решить графически ЗЛП при n = 3, но сложно. При числе неизвестных больших трех, т.е. при n > 3 должна быть построена n-мерная система координат, неравенства образуют в гиперпространстве некий гипермногогранник, а целевая функция представляет собой гиперплоскость. Перемещение этой гиперплоскости в гиперпространстве параллельно самой себе приведет до верхней точки гипермногогранника, координаты вершины которого обеспечивают D = max.

Источник

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

Общая задача. Найти максимальное значение линейной целевой функции. z = c₁x₁+ c₂x₂+ … + c_nx_n при линейных ограничениях x_j>= 0,j= 1,n= n> Определение 1.1. Совокупность чисел х = (х₁, х₂. х_n), удовлетворяющих ограничениям (1.2), называется допустимым решением или планом. Определение 1.2. План х* =(х₁ * , х₂ * . х_n*), при котором целевая функция (1.1) принимает свое максимальное значение, называется оптимальным.Каноническая форма. Задачу линейного программирова­ния будем считать приведенной к каноническому виду, если 1) требуется найти максимум целевой функции; 2) система ограничений (1.2) содержи! только равенства; 3) правые части системы ограничений неотрицательны. Переход от общей формы к канонической: 1) если в задаче требуется найти минимум целевой функции, то вводим новую целевую функцию z₁ = -z, тогда max z₁ = -min z; 2) чтобы перейти от неравенства к равенству в системе огра­ничений, необходимо прибавить (вычесть) дополнительную не­отрицательную переменную к левой части неравенства; 3) если в правой части системы ограничений имеются отрица­тельные числа, то необходимо умножить на «-1» обе части равен­ства, в котором в правой части стоит отрицательное число. Задачу линейного программирования в канонической фор­ме называют основной задачей.

Свойства задач линейного программирования. Графический метод решения задач линейного программирования.

Свойства задач линейного программирования. Рассмотрим следующую основную задачу линейного про­граммирования: z = c₁x₁+ c₂x₂+ …+c_nx_nmax при ограничениях , Перепишем ограничения этой задачи к немирной форме: x₁Р,+х₂Р₂+. + х_nР_n,(1.3) где Р₁, . Р_nи Р₀ — k-мерные вектор-столбцы, составленные из коэффициентов при неизвестных и свободных членах системы ограничений основной задачи: Определение 1. План х = (x₁,х₂. х_n) называется опорным планом основной задачи линейного программирования, если его положительные коэффициенты (х_j >0) стоят при линейно независимых векторах Р_j. Так как векторы Р: являются k-мерными, то из определения опорного плана следует, что число его положительных компо­нент не может быть больше числа К. Определение 2. Опорный план называется невырож­денным, если он содержит ровно k положительных компонент, в противном случае он называется вырожденным. Свойства задач линейного программирования тесным обра­зом связаны со свойствами выпуклых множеств. Определение 3. Пусть х(|). х(m) — произвольные точ­ки евклидова пространства Rn . Выпуклой линейной комбинацией этих точек называется сумма: а,х(|) + . + а_mх(m) , где а_i; -про­извольные неотрицательные числа, сумма которых равна 1. Определение 4. Множество называется выпуклым, ес­ли вместе с любыми двумя своими точками оно содержит и отре­зок прямой, соединяющий эти точки. Определение 5. Точка х выпуклого множества назы­вается угловой, если она не может быть представлена в виде вы­пуклой линейной комбинации каких-нибудь двух других различ­ных точек данного множества. Сформулируем первое свойство задач ЛП. Теорема 1.1. Множество планов любой задачи линейного программирования является выпуклым (если оно не пусто). Определение 7. Непустое множество планов задачи линейного программирования называется многогранником реше­ний, а всякая угловая точка многогранника решений — вершиной. Сформулируем второе свойство задач ЛП. Теорема 1.2. Если задача линейного программирования имеет оптимальный план, то экстремальное значение целевая функция задачи принимает в одной из вершин многогранника решений. Если экстремальное значение целевая функция прини­мает более чем в одной вершине, то она принимает его на ребре (грани), содержащем эти вершины. Теорема 1.3. Если система векторов Р₁. Р_m() ли­нейно независима и такова, что х₁Р₁₊. + х_mР_m=Р₀, где все х_j>= 0, то точка х = (х,, х₂. х_т,0. 0) является верши­ной многогранника решений. Теорема 1.4. Если х = (х,,х₂. х_п) — вершина многогран­ника решений, то векторы Р_j , соответствующие положительным х_j > 0, линейно независимы.

Источник

Читайте также:  Машинные языки программирования это