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

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

Выберем какой-нибудь базисный минор матрицы А. Для определённости будем считать, что он соответствует первым Г столбцам и строкам этой матрицы. Если Г<m, то уравнения с номерами i = Г+1,..., m, являющиеся следствием остальных уравнений системы, отбросим, в дальнейшем Г=m.

Для решения системы уравнений относительно базисных переменных x_j, j=1,..., m, с помощью преобразований приведём её к виду:

x₁ + a⁽⁰⁾_1,m+1x_m+1+...+a⁽⁰⁾_1,nx_n = b₁⁽⁰⁾,

x₂ + a⁽⁰⁾_2,m+1x_m+1+...+a⁽⁰⁾_2,nx_n = b₂⁽⁰⁾,

.................................................................. (1)

x_m + a⁽⁰⁾_m,m+1x_m+1+...+a⁽⁰⁾_m,nx_n = b_m⁽⁰⁾,

тогда общее решение системы запишется:

x₁ = b₁⁽⁰⁾ - a⁽⁰⁾_1,m+1x_m+1 -...- a⁽⁰⁾_1,nx_n,

x₂ = b₂⁽⁰⁾ - a⁽⁰⁾_2,m+1x_m+1 -...- a⁽⁰⁾_2,nx_n,

................................................................. (2)

x_m = b_m⁽⁰⁾ - a⁽⁰⁾_m,m+1x_m+1 -...- a⁽⁰⁾_m,nx_n,

где свободные переменные x_m+1,..., x_n могут принимать произвольные значения.

Положив их равными нулю, получим частное решение:

x₁ = b₁⁽⁰⁾, x₂ = b₂⁽⁰⁾,..., x_m = b_m⁽⁰⁾, x_m+1 = x_m+2 =...= x_n = 0 или

x⁽⁰⁾ = (b₁⁽⁰⁾, b₂⁽⁰⁾,..., b_m⁽⁰⁾, 0, 0,...,0). (3)

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

b_i⁽⁰⁾ ³ 0, i = 1,...,m,

то такое решение называют допустимым базисным решением или угловой точкой допустимого множества D задачи линейного программирования. Если среди неотрицательных чисел b_i⁽⁰⁾ в (3) есть равные 0, то допустимое базисное решение называют вырожденным (вырожденной угловой точкой), а соответствующая задача линейного программирования также называется вырожденной.

В основе симплекс-метода лежит следующий факт:

Если задача линейного программирования разрешима, то минимум целевой функции f(`x) достигается хотя бы в одной из угловых точек допустимого множества D этой задачи.

Так как различные базисные решения соответствуют различным вариантам выбора m базисных из общего числа n переменных x_j, то чиcло допустимых базисных решений (угловых точек) не превышает C_n^m. Поэтому задачу линейного программирования можно решеть посредством перебора конечного числа угловых точек допустимого множества D, сравнивая значения целевой функции в этих точках. Однако при большой размерности n задачи линейного программирования этот подход затруднителен. Идея симплекс-метода состоит в направленном переборе угловых точек допустимого множества D с последовательным уменьшением целевой функции f(`x).

ОПИСАНИЕ СИМПЛЕКС - МЕТОДА

Предположим, что задача линейного программирования является невырожденной, а базисное решение допустимым. Используя соотношение (2), выразим целевую функцию через свободные переменные x_j, j = m+1,..., n

(4)

где

Справедливы следующие утверждения:

а) если в выражении (4) все коэффициенты p_j⁽⁰⁾, j = m+1,..., n

неотрицательны, то в угловой точке (3) достигается минимум целевой функции f(`x) на допустимом множестве D и этот минимум равен p₀⁽⁰⁾;

б) если среди отрицательных коэффициентов p_j⁽⁰⁾, j ¹ 0, из (4) есть такой (например p_a⁽⁰⁾), что в (1) все коэффициенты a_il⁽⁰⁾ £ 0, i = 1,..., m, то целевая функция f(`x) не ограничена снизу на допустимом множестве D и задача не имеет решений.

в) если хотя бы один из коэффициентов p_j⁽⁰⁾, j ¹ 0, из (4) отрицателен (например, p_l⁽⁰⁾ < 0) и при этом среди коэффициентов a_il⁽⁰⁾ в (1) есть хотя бы один положительный, то существует угловая точка `x<sup>(1)</sup> множества D такая, что f(`x⁽¹⁾) < f(`x⁽⁰⁾).

В случаях а) и б) процесс решения задачи линейного программирования на этом заканчивается. Рассмотрим подробнее случай в). Пусть в (4) коэффициент p_l⁽⁰⁾ < 0 и в (1) имеются положительные коэффициенты a_il⁽⁰⁾. Найдём номер k базисной переменной из условия.

(5)

где минимум берётся по всем номерам i = 1,..., m, для которых a_il⁽⁰⁾ > 0.

Найдём решение системы ограничений, считая свободными переменные x_m+1,..., x_l-1,..., x_k, x_l+1,..., x_n, т.е. поменяв местами свободную переменную x_l с базисной переменной x_k. Система уравнений (1) в этом случае запишется следующим образом:

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

(7)

Компоненты нового базисного решения `x<sup>(1)</sup> можно найти, приравняв нулю свободные переменные x<sub>j,</sub> j = m+1,..., n, j ¹ l и x<sub>k</sub>, и найдя при этом условии значения базисных переменных из (6). Базисное решение`x⁽¹⁾ является допустимым, т.е. угловой точкой множества D, причём f(`x<sup>(1)</sup>) < f(`x⁽⁰⁾).

По знакам коэффициентов в системе (6) и выражении для целевой функции (7) можно сделать одно из трёх приведённых выше заключений, как это было сделано для угловой точки `x<sup>(0)</sup>. В случае в) следует совершить переход к очередной угловой точке `x⁽²⁾, аналогичный переходу от `x<sup>(0)</sup> к`x⁽¹⁾, и т.д.

Так как число угловых точек допустимого множества D не превышает C_n^m, то случай в) может повторяться конечное число раз, т.е. в результате конечного числа шагов перехода к новой угловой точке будет либо найдено решение задачи, либо сделано заключение о том, что она не имеет решения.

Реализация описанного выше симплекс-метода значительно упрощается при использовании симплекс-таблиц. Записав коэффициенты уравнений (1) и целевой функции (4) соответствующим образом, получим симплекс-таблицу задачи:

Рассмотрим переход от симплекс-таблицы, соответствующей угловой точке x⁽⁰⁾, к симплекс-таблице для угловой точки `x⁽¹⁾.

Пусть номера k и l определены так, как это сделано выше. Элемент a⁽⁰⁾_k,1, а также строка и столбец на пересечении которых он стоит, называется разрешающими или опорными. Из формул (6) и (7) следует, что преобразование исходной симплекс-таблицы с опорным элементом a⁽⁰⁾_k,1 приводит к новой симплекс-таблице, для определения элементов которой необходимо выполнить следующие опреации:

1) Поменять местами переменные x_k и x_l, остальные переменные оставить на прежних местах.

2) На место опорного элемента поставить число 1/a⁽⁰⁾_k,1.

3) На остальных местах разрешающей строки записать соответствующие элементы исходной таблицы, делённые на опорный элемент.

4) На свободные места разрешающего столбца поставить со знаком минус соответствующие элементы исходной таблицы, делённые на опорный элемент.

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

Пример. Решить задачу симплекс методом:

f(`x) = x₁+ 9x₂ +5 x₃ +3x₄ + 4x₅+ 14x₆ ® min

x₁ + x₄ = 20

x₂ + x₅ = 50

x₃ + x₆ =30

x₄ + x₅+ x₆=60

x_j ³0_, j = 1,..., 6.

Столбцы 2, 4, 5 и 6 матрицы А образуют базисный минор. С помощью эквивалентных преобразований приводим эту систему к виду (1), где базисными являются переменные x₂, x₄, x₅, x₆.

x₂ + x₁ + x₃ = 40 (8)

x₄ + x₁ = 20

x₅ - x₁ – x₃ = 10

x₆ + x₃ = 30

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

f(`x) = 880 - 7x₁ - 14x₃ (9)

Так как min (40/1; 30/1) = 30/1, то разрешающей является строка, соответствующая базисной переменной x_6.

Ответ: `x<sup>*</sup> = `x⁽²⁾ = (10; 0; 30; 10; 50; 0). f^* = 390.

ЛЕКЦИЯ №4.

ТИПОВЫЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

ЗАДАЧА ПЛАНИРОВЫАНИЯ ПРИ ОГРАНИЧЕНИЯХ НА РЕСУРСЫ

Задача. У предприятия есть m видов ресурсов (сырье, оборудование, рабочая сила и т.д), каждый в количестве b_i единиц, i=1,2,…,m. Предприятие выпускает n видов продукции, a_ij – количество единиц i-того вида ресурса, необходимого для выпуска единицы j-той продукции. Прибыль от одной единицы j-той продукции равна С_j,$, а затраты на ее выпуск - S_j, $. Продукции j-того вида надо выпустить не менее P_j единиц. Единица j-той продукции содержит V_kj единиц k-го потребительского свойства (калорийность или содержание определенных питательных веществ в производимых продуктах питания, производительность выпускаемых средств и т.д), которого во всей выпускаемой продукции должно быть не менее r_k единиц, k=1,2,…,l. Определить количество выпускаемой продукции каждого вида, при котором суммарная прибыль максимальна либо минимальны затраты.

Решение. Следует помнить, что при составлении любой, не только линейной, модели параметрической оптимизации необходимо выполнить три этапа:

1) Определить, значения каких параметров надо найти (что является входными параметрами) и обозначить их через х₁, х₂,…, х_n.

2) Записать выражение для целевой функции через х₁, х₂,…, х_n.

3) Записать выражения для ограничений через х₁, х₂,…, х_n.

Для задачи планирования имеем:

1) Обозначим х_j – объем выпуска j-той продукции (j=1,2,…,n).

2) Целевая функция – прибыль или затраты. От одной единицы 1-ой продукции прибыль составит С₁, $, а от х₁ единиц – C₁x₁, $. Аналогично, для всех видов продукции суммарная прибыль составит:

Q₁=C₁x₁+C₂x₂+…+C_nx_n→max (1)

Суммарные затраты:

Q₂=S₁x₁+S₂x₂+…+S_nx_n→min. (1^*)

3) Ограничения:

Ограничения на объем выпуска: согласно условию задачи x_j≥P_j.

Ограничения на ресурсы: на одну единицу 1-ой продукции надо затратить a₁₁