Математическое программирование

Математическое программирование

Математическое программирование (МП) – это наука, посвященная решению задач, связанных с нахождением экстремумов функций нескольких переменных при наличии ограничений на переменные. Методами математического программирования решаются задачи о распределении ресурсов, планировании выпуска продукции, ценообразовании, транспортные задачи и т.п. В результате решения задач МП находится в общем случае максимум (или минимум) функции при условии, что ее переменные удовлетворяют некоторой системе уравнений и неравенств. Задачи МП делятся на задачи линейного программирования (ЛП) и нелинейного программирования (НЛП). ЛП — это наука о методах исследования и отыскания наибольших и наименьших значений линейной функции, на неизвестные которой наложены линейные ограничения. Наиболее изученным разделом МП является ЛП. Для решения ЗЛП разработаны эффективные методы, алгоритмы и программы.

Понятие модели

Модель — это условный образ объекта, формирующий представление о нем в некоторой форме, отличной от реального существования данного объекта.

Модель какого-либо объекта отображает его основные характеристические свойства в некоторой абстрактной форме. Модель может служить для достижения различных целей:

• познавания объекта или системы;

• прогнозирования поведения объекта;

• принятия наилучших решений для достижения объектом поставленной перед ним цели.

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

Математическая модель экономического объекта — это его отображение в виде совокупности уравнений, неравенств, логических отношений.

Для построения экономико-математической модели используется следующий алгоритм:

1. Формируются предмет и цели исследования.

2. В рассматриваемой экономической системе выделяются определенные элементы, соответствующие данной цели исследования, а также наиболее важные характеристики этих элементов.

3. Словесно описываются взаимосвязи между элементами модели.

4. Вводятся символические обозначения для учитываемых характеристик экономического объекта и формируются, насколько возможно, взаимосвязи между ними.

5. По данной модели проводятся расчеты и анализ полученного решения.

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

Оптимизационные модели

Отличительные признаки оптимизационных моделей:

• наличие одного или нескольких критериев оптимальности (критерий оптимальности — это признак, по которому одно (или множество) решений задачи признается наилучшим); наиболее типичными критериями в экономических оптимизационных задачах являются: максимум дохода или прибыли, минимум издержек, минимальное время для выполнения задания;

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

Математически эти задачи относятся к задачам на условный экстремум. Постановка таких задач, представленных в общем виде, выглядит следующим образом:

• найти условный максимум (или минимум) функции

Y = f(x₁, x₂,...,x_n) → max(min), (1.3.1)

• при условии, что независимые переменные удовлетворяют ограничениям:

G(x₁, x₂,..., x_n) = 0. (1.3.2).

В задаче на экстремум функцию Y=f(x₁, x₂..., х_n) называют целевой, так как ее максимизация или минимизация есть формальное выражение цели (например, максимизация объема производства при фиксированных затратах).

Функцию G называют функцией, задающей ограничения. Если в задаче на экстремум ограничения в виде системы уравнений G(x₁ x₂..... х_n) = 0 заменить на ограничения в виде неравенств и добавить ограничения в виде неотрицательности переменных X₁ ≥ 0, X₂ ≥ 0,... X_n ≥ 0, то получим задачу математического программирования, в которой необходимо:

• найти максимум (или минимум) функции

f(x_1, x_2, ...,x_n) → max(min) (1.3.3)

• при условии, что независимые переменные удовлетворяют системам ограничений:

g₁(x_1, x_2, ...,x_n) ≤ 0

……………………………. (1.3.4)

g_m(x_1, x_2, ...,x_n) ≤ 0

 

x₁ ≥ 0, x₂ ≥ 0,...,x_n ≥ 0. (1.3.5)

В задаче математического программирования функцию f(X₁, X₂..., X_n) также называют целевой функцией; систему неравенств (1.3.4) — специальными ограничениями задачи математического программирования, а неравенства (1.3.5) — общими ограничениями задачи линейного программирования

Задача составления рациона

При откорме каждое животное ежедневно должно получать не менее 9 единиц питательного вещества S _l, не менее 8 единиц вещества S₂ и не менее 12 единиц вещества S₃. Для составления рациона используется два вида корма. Содержание количества единиц питательных веществ в 1 кг каждого вида корма и стоимость 1 кг корма приведены в таблице:

Питательные вещества	Количество единиц питательных веществ в 1 кг корма
	Корм 1	Корм 2
S l
S2
S3.
Стоимость 1 кг корма

Необходимо составить дневной рацион нужной питательности, причем затраты на него должны быть минимальны. Обозначим x_l и x₂ соответственно количество килограммов корма 1 и корма 2 в дневном рационе.

Получим систему ограничений

3 х₁+ х₂ ³ 9

х₁ + 2х₂ ³ 8,

х₁ + 6х₂ ³ 12

х₁ ³ 0, х₂ ³ 0.

Цель задачи: общая стоимость рациона F = 4 х₁ + 6х₂ должна быть минимальной.

Задачу составления рациона можно обобщить, если предусмотреть в рационе т видов питательных веществ в количестве не менее b _i (i = 1,..., т) единиц и использовать nвидов кормов.

Обозначим a _ij (i = 1,..., т; j = 1,..., n) количество единиц i-того питательного вещества, содержащегося в единице j-того корма, С_j — стоимость единицы j-того корма, х _j— количество единиц j-того корма в дневном рационе.

Тогда необходимо найти минимум линейной функции

F = C ₁x_l +… + C _n х_n

при ограничениях

a_llx_l + a₁₂x₂+... + a_lnx_n ³ b₁

a_2lx_l + а₂₂х₂ +... + а_2nх_n ³ b₂

_{…………………………………………….}

a_m1 x_l + а_m2х₂ +... + а_mnх_n ³ b_m

х_j ³ 0. (j= 1,..., n)

b_i ³ 0(i = l,..., m)

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

Пример

Найти решение X*=(x*₁,x*₂), которое удовлетворяет системе неравенств:

a_llx₁+a₁₂x₂ ≤ b₁

a₂₁x₁+a₂₂x₂ ≤ b₂ (1.6.1)

а₃₁х₁+а₃₂х₂ ≤ b₃

_{…………………………………………}

a_m1х₁+а_m2х₂ ≤ b_m

условиям неотрицательности переменных:

х ₁ ≥ 0, х ₂ ≥ 0 (1.6.2)

и которое доставляет оптимальное значение целевой функции:

F = c₁x₁+c₂x₂ —>max(min). (1.6.3)

Применение геометрического метода предполагает использование нескольких этапов.

На первом из них в системе координат X₁OX₂ строится область допустимых решений задачи (ОДЗ). Для этого ка ждое из неравенств системы (1.6.1) заменяем равенством и строим соответствующие этим равенствам граничные прямые: a_ilx₁+a_i2x₂ = b_i (i=l,…, m).

Каждая из этих прямых делит плоскость Х₁ОХ₂ на две полуплоскости (рис. 1.6.1). Для точки (*) А, принадлежащей одной из этих полуплоскостей, выполняется неравенство: a_ilx₁+a_i2x₂ < b_i (i=l,…, m).

для любой (*)В, принадлежащей другой полуплоскости, — противоположное: a_ilx₁+a_i2x₂ > b_i (i=l...m),

а для любой из точек, лежащих на граничной прямой, — уравнение: a_ilx₁+a_i2x₂ = b_i (i=l...m).

Рис. 1.6.1. Построение ОДЗ

Чтобы графически определить, по какую сторону от граничной прямой располагается полуплоскость, содержащая решения, удовлетворяющие рассматриваемому неравенству, достаточно испытать одну какую-либо точку, например точку с координатами (0,0). Если при подстановке ее координат в левую часть неравенства оно удовлетворяется, значит, искомая полуплоскость содержит данную точку и штриховка, выделяющая искомую полуплоскость, обращена в сторону к испытуемой точке.

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

Неравенства x₁≥0 и х₂≥0 также соответствуют полуплоскостям, одна из которых расположена справа от оси ординат, а другая - над осью абсцисс (рис. 1.6.1).

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

Пример. Необходимо построить область допустимых решений, удовлетворяющую системе неравенств:

x₁+х₂≤ 1

x₁-x₂≤ -1

х ₁ ≥ 0, х ₂ ≥ 0

Для этого первое из неравенств обратим в равенство (x₁+х₂= 1) и построим соответствующую ему граничную прямую. Эта прямая проходит через две точки, координаты которых можно определить следующим образом. Положим, x₁=0, тогда получим 0+х₂= 1, т. е., х₂= 1,а если х₂=0, тогда x₁+0= 1, т. е.,x₁=l, следовательно, граничная прямая на рис. 1.6.2 проходит через точки с координатами (0,1) и (1,0).

Чтобы определить; в какой полуплоскости находят решения, удовлетворяющие первому неравенству, подставим точку с координатами (0,0) в первое неравенство 0+0≤ 1 и убедимся, что точка (0,0) ему удовлетворяет. Следовательно, все решения, удовлетворяющие данному неравенству, находятся в той же полуплоскости, что и точка 0, значит, штриховка, выделяющая полуплоскость, содержащую решения, удовлетворяющие первому неравенству, обращена к точке 0. Затем определим полуплоскость, в которой находятся решения, удовлетворяющие второму неравенству. Для этого второе из неравенств обратим в равенство и построим соответствующую этому равенству граничную прямую. С помощью приема, описанного выше, определим точки, через которые проходит граничная прямая; этими точками будут: (x₁=0, х₂=1) и (x₂=0, x₁=-l).

Испытав точку 0, увидим, что штриховка, выделяющая полуплоскость, содержащую решения, удовлетворяющие первому неравенству, обращена в сторону, противоположную от 0.

Выделим полуплоскости, соответствующие неравенствам: x₁ ≥ 0 и х₂ ≥ 0. Полуплоскость справа от оси ординат будет соответствовать неравенству x₁ ≥ 0, а полуплоскость над осью абсцисс — неравенству х₂ ≥ 0. В рассматриваемом примере область допустимых решений состоит из одной точки с координатами (0,1). Рис. 1.6.2. ОДЗ —одна точка

В общем случае область допустимых решений систем неравенств (1.6.1) и (1.6.2) может быть:

1. пустой, что означает несовместимость систем неравенств:

x₁+x₂≤3

x₁-x₂≤4

x₁≥0; x₂≥0

 

Рис. 1.6.3. ОДЗ —пуста

2. одной точкой:

x₁+x₂ ≤l

x₁-x₂ ≤-1

x₁ ≥0; x₂ ≥0

 

Рис. 1.6.4. ОДЗ — одна точка

3. выпуклым многоугольником:

2x₁+x₂ ≥2

x₁+3х₂ ≥3

x₁-x₂ ≥-1

Зх₁-х₂ ≤ 6

x₁+x₂ ≤ 5

x₁≥0;х₂≥0

Рис. 1.6.5. ОДЗ — выпуклый многоугольник

4. неограниченной выпуклой многоугольной областью:

Зх₁-2х₂ ≥-15

4х₁-х₂ ≥20

Зх₁+х₂ ≥30

x₁-2х₂ ≤20

х₁ ≥0;х₂ ≥0

Рис. 1.6.6. ОДЗ — неограниченная выпуклая многоугольная область

 

На втором этапе формируется графическое изображение целевой функции.

Уравнение: c₁x₁+c₂x₂ =L при фиксированном значении L определяет прямую, а при изменении L — семейство параллельных прямых с параметром L. Вектор С=(с₁,с₂), перпендикулярный всем этим прямым, показывает направление возрастания параметра L. Так, на рис. 1.6.7. показаны прямые, соответствующие уравнению 2x₁+3x₂=L при L= -3, 0, 3, 9.

 

Рис. 1.6.7. Графическое изображение целевой функции

Для всех точек, лежащих на одной из этих прямых, функция F принимает одно определенное значение, равное соответствующему значению L. Поэтому рассматриваемые прямые называются линиями уровня для параметра L. Важное свойство линии уровня в том, что при их параллельном смещении в одном направлении уровень (значение L) только возрастает, а при смещении в другом — только убывает.Построим для рассмотренного примера линии уровня и определим направление их возрастания. Чтобы построить вектор C=(c₁, с₂), можно использовать следующий прием: по оси X₁ откладывается значение первой компоненты вектора C₁=2, а по оси Х₂ — значение второй компоненты С₂=3. По найденным координатам строим прямоугольник и находим направление возрастания вектора С. Затем перпендикулярно вектору С строим линии уровня.

Рис. 1.6.8. Определение оптимального решения графическим методом

Построив на одном рисунке (рис. 1.6.8) область допустимых решений, вектор С, и перпендикулярную ему одну из линий уровня, можно путем ее параллельного перемещения в направлении, указанном вектором С (или в противоположном), определить точку в области допустимых значений, которая доставляет максимум или минимум целевой функции. На рис. 1.6.8 видно, что в крайнем положении линия уровня проходит через (*)В. При дальнейшем ее перемещении она уже не будет иметь общих точек с областью допустимых решений. Таким образом, искомое оптимальное решение, которое графически соответствует координатам (*)В, можно найти путем совместного решения системы двух уравнений, соответствующих граничным прямым АВ и ВД. Если при тех же исходных данных требовалось бы достичь минимума функции F, то, очевидно, линию уровня пришлось бы перемещать в направлении, противоположном вектору С. В этом случае оптимальное решение, соответствующее минимуму функции F, определялось бы координатами точки (*)0.

В зависимости от вида области допустимых решений и положения линий уровня возможны следующие случаи:

 

ЗЛП имеет единственное решение 1.6.10. ЗЛП имеет альтернат. оптимум (А и В)

 

Критерий разрешимости ЗЛП

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

Симплекс-метод может быть интерпретирован геометрически как движение по соседним угловым точкам многогранника решений. Точки называются соседними, если они расположены на одном ребре. Например, если исходное базисное решение (исходный базисный план) соответствует угловой точке А, то следующий базисный план, полученный в процессе решения задачи симплекс-методом, будет соответствовать угловой точке Q, а оптимальный — угловой точке Н. Следовательно, количество итераций симплекс-метода зависит от выбора исходного базисного плана и количества угловых точек, встречающихся при движении от исходного плана к оптимальному. Основу алгоритма симплекс-метода составляет последовательность шагов, реализующая охарактеризованный выше переход от одного базисного плана к другому и приводящая либо к оптимальному решению, либо к выводу о том, что задача решения не имеет. Прежде чем решать ЗЛП симплекс-методом, ее необходимо привести к канонической форме. Перейдем к канонической форме с неотрицательными дополнительными переменными для ограничений, целевая функция которой должна быть максимизирована, а система ограничений представлена в виде уравнений. Для этого введем дополнительные неотрицательные переменные в левые части неравенств со знаками «+» или «-» в зависимости от знака неравенств.

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

Базисным (опорным) решением системы m линейных уравнений с n переменными называется решение, в котором все (n-m) неосновных переменных равны нулю. Базисное решение, в котором хотя бы одна из основных переменных равна нулю, называется вырожденным.

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

• необходимо найти все опорные решения (точки многогранника), множество которых является конечным;

• вычислить для каждого из опорных решений значение целевой функции;

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

Рассмотренная схема связана с простым перебором опорных решений, т е в этой схеме не принимается во внимание тот факт, насколько новое испытуемое опорное решение улучшает значение целевой функции и приближает нас к оптимальному решению. Если перебор опорных решений производить направленно, т.е. на каждом из шагов улучшая (или, по крайней мере, не ухудшая) значение целевой функции, то число перебираемых опорных решений можно резко сократить, что приводит к существенному сокращению числа шагов при отыскании оптимума целевой функции. При этом каждое последующее опорное решение выбирается таким образом, чтобы оно было лучше, (или не хуже) предыдущего. Идея симплекс-метода разработана русским ученым Л.В. Канторовичем в 1939 г. На основе этой идеи американский ученый Д. Данциг в 1949 г. разработал симплекс-метод, позволяющий решить любую ЗЛП. В настоящее время на основе этого метода разработан пакет программ, с применением которого решаются задачи линейного программирования.

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

Рассмотрим конкретную задачу. Ее целевая функция имеет вид:

F = 2 х₁ + З х₂ → max

функциональные ограничения представляют собой систему неравенств:

х ₁ + З х ₂ ≤ 18

2 х ₁ + х ₂ ≤ 16

х ₂ ≤ 5

З х ₁ ≤ 21

прямые ограничения заданы неравенствами: х ₁ ≥ 0, х ₂ >0

Требуется найти решение данной задачи линейного программирования симплексным методом.

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

х ₁ + 3 х ₂ + х ₃ = 18

2 х ₁ + х ₂ + х ₄ = 16

х ₂ + х ₅ = 5

3 х ₁ + х ₆ = 21

Все дополнительные переменные введены со знаком «+», т. к. рассматриваемые неравенства имеют знак «≤». Для нахождения первоначального базисного решения разобьем переменные на две группы: основные и неосновные. Базисным решением системы m линейных уравнений с n переменными называют решение, в котором все (n-m) неосновных переменных равны нулю. В качестве основных переменных на первом шаге нужно выбрать такие переменные, каждая из которых входит только в одно уравнение системы ограничений, и при этом нет таких уравнений системы, в которые не входит ни одна из этих переменных. Количество основных переменных равно m. Если выбранные по этому правилу переменные имеют те же знаки, что и соответствующие им свободные члены в правых частях уравнений, то полученное таким образом базисное решение будет допустимым.

Шаг 1. Определим состав основных и неосновных переменных. В соответствии с вышеизложенным правилом:

§ основные переменные: х_з, x₄, х₅, х₆;

§ неосновные переменные: x₁, x₂.

Шаг 2. Теперь, используя систему равенств, выразим основные переменные через неосновные:

х₃=18- x₁- 3х₂ ;

х₄=16-2 x₁-х₂ ;

х₅=5-х₂;

х₆=21-3 х ₁.

Шаг 3. Положив неосновные переменные равными нулю, получим первое базисное решение:

Х¹ =(х₁¹=0, х₂¹=0, х₃¹=18, х₄¹=16, x₅¹=5, x₆¹=21).

Шаг 4. Выразим целевую функцию через неосновные переменные и определим ее значение при выбранном базисном решении:

F ¹ =2x₁+3x₂=0.

Шаг 5. Проверим, доставляет ли выбранное базисное решение оптимум целевой функции F. Для этого воспользуемся критерием оптимальности решения при нахождении максимума целевой функции: если в выражении линейной функции через неосновные переменные отсутствуют положительные коэффициенты при неосновных переменных, то решение является оптимальным.

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

Шаг 6. Сформулируем основное правило перехода к лучшему (не худшему) решению: в новый состав основных переменных вводится та из неосновных переменных, которая имеет наибольший положительный коэффициент в целевой функции. В данном случае это коэффициент при x₂.

Чтобы новое опорное решение, с одной стороны, улучшало (или не ухудшало) значение функции, а с другой — было бы опорным, необходимо определить:

• как должна измениться (увеличиться) переменная х₂, вошедшая в новый состав основных переменных;

• какая переменная из «бывших основных» должна перейти в новый состав неосновных переменных при переходе от одного (старого) базисного решения к другому — новому. Чтобы оценить, в каких пределах возможно изменение переменной х ₂, необходимо определить, при каких значениях х₂ каждая из «старых» основных переменных останется неотрицательной (соблюдение этого условия и делает новое искомое решение допустимым).

Очевидно, что для этого должны выполняться следующие неравенства:

х₃=18 - х₁ - 3х₂ ≥ 0 х₂ ≤ 18/3

х₄=16 - 2х₁ - х₂ ≥ 0 х₂ ≤ 16 (1.1)

х₅=5 - х₂ ≥ 0 х₂≤ 5

х₆=21 - 3х₁ ≥ 0 х₂ — любое число

Каждое из неравенств системы (1.1) определяет возможные границы изменения переменной х₂. В частности, из последнего неравенства системы следует, что переводимая переменная может возрастать неограниченно, т.е. ее граница может быть обозначена как ∞.

Очевидно, что допустимость решения будет обеспечена только в том случае, если будут выполнены все ограничения системы (1.9.1). В свою очередь, это условие будет соблюдаться, если:

x₂ =min { 18/3; 16; 5; ∞ } = 5.

При х₂=5 переменная х₅ обращается в 0 и переходит в разряд неосновных. Уравнение, где достигается наибольшее возможное значение переменной х₂, называется разрешающим. После проделанных преобразований вновь возвращаемся к первому шагу.

Шаг 1. Определяем состав основных и неосновных переменных:

§ основные переменные — x₂,х₃,x₄,x₆;

§ неосновные переменные — x₁,х₅.

Шаг 2. Выразим основные переменные через неосновные, воспользовавшись соотношением из разрешающего уравнения:

х₂ = 5 - х₅ х₂ = 5 - х₅

х₃ = 18- х₁ -3(5 - х₅) х₃ = 3-х₁-3х₅

х₄ = 16 - 2х₁ -(5 - х₅) х₄ = 11- 2х₁ + х₅

х₆=21-3х₁ х₆=21-3х₁

Шаг 3. Положив неосновные переменные равными нулю, получим новое базисное решение:

Х²=(х₁²=0, х₂²=5, х₃²=3, х₄²=11, х₅²=0, х₆²=21).

Шаг 4. Выразим целевую функцию через неосновные переменные, воспользовавшись соотношением из разрешающего уравнения, и определим ее значение при данном базисном решении:

F ² =2x₁+3x₂=2x₁+3(5-x₅) = 2x₁+15-3x₅=15.

Шаг 5. Проверим, доставляет ли выбранное базисное решение оптимум целевой функции. Коэффициент при х₁ в выражении целевой функции положителен, следовательно данное базисное решение не доставляет оптимума целевой функции и необходимо искать новое базисное решение, которое улучшило бы (или, по крайней мере, не ухудшило бы) значение функционала.

Шаг 6. Используя сформулированное выше правило перехода к лучшему решению, введем в новый состав основных переменных х₁

х₂=5 - х₅ ≥ 0 х₁ — любое число

х₃=3 - х₁ + 3х₅ ≥ 0 х₁ ≤ 3

х₄=11 - 2х₁ + х₅ ≥ 0 х₁ ≤ 11/2

х₆=21 - 3х₁ ≥ 0 х₁ ≤ 21/3

x₁=min{∞; 3; 11/2; 21/3 } = 3.

Из разрешающего уравнения следует, что если х₁=3, то х₃=0, следовательно, можно опять вернуться к первому шагу.

Шаг 1. Определим новый состав основных и неосновных переменных:

§ основные переменные: х₁, х₂, х₄, х₆

§ неосновные переменные: х₃, х₅.

Шаг 2. Выразим основные переменные через неосновные, воспользовавшись соотношением из разрешающего уравнения:

х₁=3 - х₃ + 3х₅ х₁=3- х₃+3х₅

х₂ =5 - х₅ х₂ =5-х₅

х₄=11 - 2(3 - х₃ + 3х₅) + х₅ х₄= 5+2х₃-5х₅

х₆=21 - 3(3 - х₃ + 3х₅) = 21 – 9 + 3х₃ - 9 х₅ х₆=12+3х₃-9х₅

Шаг 3. Положив неосновные переменные равными нулю, получим новое базисное решение:

Х³=(х₁³=3, x³₂=5, х₃³=0, х₄³=5, х₅³=0, х₆³=12).

Шаг 4. Выразим целевую функцию через неосновные переменные и определим ее значение при данном базисном решении:

F³ = 2x₁ + 3x₂=2(3 - х₃ + 3x₅) + 3(5 - x₅) = 21 - 2x₃ + 3 x₅ = 21.

Шаг 5. Проверим критерий оптимальности: он опять не выполняется, так как коэффициент при х₅ положителен.

Шаг 6. Вновь используя сформированное выше правило перехода к лучшему решению, введем в новый состав основных переменных х_5.

Определим допустимое изменение х₅ и разрешающее уравнение:

х₁=3 - х₃ + 3х₅ ≥ 0 х₅ ≥ -1

х₂ =5 - х₅ ≥ 0 х₅ ≤ 5

х₄ = 5 + 2 х₃ - 5 х₅ ≥ 0 х₅ ≤ 5/5

х₆= 12+3 х₃-9 х₅ ≥0 х₅ ≤ 12/9

x₅=min{0,5,5/5,12/9}=l

Из разрешающего уравнения следует, что при х₅=1 х₄ = 0, следовательно х₄ переходит в состав неосновных переменых. Вновь возвращаемся к первому шагу.

Шаг 1. Определяем новый состав переменных:

§ основные переменные: х₁, х₂, х₅, х₆,

§ неосновные переменные: х₃, х_4.

Шаг 2. Выразим основные переменные через неосновные. Воспользовавшись разрешающим уравнением х₄=5+2х₃-5х₅,

получаем:

х₅= 1+2/5х₃-1/5x₄

x₁=3-x₃+3(1+2/5х₃-1/5х₄)

х₂=5-1-2/5х₃+1/5x₄

х₆= 12+Зх₃-9(1 +2/5х₃-1 /5х₄)

или после преобразования:

x₁=6+l/5x₃-3/5x₄

х₂=4-2/5х₃+1/5х₄

х₅=1+2/5х₃-1/5х₄

х₆=3-3/5х₃+9/5х₄.

Шаг 3. Положив неосновные переменные равными нулю, получим новое базисное решение:

.Х⁴=(x₁⁴=6, х₂⁴=4, х₃⁴=0, х₄⁴=0, х₅⁴=1, х₆⁴=3).

Шаг 4. Выразим целевую функцию через неосновные переменные и определим ее значение при данном базисном решении:

F⁴₌2x₁₊3x₂=2(6+l/5x₃-3/5x₄) + 3(4-2/5x₃+l/5x₄)=24-4/5x₃-3/5x₄=24

Шаг 5. Используя критерий оптимальности, приходим к выводу, что на этот раз он выполняется и что исследуемое базисное решение является оптимальным

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

Симплекс-таблицы

Ручные вычисления по симплекс-методу удобно оформлять в виде так называемых симплекс-таблиц. Алгоритм симплекс-метода применительно к исходным данным. По исходным данным заполняется начальная симплекс-таблица.

1. Выяснить, имеются ли в последней строке таблицы положительные числа (значение в строке целевой функции не принимается во внимание). Если все числа отрицательны, то процесс закончен; базисное решение является оптимальным; соответствующее значение целевой функции равно исходному значению. Если в последней строке имеются положительные числа, перейти в п. 2.

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

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

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

4. Разделить элементы выделенной строки исходной таблицы на разрешающий элемент (на месте разрешающего элемента появится единица). Полученная таким образом новая строка пишется на месте прежней в новой таблице. Перейти к п. 5.

5. Каждая следующая строка новой таблицы образуется сложением соответствующей строки исходной таблицы и строки, записанной в п. 4, которая предварительно умножается на такое число, чтобы в клетках выделенного столбца при сложении появились нули. На этом заполнение новой таблицы заканчивается, и происходит переход к п. 1.

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

Дана система ограничений X ₁ + З X ₂ ≤ 18

2 X ₁ + X ₂ ≤ 16

Х₂ ≤ 5

3 X ₁ ≤ 21

X ₁ ≥0, Х₂≥0

и целевая функция

Z = 2 Х₁ + З Х₂ → max

Приведем задачу к каноническому виду.

Х ₁ + 3 Х ₂ + Х ₃ = 18

2 Х ₁ + Х ₂ + Х ₄ = 16

Х ₂ + Х ₅ = 5

3 Х ₁ + Х ₆ = 21

X ₁, …, Х₆≥0

Перепишем целевую функцию в виде

–– Z + 2 X₁+3 X₂=0.

Определим состав основных и неосновных переменных. В соответствии с правилом (см. лекцию 1):

§ основные переменные: x₃, x₄, х₅, х₆

§ неосновные переменные: x₁, х₂

Заполним начальную симплекс – таблицу.