Ограничения задачи линейного программирования могут быть уравнениями

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

Итак, повторим, что необходимо для составление математической модели:

• выбор целевой функции
• выбор переменных задачи
• составление системы ограничений

Целевой функцией задачи называют функцию переменных задачи, которая характеризует качество выполнения задачи, и экстремум которой требуется найти. Переменными задачи называются величины x₁, x₂, x_n, которые полностью характеризуют экономический процесс. Системой ограничений задачи называют совокупность уравнений и неравенств, описывающих ограниченность ресурсов в рассматриваемой задаче. В общем случае задача линейного программирования может быть записана в таком виде: (1) a₁₁x₁+a₁₂x₂+…+a_1nx_n ≤ b₁ a₂₁x₁+a₂₂x₂+…+a_2nx_n ≤ b₂ … … …. …. …. ….. …. (2) a_m1x₁+a_m2x₂+…+a_mnx_n ≤ b_m x_j≥0 (j=1,2,…,n), (3) где — заданные постоянные величины, а m>n. Необходимо найти экстремум целевой функции (1) и соответствующие ему переменные x₁, x₂. x_n, при условии, что эти переменные удовлетворяют системе ограничений (2) и условиям неотрицательности (3). Допустимым планом(решением) называется набор значений неизвестных х₁, х₂, …, х_j,…x_n, которые удовлетворяют ее системе ограничений (2) и (3). Множество допустимых решений (планов) задачи образует область допустимых решений (ОДР). Оптимальным решением (планом) задачи линейного программирования называется такое допустимое решение (план) задачи, при котором целевая функция достигает экстремума.

3.Различные формы записи моделей лп. Пример составления математической модели: Задача использования ресурсов (сырья).

Постановка задачи(условие): Для изготовления n видов продукции используется m видов ресурсов 1 . Составить математическую модель. Известны:

• b_i ( i = 1,2,3. m) — запасы каждого i-го вида ресурса;
• a_ij ( i = 1,2,3. m; j=1,2,3. n) — затраты каждого i-го вида ресурса на производство единицы объема j-го вида продукции; a_ij –технологический коэффициент;
• c_j ( j = 1,2,3. n) — прибыль от реализации единицы объема j-го вида продукции.

Требуется составить план производства продукции, который обеспечивает максимум прибыли при заданных ограничениях на ресурсы (сырье). Решение: Введем вектор переменных X=(X₁, X₂. X_j,…,X_n), где x_j ( j = 1,2. n) — объем производства j-го вида продукции. Комментарий: переменные x₁…x_n как мы знаем, являются параметром управления, в данной задаче — это пока неизвестный объём выпускаемой продукции j-го вида. Затраты i-го вида ресурса на изготовление данного объема x_j продукции равны a_ijx_j, поэтому ограничение на использование ресурсов на производство всех видов продукции имеет вид: . Прибыль от реализации j-го вида продукции равна c_jx_j , поэтому целевая функция равна: . Ответ: Математическая модель имеет вид: (4) a₁₁x₁+a₁₂x₂+…+a_1nx_n ≤ b₁ a₂₁x₁+a₂₂x₂+…+a_2nx_n ≤ b₂ … … …. …. …. ….. …. (5) a_m1x₁+a_m2x₂+…+a_mnx_n ≤ b_m x_j≥0 (j=1,2,…,n) (6) Комментарий: (a₁₁,a₁₂,…,a_1n) — использование 1-го вида ресурса на производство всех видов продукции; (a₂₁,a_22,…,a_2n) — использование 2-го вида ресурса на производство всех видов продукции, и т.д. Структурные ограничения (5) отражают требования, которые накладываются на значения переменных (x₁, x₂. x_n) в данном случае — это лимит ресурсов. Если все ограничивающие условия задачи сформулированы в виде неравенств, то говорят, что модель задачи записана в стандартной форме. Запишем эту же мат.модель с помощью знаков суммирования: (7) ) (8) ) (9) В общем случае задача линейного программирования записывается так, что ограничениями являются как уравнения, так и неравенства, а переменные должны быть неотрицательными. В том случае, когда все ограничения являются уравнениями и все переменные удовлетворяют условию неотрицательности, то говорят, что (ЗЛП) задана в канонической форме. Общая задача ЛП может быть представлена в координатной,векторнойиматричной форме записи. Задача линейного программирования в координатной форме записи имеет вид: (10) (11) ). (12) Для матричной формы записи введем обозначения:

• С — матрица-строка коэффициентов при ЦФ;

• А — матрица коэффициентов системы уравнений;
• Х — матрица-столбец переменных задачи;
• В — матрица-столбец правых частей системы ограничений.

C = (c₁, c₂. c_j,…,c_n); , ,. Таким образом, задача линейного программирования в матричной форме записибудет иметь вид: (13) (14) , (15) Для векторной формы записи введем обозначения: C = (c₁, c₂. c_j,c_n) – n-мерный вектор 2 -строка коэффициентов; ; — n-мерные векторы столбцы; -m-мерные векторы, состоящие из коэффициентов при неизвестных в ограничениях (A_j, j=) и свободных членов (B). Тогда мат. модель общей задачи ЛП может быть записана так: (16) (17) (18) Мы рассмотрели математическую модель общей задачи ЛП на максимум и различные формы ее записи. Задачу максимизации линейной функции всегда можно свести к задаче минимизации той же линейной функции со знаком минус, при этом используется соотношение: maxZ= −min(−Z) (19) Из (19) следует, что для сведения задачи на максимум к задаче на минимум достаточно у коэффициентов ЦФ поменять знаки на противоположные и найти минимум полученной функции (−Z). В экономике при неравенствах вида ≤, как правило, формулируются задачи на максимум, а при неравенствах вида ≥, как правило, формулируются задачи наминимум. Различают следующие формы математических моделей общей задачи ЛП в зависимости от соотношений между правыми и левыми частями ограничивающих условий:

• Модели задач в стандартной форме, когда между левой и правой частями ограничений стоит знак неравенства: (≤) Ц.Ф. задана на max,(≥) Ц.Ф. на min.
• Каноническая форма, когда между левой и правой частями ограничений стоит знак равенства, при такой форме ограничений возможна и максимизация, и минимизация целевой функции.
• Смешанная форма, когда одна часть ограничений представлена в виде равенств, а другая — в виде неравенств

Для приведения моделей задач стандартной формы к канонической достаточно в левую часть ограничений ввести дополнительные переменные: х_п+1, х_п+2,.х_п+m. Эти переменные вводятся со знаком «плюс» если между левой и правой частью ограничений стоит неравенство «≤» или со знаком «минус» если стоит неравенство «≥». Подобным образом можно привести к каноническому виду задачи со смешанной системой ограничивающих условий. Дополнительные переменные необходимо ввести также и в целевую функцию задачи с нулевыми коэффициентами, а также в условия неотрицательности переменных. Число вводимых дополнительных неотрицательных переменных при преобразовании ограничений-неравенств в ограничения-равенства равно числу преобразуемых неравенств. Вводимые дополнительные переменные имеют вполне определенный экономический смысл. Так, если в ограничениях исходной задачи линейного программирования отражается расход и наличие производственных ресурсов, то числовое значение дополнительной переменной в плане задачи, записанной в форме основной, равно объему неиспользуемого соответствующего ресурса. Любую задачу линейного программирования можно свести к задаче линейного программирования в канонической форме. Для этого в общем случае нужно уметь сводить задачу максимизации к задаче минимизации; переходить от ограничений неравенств к ограничениям равенств. Пример 1 . Привести задачу к канонической форме записи: Введем дополнительные переменные ,по количеству существующих неравенств в ограничения со знаком (+), а также в ЦФ с нулевыми коэффициентами и в условие неотрицательности переменных: ,что и дает нам задачу в канонической форме. Пример 2. Привести задачу к канонической форме записи: при (ограничениях): , ,

Источник

2.3 Формы записи задач линейного программирования: общая, каноническая и стандартная

Система ограничениями (2.2) задачи линейного программирования может содержать как неравенства, так и уравнения. Различают следующие формы записи ЗЛП:

1. Общаяформа ЗЛП

— это задача максимиза­ции или минимизации линейной функции с линейными ограничениями в виде как равенств, так и неравенств:

1. Каноническаяформа ЗЛП

— это задача максимиза­ции линейной функции с линейными ограничениями в виде ра­венств:

1. Стандартнаяформа записи ЗЛП

– это задача максимизации (минимизации), если все ограничения – неравенства Запишем задачу линейного программирования (стандартная и кононическая формы) в матричном виде: Найти X(), при котором _{если выполняются условия} где: Замечания Указанные формы ЗЛП эквивалентны в том смысле, что каждая из них может быть приведена к любой другой путем несложных тождественных преобразований. Для того чтобы переходить от одной формы записи к другой, нужно уметь преобразовывать задачу минимизации в задачу максимизации и ограничения-равенства к ограничениям-неравенствам (и обратно), а также уметь изменять знаки неравенств на противопо­ложные.

• Задача минимизации (максимизации) функции Z эквива­лентна задаче максимизации (минимизации) функции (-Z),

так как

• Уравнение АX=В эквивалентно двум неравенствам: .
• Переход от неравенств к равенствам может быть легко осу­ществлен путем добавления в неравенства дополнительных пере­менных, которые затем включаются в оптимизируемую функцию с нулевыми коэффициентами.

Например, от неравенства перейдем к уравнению, добавив новую балансовую переменную х_n+1где х_n+10. Таким образом, все операции, необходимые для перехода от одной формы задачи ЛП к любой другой, известны и легко осущест­вимы.

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

При решении ЗЛП графическим методом необходимо, чтобы задача была записана в стандартной форме и переменных в задаче было две . Запишем математическую модель ЗЛП. Найти решение такое, чтобы функция (3.1) достигала экстремума и выполнялись условия: , или , (3.2) а также , или ,(3.3) Алгоритм решения ЗЛП графическим методом:

1. Построить область допустимых решений ОДР,

удовлетворяющую ограничениям (3.2) и (3.3);

1. Построить вектор – градиент целевой функции

1. Построить линию уровня – прямую, перпендикулярную вектору-градиенту ( );
2. Найти:

«точку входа» — minz – первая точка пересечения линии уровня с ОДР, «точку выхода» — maxz – последняя точка пересечения линии уровня с ОДР. Пример 3 Решить графически следующую ЗЛП: найти , если Решение Построим область допустимых решений (ОДР), для этого необходимо построить границы области – прямые: 324,, 6 А l4линия уровня -4 _c1. В 2 _{-3x= 6}Рис.1 Далее строим:

• вектор-градиент ;
• линии уровня , на чертеже эти прямые изображены пунктиром, через начало координат проходит линия уровня, уравнение которой;

Перемещаем линию уровня (прямая l на рис.1) по ОДР (заштрихованная область) в направлении вектора , находим точку «входа» в область — точку А , в которой достигается наименьшее значение целевой функции. Точка А лежит на пересечении прямых 324 ;, чтобы определить ее координаты решим систему уравнений: ; ;Итак, координаты точки А найдены: А(,). Подставляя найденные значения в целевую функцию, получим: =. Перемещая далее линию уровня в направлении вектора , определим точку «выхода» — точкуВ (6; 0). Наибольшее значение функция принимает в точке В (6; 0) и _. В предыдущем примере (примере 3) ЗЛП имела единственное оптимальное решение, на практике встречаются и задачи, которые либо не имеют оптимального решения (примере 4) , либо имеют бесконечное множество оптимальных решений (примере 5). Пример 4 Найти наибольшее и наименьшее значения функции Z = 2х₁+2х₂при ограничениях х₁-3х₂3 -3х₁+х₂3 х₁0, х₂0 РешениеРис. 2 По условию задачи построим ОДР – множество точек области, координаты которых удовлетворяют условиям ограничений (заштрихованная область). Перемещая линию уровня (прямая l на рис.2) в направлении вектора-градиента (2,2), найдем «точку входа» О (0,0), таким образом, Z_min = Z(0) = 0; «Точку выхода» найти невозможно, так как линия уровня всегда будет пересекать ОДР. Итак, оптимального решения, при котором целевая функция достигает максимума, не существует, Z_maxПример 5 (альтернативный оптимум) Найти наибольшее значение функции Z = 2х₁+2х₂при ограничениях х₁+х₂ х₁-2х₂ х₁х₂Решение Построим ОДР Рис. 3 Очевидно, что вектор-градиент (2,2) ортогонален границе области – отрезку АВ. Линия уровняl параллельна стороне (рис.3). Таким образом «точки выхода» — это любые точки отрезка АВ. Точка имеет координаты А( 0,4); координаты точки В найдем из системы: х₁+х₂=4 х₁-2х₂=2 3х₂ = 2; х₂ =; х₁ = 4 —=, итак, В (. Значение целевой функции будет одно и то же в любой точке отрезка АВ, оно равно Z(А) = Z(В) = 2·0 + 2·4 = 8. Данная ЗЛП имеет бесконечно много оптимальных решений х₁ = t х₂ = 4-t где 0 , причемZ_max = 8. Пример 6 Найти Z = х₁ – 2х₂max при ограничениях х₁ + х₂2х₁ + 2х₂х₁х₂0 Решение В данной ЗЛП область допустимых решений представляет собой пустое множество; очевидно, что в этом случае оптимального решения не существует. Рис. 4

Источник