АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология

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

Решим следующую задачу:

max -5х₁ + 2х₃

-5х₁ - х₂ + 2х₃ £ 2

-х₁ + х₃ + х₄ £ 5

-3х₁ + 5х₄ £ 7

х_1-4 ³ 0

Приведем ее к канонической форме.

max -5х₁ + 2х₃

-5х₁ - х₂ + 2х₃ + х₅ = 2

-х₁ + х₃ + х₄ + х₆ = 5

-3х₁ + 5х₄ + х₇ = 7

х_1-7 ³ 0

Теперь пример имеет вид задачи (14) с той разницей, что единичные вектора стоят не при первых трех, а при последних трех переменных - х₅, х₆ и х₇; но изменять обозначения не имеет смысла.

Для удобства дальнейших рассуждений ограничения пронумеруем. При этом обозначим значение целевой функции (-5х₁ + 2х₃) = z и припишем к системе новое (четвертое) ограничение, после чего задача примет следующий вид:

max z

1) -5х₁ - х₂ + 2х₃ + х₅ = 2

2) -х₁ + х₃ + х₄ + х₆ = 5

3) -3х₁ + 5х₄ + х₇ = 7

4) z + 5х₁ - 2х₃ = 0

х_1-7 ³ 0

Решений такой системы бесконечно много.

При последних трех переменных (дополнительных) стоят единичные столбцы: А₅ = , А₆ = и А₇ = . Поэтому удобно взять переменные х₅, х₆ и х₇ в качестве базисных. Приравняем их к свободным членам, а остальные – к нулю. Таким образом мы получим исходный опорный план - одно из решений этой системы - Х^о =
= (0; 0; 0; 0; 2; 5; 7).

На этом плане значение целевой функции z^о = 0 (-5*0 +
+ 2*0 = 0). Отметим, что в системе (15) столбец коэффициентов при переменной z тоже единичный ( - она входит только в ограничение (4) с коэфициентом 1). Она тоже приравнивается к свободному члену – 0.

Является ли план Х^о оптимальным? Чтобы ответить на этот вопрос, попытаемся увеличить значение целевой функции z. Переменная z входит в ограничение (4). Если в ограничении (4) увеличивать z, то остальные слагаемые (5х₁ - 2х₃) необходимо уменьшить. Это можно сделать либо за счет уменьшения х₁ (при этой переменной стоит положительный коэффициент 5), либо увеличения х₃ (при этой переменной стоит отрицательный коэффициент -2). Однако уменьшить переменную х₁ нельзя, так как она небазисная и равна нулю (а отрицательные значения переменные задачи принимать не могут). Поэтому следует увеличить х₃. Эту переменную увеличить можно, при этом z возрастет. Следовательно, оптимальный план еще не найден.

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

До какого значения можно увеличивать переменную х₃, и какую переменную следует вывести из базиса? Чтобы ответить на этот вопрос, следует проанализировать остальные ограничения задачи.

В ограничение (1) входит базисная переменная х₅. Если уменьшить ее до нуля, то, учитывая, что небазисные переменные х₁ = х₂ = 0, получим 2х₃ =
= 2 Û х₃ = 2/2 = 1. Следовательно, ограничение (1) позволяет увеличить х₃ до 1 (за счет уменьшения х₅).

Аналогично ограничение (2) позволяет увеличить х₃ до 5 (за счет уменьшения х₆).

В ограничение (3) переменная х₃ вообще не входит, следовательно, оно позволяет увеличивать значение этой переменной до бесконечности.

Таким образом, самым жестким ограничением является первое, и мы увеличим х₃ только до 1 (если попытаться увеличить эту переменную до большего значения, то придется уменьшить переменную х₅ до отрицательных значений, иначе ограничение (1) не будет выполняться).

Следовательно, в в новом опорном плане переменная х₃ станет базисной, а х₅ из базиса выйдет. Преобразуем систему методом Гаусса таким образом, чтобы перейти к новому опорному плану. В новой системе столбец коэффициентов при х₃ станет единичным, причем единица должна стоять именно в первом ограничении, а в остальных – нули (тогда при ненулевых компонентах опорного плана снова будут линейно независимые столбцы коэффициентов - единичные).

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

Чтобы получить на месте разрешающего элемента единицу, надо обе части первого ограничения разделить на этот элемент, т.е. на 2. После этого ограничение примет вид (1`).

В ограничение (2) переменная х₃ входит с коэффициентом 1. На месте этого коэффициента необходимо получить ноль. Для этого вычтем из ограничения (2) ограничение (1`), в которое х<sub>3</sub> входит теперь именно с коэффициентом 1. Результат обозначим (2`).

Ограничение (3) можно оставить без изменений, так как коэффициент при х₃ в нем и так нулевой. В новой системе обозначим его (3`).

В ограничение (4) переменная х₃ входит с коэффициентом -2. Умножим обе части ограничения (1`) на -2. Теперь переменная х<sub>3</sub> входит в него не с коэффициентом 1, а с коэффициентом -2. Вычтем из уравнения (4) полученное уравнение, при этом коэффициент при х<sub>3</sub> станет нулевым. Результат обозначим (4`).

Преобразованная система примет вид:

1`) -2,5х₁ – 0,5х₂ + х₃ + 0,5х₅ = 1

2`) 1,5х₁ + 0,5х₂ + х₄ - 0,5х₅ + х₆ = 4

3`) -3х₁ + 5х₄ + х₇ = 7

4`) z – х₂ + х₅ = 2

х_1-7 ³ 0

Этой системе можно поставить в соответствие новый опорный план, приравняв базисные переменные х₃, х₆ и х₇ к свободным членам, а остальные – к нулю: Х⁽¹⁾ = (0; 0; 1; 0; 0; 4; 7).

Значение целевой функции увеличилось: z⁽¹⁾ = 2. Это число является свободным членом ограничения (4`). В самом деле, так как небазисные переменные х<sub>2</sub> = х<sub>5</sub> =0, то из (4`) z = 2 (z - 0 + 0 = 2). Подстановкой плана в целевую функцию можно получить тот же результат
(-5*0 + 2*1 = 2).

Из ограничения (4`) видно, что план Х⁽¹⁾ тоже не является оптимальным. Значение z можно еще увеличить за счет увеличения х₂.

Чтобы определить, до какого значения можно увеличить переменную х₂, и какую переменную следует вывести из базиса, снова по очереди рассмотрим ограничения.

В ограничение (1`) х₂ входит с отрицательным коэффициентом -0,5. Следовательно, при увеличении х₂ значение базисной переменной х₃, входящей в это ограничение, тоже будет увеличиваться (и это увеличение может происходить до бесконечности).

В ограничение (2`) входит базисная переменная х<sub>6</sub>. Если уменьшить ее до нуля, то, учитывая, что небазисные переменные х<sub>1</sub> = х<sub>4</sub> = х<sub>5</sub> = 0, получим 0,5х<sub>2</sub> = 4 Û х<sub>2</sub> = 4/0,5 = 8. Следовательно, ограничение (2`) позволяет увеличить х₂ до 8 (за счет уменьшения х₆).

В ограничение (3`) переменная х₂ вообще не входит, следовательно, и оно позволяет увеличивать значение этой переменной до бесконечности.

Таким образом, самым жестким ограничением является второе, и мы увеличим х₂ до 8.

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

Для этого обе части ограничения (2`) разделим на 0,5 (результат обозначим (2``)).

Из ограничения (1`) вычтем уравнение (2``), умноженное на (-0,5) (поскольку в ограничении (1`) в разрешающем столбце стоит именно
(-0,5), а надо получить 0). Результат обозначим (1``).

Третье ограничение оставим без изменений, обозначив (3``) (поскольку х₂ в это ограничение не входит).

Из ограничения (4`) вычтем уравнение (2``), умноженное на (-1) (поскольку в ограничении (4`) в разрешающем столбце стоит именно
(-1), а надо получить 0). Результат обозначим (4``).

1``) -х₁ + х₃ + х₄ + х₆ = 5

2``) 3х₁ + х₂ + 2х₄ - х₅ + 2х₆ = 8

3``) -3х₁ + 5х₄ + х₇ = 7

4``) z + 3х₁ + 2х₄ + 2х₆ = 10

х_1-7 ³ 0

Этой системе можно поставить в соответствие новый опорный план Х⁽²⁾ = (0; 8; 5; 0; 0; 0; 7). Значение целевой функции увеличилось: z⁽²⁾ = 10.

Из ограничения (4`) видно, что значение целевой функции увеличить больше нельзя. Для этого пришлось бы уменьшить значения переменных х₁, х₄ или х₆, а они и так равны нулю. Следовательно, Х⁽²⁾ – оптимальный план, а 10 – оптимум задачи.

3.2.2 Решение задачи в общем виде. Симплексная таблица

Вернемся к решению задачи в общем виде из раздела 3.2, начиная с исходного опорного плана Х = (b₁, b₂,... b_m, ). Обозначим z целевую функцию задачи. На исходном плане значение целевой функции , так как слагаемые, соответствующие небазисным переменным, обратятся в 0.

Для применения симплекс-метода к системе необходимо приписать еще одно ограничение - критериальное: z - = 0.

В решенном примере это было четвертое ограничение. Поскольку в этом примере базисные переменные исходного опорного плана (х_5-7) не входили в целевую функцию, то и в критериальное ограничение они не вошли. В общем случае это не так. Например, если бы задача имела вид:

max -5х₁ + 2х₃

-2,5х₁ – 0,5х₂ + х₃ + 0,5х₅ = 1

1,5х₁ + 0,5х₂ + х₄ - 0,5х₅ + х₆ = 4

-3х₁ + 5х₄ + х₇ = 7

х_1-7 ³ 0

то в качестве базисных в исходном опорном плане следовало бы взять переменные х₃, х₆ и х₇. Одна из них - х₃ - входит в целевую функцию. Уравнение z - = 0 здесь приняло бы вид: z + 5х₁ - 2х₃ = 0. Чтобы увеличить z, здесь следовало бы увеличить х₃. Но переменная х₃ и так является базисной, уже равна 1, и из ограничений следует, что увеличить ее до большего значения невозможно. Такое затруднение возникло из-за того, что после добавления критериального ограничения столбцы коэффициентов перестали быть единичными. Базисные переменные должны входить в него с нулевыми коэффициентами, а в последней задаче это не так.

Чтобы избежать этого, выразим базисную переменную х₃ из первого ограничения через небазисные (-2,5х₁ – 0,5х₂ + х₃ + 0,5х₅ = 1 Û х₃ = 1 +
+ 2,5х₁ + 0,5х₂ - 0,5х₅) и подставим в целевую функцию: z = -5х₁ + 2х₃ = -5х₁ +
+ 2*(1 + 2,5х₁ + 0,5х₂ - 0,5х₅) = 2 + х₂ - х₅. Теперь уравнение z - = 0 примет вид: z + х₂ - х₅ = 2, т.е. вид уравнения (4`) из системы (16). Рекомендуется сравнить остальные ограничения последней задачи с уравнениями (16): они в точности совпадают; и целевая функция взята из того же примера.

Итак, в общем случае после введения критериального ограничения столбцы при базисных переменных могут перестать быть единичными. Чтобы избежать этого, выразим базисные переменные x_1-m из ограничений через небазисные:

x₁ = b₁ - a_{1 m+1}x_m+1 -... -a_{1 n}x_n

…

x _i = b _i - a _{i m+ 1}x_{m+ 1} -... -a _{i n}x_n

…

x_m = b_m - a_{m m+1}x_m+1 -... -a_{m n}x_n

и подставим их в целевую функцию: z = = c₁(b₁ -
- a_{1 m+1}x_m+1 -... -a_{1 n}x_n) +... + c_m(b_m - a_{m m+1}x_m+1 -... - a_{m n}x_n) + c_m+1x _m+1 +... +
+ c_nx_n.

После приведения подобных членов и переноса свободного члена в правую часть критериальное ограничение примет следующий вид: z + x_m+1(c₁a_{1 m+1} +... + c_ma_{m m+1} - c _m+1) +... + x_n(c₁a_{1 n}+... + c_ma_{m n} - c_n) = c₁b₁ +
+... + c_mb_m; или x_m+1( - c_m+1) + … + x_n( - c_n) = .

Обозначим коэффициенты при переменных x_j в критериальном ограничении - D_j = - c_j; а свободный член этого ограничения - d = .

Отметим, что коэффициенты при базисных переменных в критериальном ограничении будут нулевыми, что и требовалось получить. Но и эти нулевые коэффициенты также можно рассчитать по формулам ( - c_j): поскольку базисные переменные входят лишь в одно ограничение, в этих формулах только одно слагаемое в сумме слева будет ненулевым. Для базисных переменных .

Таким образом, критериальное ограничение примет вид:

z + = d

Теперь исходные данные задачи линейного программирования можно записать в виде симплексной таблицы (таблица 7).

Каждая строка таблицы соответствует одному ограничению задачи линейного программирования ((m+1)-я строка - критериальному ограничению).

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

В правой части таблицы в столбце В указаны свободные члены системы ограничений (в (m+1)-ой строке - значение целевой функции на опорном плане d), а все остальные столбцы соответствуют переменным задачи линейного программирования, и в них указаны коэффициенты при этих переменных в каждом ограничении.

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

Таблица 7 – Симплексная таблица

Идея дальнейшего решения заключается в том, чтобы в критериальном ограничении увеличивать первое слагаемое (z) за счет уменьшения суммы остальных (свободный член - постоянная величина). При этом в той сумме, которую необходимо уменьшить, отличные от нуля коэффициенты стоят только при небазисных переменных (так как базисным соответствуют единичные столбцы). Небазисные переменные равны нулю, их значения можно только увеличивать. При этом увеличиваться должны значения тех небазисных переменных, при которых стоят отрицательные коэффициенты D_j (чтобы сумма уменьшалась)_. Однако увеличение этих переменных ограничивается другими уравнениями системы.

Лемма 1 (критерий оптимальности плана).Если все D_j ³ 0, то текущий опорный план - оптимальный.

Доказательство следует из того, что небазисные переменные равны нулю. Их можно только увеличивать, при этом, так как D_j ³ 0, то целевая функция уменьшается, так как в уравненим (z + = d) значение d - const.

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

В диапазон ячеек D1:К5 введены исходные данные примера. Исходя из них, заполнена вспомогательная часть таблицы в А2:С5. В D6 введена формула =-D1, которая затем скопирована по строке до К6 (таким образом введены свободный член и коэффициенты критериального ограничения).

Таблица 8 – Исходная симплексная таблица

Таким образом, в таблице 8 записана система (15).

Итак, если все D_j ³ 0, то задача решена (это критерий оптимальности для задачи на максимум). Если это не так, необходимо перейти к другому опорному плану. Для этого выберем столбец таблицы, в котором нарушен критерий оптимальности, т.е. некоторый k-й столбец, такой, что D_k < 0. Этот столбец называют разрешающим (очевидно, он не базисный, так как иначе было бы D_k = 0). Преобразуем симплексную таблицу таким образом, чтобы переменная х_к вошла в базис (т.е. в набор базисных переменных), а некоторая другая переменная из него вышла.

В этом примере среди коэффициентов D_j есть отрицательный: D₃ = -2 < 0 (k = 3). Поэтому при преобразовании системы (15) в систему (16) в базис входила переменная x₃. Далее в разделе 3.2.1 мы определяли, какую переменную следует вывести из базиса, и для этого подсчитывали отношения 2/2 и 5/1.

Для выбора переменной, которая должна выйти из базиса, для всех положительных элементов k-го столбца подсчитывают отношения b_i/a_iк и выбирают из них наименьшее. Соответствующую строку (пусть это будет
t-ая строка) также называют разрешающей, а коэффициент а_tk - разрешающим элементом.

В таблице 8 положительные a_iк = a_i3 находятся в первой и второй строках. Наименьшее из отношений b_i/a_iк соответствует первой строке: min {b₁/a₁₃; b₂/a₂₃ } = {2/2; 5/1} = {1; 5} = 1. Таким образом, разрешающая строка - первая, т.е. t = 1. Разрешающий элемент а_tk = а₁₃ = 2. В таблице 8 он выделен заливкой. При преобразовании системы (15) в систему (16) из базиса выходила переменная x₅, которая соответствует первой строке.

Левая (вспомогательная) часть новой таблицы будет отличаться только содержанием t-й строки столбцов х_б и с_б: вместо х_t и с_t там будет стоять соответственно х_к и с_к, так как переменная х_t из базиса выйдет, а х_к войдет.

Правая часть таблицы подвергнется преобразованию методом Гаусса. Цель преобразования - получить единичный столбец при переменной х_к, причем единица должна будет стоять на месте разрешающего элемента, т.е. в t-ой строке. Общие формулы для таких преобразований выглядят следующим образом (со штрихом обозначены элементы новой таблицы):

а_tj`= а_tj / а_tk;

b_t`= b_t / а_tk – вся разрешающая строка делится на разрешающий элемент, при этом на его месте получают 1;

а_ij`= а<sub>ij</sub> - а<sub>tj</sub>`* а_ik = а_ij - а_tj * а_ik / а_tk;

b_i`= b<sub>i</sub> - b<sub>t</sub>`* а_ik = b_i - b_t * а_ik / а_tk – из всех остальных строк вычитают преобразованную разрешающую строку, умноженную на элемент, стоящий в преобразуемой строке в разрешающем столбце (при этом на его месте получают 0, так как из него вычитают его же, умножив на 1);

D_j `= D<sub>j</sub> - а<sub>tj</sub>`* D_k =D_j - а_tj *D_k / а_tk ;

d`= d - b<sub>t</sub>`*D_k = d - b_t * D_k / а_tk – то же самое делают с критериальной строкой.

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

Лемма 2 (о критерии допустимости таблицы). При преобразовании таблицы она сохраняет допустимость, т.е. b_i` ³ 0, "i.

Дата добавления: 2015-01-18 | Просмотры: 815 | Нарушение авторских прав