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

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

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

Если же в Z-строке имеется отрицательный коэффициент, то полу­ченное решение не будет оптимальным. Симплекс-метод определения оптимального решения означает переход от одной вершины многогран­ника решений к соседней этого многогранника, в которой значение це­левой функции Z больше или не меньше, чем в исходной вершине.

Для осуществления такого перехода выполняется шаг модифициро­ванного жорданова исключения. В симплексной таблице разрешающий (ведущий) столбец определяется вводимой переменной, а разрешающую (ведущую) строку предполагают исключаемой переменной. Элемент, на­ходящийся на пересечении разрешающей строки и разрешающего столб­ца, называют разрешающим (ведущим).

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

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

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

Пример 4.3

Для реализации трех видов товаров предприятие располагает тремя видами ресурсов b₁ = 180, b₂ = 50 и b₃ = 40. Для продажи первой группы товаров на одну тысячу рублей товарооборота расходуется ресурсов пер­вого вида в количестве а₁₁ = 3 единицы, ресурсов второго вида а₂₁ = 2 еди­ницы и третьего а₃₁ = 2 единицы. Для продажи второй и третьей групп товаров на 1 тысячу рублей товарооборота расходуется соответственно:

a_2l = 6 единиц, a_l3 = 4 единицы, а₂₂ = 1 единицу, a₂₃ = 2 единицы, а₃₂ =3 еди­ницы, а₃₃ = 1 единицу.

Прибыль, полученная от продажи трех групп товаров на единицу то­варооборота, составляет: с₁ = 6, с₂ = 5 и с₃ = 5.

Определить максимальную прибыль предприятия.

Математическая модель задачи имеет вид:

(4.20)

при ограничениях-неравенствах:

(4.21)

и условиях:

(4.22)

Решение

1. Вводим зависимые переменные y_i ≥ 0 удовлетворяющие условиям:

и перепишем ограничения (4.16) и целевую функцию Z (4.20) в виде:

(4.23)

(4.24)

2. Составляем симплексную табл. №1, включая в нее независимые пере­менные -x₁ -x₂,,-х₃, на верху таблицы, зависимые переменные y₁ ,y_{2 ,}у₃и целевую функцию Z, записывая в левом столбце таблицы с соот­ветствующими знаками у коэффициентов - a_ik. Ограничения на знак в таблицу не включаем.

Первоначальный план (исходное решение) является опорным, так как при х₁ = х₂ = х₃ = 0 (все переменные, расположенные на верху таблицы, равны нулю) и зависимые переменные у₁ = 180, у₂ = 50, у_ъ = 40 удов­летворяют условиям у_i ≥ 0.

3. Определяем оптимальное (максимальное) решение задачи линейного программирования. Находим разрешающий элемент a_rs.В качестве разрешающего выбираем столбец, содержащий наиболь­ший отрицательный по абсолютной величине коэффициент Z-строки, равный «-6». В табл. № 1 указано вертикальной стрелкой. Разрешающую строку определяем из условия min

Такой строкой будет третья (указана горизонтальной стрелкой). Сле­довательно a_rs = а₃₁ = 2.

Выполним шаг модифицированного жорданова исключения с раз­решающим элементом а₃₁ = 2, отмечено квадратиком. Получим табл. №2 в виде:

Разрешающий элемент а₃₁ = 2, заменяем обратной величиной, рав­ной 1/2. Все остальные элементы разрешающего столбца делим на «-2», получаем

Остальные элементы разрешающей строки делим на 2 и получаем:

Все элементы табл. №2 получаем, вычисляя по правилу «прямо­угольника».

Вычисления элементов таблицы запишем по строкам:

Решение, представленное табл. № 2, не является оптимальным, так как в Z-строке имеется отрицательный коэффициент, равный -2. Выпол­ним шаг модифицированного жорданова исключения с разрешающим элементом а₂₃ = 1 (третий столбец — разрешающий, а строка определена из условия min

и получим табл. № 3 в виде:

Вычисления для заполнения табл. № 3 выполняем, начиная с разре­шающих строки и столбца, а затем определяем элементы столбца сво­бодных членов и Z-строки. Так как свободные члены и коэффициенты Z-строки неотрицательны, то решение является оптимальным. Осталь­ные элементы симплекс-таблицы можно не вычислять.

Решение задачи выписываем из табл. № 3:

у₃ = х₂ = у₂ = 0, так как все переменные, расположенные на верху табли­цы равны нулю. Тогда переменные, находящиеся в левом столбце таблицы равны соответствующим значениям свободных членов (элементы в столбце под «1»), то есть

Проверка.

Ответ:

Пример 4.4

Для заданной целевой линейной функции

(4.25)

Найти максимальное значение при линейных ограничениях-неравен­ствах:

(4.26)

и условиях:

(4.27)

Решение

1. Введем зависимые переменные, удовлетворяющие условиям у_i > 0, и перепишем систему ограничений (4.26) и целевую функцию (4.25) в виде:

(4.28)

(4.29)

2. Составляем симплексную табл. № 1, включая в нее зависимые y_jне­зависимые переменные -х_к (4.28) и целевую функцию Z (4.29). Огра­ничения на знак переменных х_к в таблицу не включаем. Номера таб­лиц будем указывать в левом верхнем углу:

Исходный (первоначальный) план является неопорным, так как в третьей строке у_з = -5 (свободный член, т.е. элемент табл. № 1 в столб­це под 1 величина отрицательная).

Полученное решение представлено табл. № 2:

3. Определяем опорное решение, выполняя шаг модифицированного жорданова исключения с разрешающим элементом а₃₃ = -1 выбран­ным в соответствии с правилами, изложенными выше, т.е. в качест­ве разрешающего столбца берем коэффициент в третьей строке (свободный член равен -5) под переменной х₃, а разрешающей будет строка с наименьшим положительным отношением свободных чле­нов к соответствующим коэффициентам разрешающего столбца, т.е.

Решение задачи, представленное табл. № 2, показывает, что план яв­ляется опорным, но неоптимальным, так как в Z-строке все коэффи­циенты отрицательные.

4. Определяем оптимальное решение, выполняя шаг модифицирован­ного жорданова исключения с разрешающим элементом а₂₁ = 1. В ка­честве разрешающего столбца берем наибольший по модулю отрица­тельный коэффициент — 16, т.е. столбец под переменной х₁ (отмечен­ный вертикальной стрелкой), а разрешающей будет строка с единст­венным положительным коэффициентом равным 1. Следовательно, a₂₁ = 1, а решение будет представлено табл. № 3:

Решение задачи, представленное табл. № 3, является оптимальным, так как все коэффициенты Z-строки — положительные величины. Выписываем решения задачи из табл. № 3:

Проверка зависимых переменных и целевой функции:

Пример 4.5

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

(4.30)

удовлетворяющие линейным ограничениям-неравенствам:

(4.31)

и условиям:

(4.32)

Решение

1. Введем зависимые переменные y_t > 0 и ограничения (4.31) перепишем в виде:

2. Составляем симплексную табл. № 1, включая в нее зависимые, неза­висимые переменные и целевую функцию (4.30):

Исключаем из табл. № 1 свободную независимую переменную x_vвы­бирая в качестве разрешающего элемента любой коэффициент в этом столбце (под переменной х_х), так как согласно правилу выбора разрешаю­щего элемента при исключении свободной переменной ограничений на выбор его нет.

Разрешающий элемент отмечен квадратиком, а соответствующие раз­решающие строка и столбец указаны стрелками. Выполним шаг модифи­цированного жорданова исключения с разрешающим элементом а₃₁ = 1 и получаем табл. № 2:

В табл. № 2 вписываем значение для х₁ и вычеркиваем третью строку

(4.33)

Перепишем табл. № 3 в виде:

Решение задачи, представленное табл. № 3, указывает, что получен­ный план является опорным, так как все элементы столбца, расположен­ные под 1, — неотрицательны, но неоптимальны.

Определяем оптимальное решение задачи, выполняя шаг модифици­рованного жорданова исключения с разрешающим элементом а₂₂ = 2. Разрешающим является столбец с коэффициентом -5 в Z-строке, а раз­решающую строку определяем из условия

Так как в случае равенства нулю отношений свободных членов к ко­эффициентам разрешающего столбца в качестве разрешающего элемента берем коэффициент с положительным знаком, получаем табл. № 4:

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

Так как в отношении коэффициент, стоящий в знаменателе, отри­цательный, то в качестве разрешающей строки принимаем третью строку с коэффициента равным 7. Выполним шаг модифицированного жордано­ва исключения с а₃₁ = 7 и табл. № 5 будет иметь вид (вычисляем элементы разрешающего столбца, разрешающей строки, столбца свободных членов и Z-строки. Остальные элементы табл. № 5 можно не вычислять).

План, представленный табл. № 5, является оптимальным. Выписыва­ем решения задачи:

Вычисляем значение свободной переменной х₁ на основании (4.33):

Вычисляем значения зависимых переменных у_{ и целевой функции, подставляя найденные значения в (4.30) и (4.31).

Пример 4.6

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

при линейных ограничениях-неравенствах

(4.34)

и условиях:

(4.35)

(4.36)

Решение

1. Вводим зависимые переменные и перепишем условие задачи (4.34)-(4.36) в виде:

(4.37)

(4.38)

2. Составляем симплексную табл. № 1:

3. Исключаем свободную независимую переменную х₃, выполняя шаг модифицированного жорданова исключения с разрешающим элемен­том а₄₃ = 1. Получаем табл. № 2:

Выписываем значение переменной х₃:

(4.39)

и вычеркиваем четвертую строку в табл. № 2.

Получаем табл. № 3 в виде:

Так как в табл. № 3 в столбце свободных членов два отрицательных элемента -5 и -10, то план неопорный. В качестве разрешающего прини­маем 1 столбец, так как в третьей строке находится элемент с наиболь­шим отрицательным по модулю значением -10 и коэффициент -8 распо­ложен в этом столбце, а разрешающую строку определяем из условия:

Следовательно, выполним шаг модифицированного жорданова ис­ключения с разрешающим элементом а₁₁ = -8, получим табл. № 4:

Решение, представленное табл. № 4, не является опорным, так как в столбце свободных членов имеется отрицательный элемент, равный -5. Выполнив шаг модифицированного жорданова исключения с разрешаю­щим элементом а₃₁ = -1, получим табл. № 5:

Решение, полученное в виде табл. № 5, является опорным, но не оп­тимальным, поскольку в Z-строке коэффициент равный – 15/8 в первом столбце отрицательный, но в этом столбце нет положительных коэффи­циентов. Следовательно, целевая функция ограничений на максимум не имеет.