Злп имеет минимум и не имеет максимума 1. 6. 12. Злп не имеет решения

Область допустимых решений, изображенная на рис. 1.6.9 и 1.6.10, соответствует одной и той же системе неравенств:

2x₁+x₂ ≥2

х₁+3x₂ ≥3

х₁-х₂ ≥-1

3x₁-x₂ ≤6

х₁+х₂ ≤ 5

_Xl ≥0;x₂ ≥0, но функции, которые максимизируются, отличаются друг от друга:

• в первом случае — F=x₁+2x₂,

• во втором — F= х₁+x₂

Рассмотренные выше примеры показывают, что:

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

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

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

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

Симплексный метод решения ЗЛП

Графический метод непригоден для решения ЗЛП, у которых количество переменных n > 3. Решение таких задач требует применения аналитических методов. Для решения ЗЛП созданы специальные методы решения, одним из которых является симплекс-метод. Оптимальные решения задачи линейного программирования связаны с угловыми точками многогранника решений. Угловых точек может быть много, если много ограничений. Количество угловых точек соответствует количеству базисных решений. Для каждого базисного решения однозначно определяется значение целевой функции.

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

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

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

Симплекс-метод может быть интерпретирован геометрически как движение по соседним угловым точкам многогранника решений. Точки называются соседними, если они расположены на одном ребре. Например, если исходное базисное решение (исходный базисный план) соответствует угловой точке А, то следующий базисный план, полученный в процессе решения задачи симплекс-методом, будет соответствовать угловой точке 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₁, х₂

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

Базисные неизвестные	Свободные члены	X1	X2	X3	X4	X5	X6
X3
X4
X5
X6
-Z

Воспользуемся алгоритмом симплекс-метода. Замечаем, что в последней строке таблицы имеется 2 положительных элемента, выберем наибольший из них (помечен стрелкой), разделим свободные члены на соответствующие положительные числа из выделенного столбца, выбираем наименьшее частное из 6, 16, 5 и выделяем разрешающий элемент (на пересечении строки. X₅ и столбца X₂). В новый базис вместо неизвестного X₅ войдет неизвестное X₂. Поскольку разрешающий элемент уже равен единице, выделенную строку без изменений переписываем на прежнее место в новую таблицу. Остальные строки преобразовываем в соответствии с алгоритмом так, чтобы в соответствующих клетках столбца X₂ появились нули (так, например, при преобразовании первой строки она предварительно складывается с уже переписанной третьей, умноженной на —3).

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

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

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

Базисные неизвестные	Свободные члены	X1	X2	X3	X4	X5	X6
X3						-3
X4						-1
X2
X6
-Z	-15					-3

Замечаем, что в последней строке таблицы имеется 1 положительный элемент, пометим столбец X₁ стрелкой. К новой таблице снова применяем симплекс-алгоритм, начиная с п. 1. Разделим свободные члены на соответствующие положительные числа из выделенного столбца, выбираем наименьшее частное из 3; 5,5; 7 и выделяем разрешающий элемент (на пересечении строки X₃ и столбца X₁)._. В новый базис вместо неизвестного x₃ войдет неизвестное X₁. Поскольку разрешающий элемент уже равен единице, выделенную строку без изменений переписываем на прежнее место в новую таблицу. Остальные строки преобразовываем в соответствии с алгоритмом так, чтобы в соответствующих клетках столбца X₁ появились нули.

Базисные неизвестные	Свободные члены	X1	X2	X3	X4	X5	X6
X1						-3
X4				-2
X2
X6				-3
-Z	-21			-2

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

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

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

В последней строке таблицы имеется 1 положительный элемент, пометим столбец X₅ стрелкой. К новой таблице применяем симплекс-алгоритм. Разделим свободные члены на соответствующие положительные числа из выделенного столбца, выбираем наименьшее положительное частное из -1; 1; 5; 12/9 и выделяем разрешающий элемент (на пересечении строки X₄ и столбца X₅)._. В новый базис вместо неизвестного x₄ войдет неизвестное X₅. Разрешающий элемент не равен единице, поэтому выделенную строку делим на его значение (5) и переписываем на прежнее место в новую таблицу. Остальные строки преобразовываем в соответствии с алгоритмом так, чтобы в соответствующих клетках столбца X₅ появились нули.

Базисные неизвестные	Свободные члены	X1	X2	X3	X4	X5	X6
X1				-1/5	3/5
X5				-2/5	1/5
X2				2/5	-1/5
X6				3/5	-9/5
-Z	-24			-4/5	-3/5

 

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

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

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

является оптимальным. Соответствующее значение целевой функции Z= 24. Таким образом, задача решена.