Математическое программирование: Линейное программирование, постановка задач, методы решения

3X₁  + X₂ ≥ 9

                       X₁  + 2X₂  ≥ 8

             X₁  + 6X₂  ≥ 12 

     Кроме того, переменные x₁  ≥ 0,   x₂  ≥ 0.

     Общая стоимость рациона составит (в  руб.)  F = 4X₁  + 6X₂.

Итак, экономико-математическая модель задачи: составить дневной  рацион X = (X₁, X₂), удовлетворяющий системе  и условию, при котором функция принимает минимальное значение.  

 

Глава 3. Методы решения задач линейного программирования

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

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

     Для того, чтобы решить задачу симплексным  методом необходимо выполнить следующее:

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

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

     Этот  метод является универсальным, применимым к любой задаче линейного программирования в канонической форме. Система ограничений здесь - система линейных уравнений, в которой количество неизвестных больше количества уравнений. Если ранг системы равен r, то мы можем выбрать r неизвестных, которые выразим через остальные неизвестные. Для определенности предположим, что выбраны первые, идущие подряд, неизвестные X1, X2, ..., Xr. Тогда наша система уравнений может быть записана как

       К такому виду можно привести  любую совместную систему, например, методом Гаусса. Правда, не всегда можно выражать через остальные первые r неизвестных (мы это сделали для определенности записи). Однако такие r неизвестных обязательно найдутся. Эти неизвестные (переменные) называются базисными, остальные свободными.

     Придавая  определенные значения свободным переменным и вычисляя значения базисных (выраженных через свободные), мы будем получать различные решения нашей системы  ограничений. Таким образом, можно  получить любое ее решение. Нас будут интересовать особые решения, получаемые в случае, когда свободные переменные равны нулю. Такие решения называются базисными, их столько же, сколько различных базисных видов у данной системы ограничений. Базисное решение называется допустимым базисным решением или опорным решением, если в нем значения переменных неотрицательны. Если в качестве базисных взяты переменные X1, X2, ..., Xr, то решение {b1, b2,..., br, 0, ..., 0} будет опорным при условии, что b1, b2,..., br ≥ 0.

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

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

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

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

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

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

     Таким образом, применение симплексного метода распадается на два этапа: нахождение допустимого базисного решения системы ограничений или установление факта ее несовместности; нахождение оптимального решения.

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

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

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

     Пример: Найдем наибольшее значение линейной функции

L =  6 x₁  + 5 x₂   + 9 x₃

при следующих  ограничениях

      5x₁  + 2 x₂  + 3 x₃  ≤ 25

     x₁  + 6 x₂  + 2 x₃ ≤ 20

     4x₁  +  3 x₃ ≤ 18

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

Свободные члены системы ограничений должны быть неотрицательными. Свободные члены  системы ограничений неотрицательные. Система ограничений должна быть приведена к каноническому виду.

• К левой части неравенства 1 системы ограничений прибавляем неотрицательную переменную x₄ - преобразуем неравенство 1 в равенство.
• К левой части неравенства 2 системы ограничений прибавляем неотрицательную переменную x₅ - преобразуем неравенство 2 в равенство.
• К левой части неравенства 3 системы ограничений прибавляем неотрицательную переменную x₆ - преобразуем неравенство 3 в равенство

 

      5x₁  + 2 x₂  + 3 x₃ + x₄ =25

     x₁  + 6 x₂  + 2 x₃ + x₅=20

     4x₁  +  3 x₃ + x₆= 18

Система ограничений приведена к каноническому  виду, т.е. все условия системы  представляют собой уравнения.

Определимся с начальным опорным решением.

     Наличие единичного базиса в  системе ограничений позволяет  легко найти начальное опорное  решение. Рассмотрим подробнее:

• Переменная x₄ входит в уравнение 1 с коэффициентом 1, а в остальные уравнения системы с коэффициентом ноль, т.е. x₄ - базисная переменная.
• Переменная x₅ входит в уравнение 2 с коэффициентом 1, а в остальные уравнения системы с коэффициентом ноль, т.е. x₅ - базисная переменная.
• Переменная x₆ входит в уравнение 3 с коэффициентом 1, а в остальные уравнения системы с коэффициентом ноль, т.е. x₆ - базисная переменная.
• Переменные, которые не являются базисными называются свободными переменными.

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

X нач  = ( 0 , 0 , 0 , 25 , 20 , 18 )

     Вернемся  к рассмотрению функции L.

L =    6 x₁  + 5 x₂  + 9 x₃

     Функция L не содержат базисных переменных.

     Для составления начальной симплекс таблицы мы выполнили все условия.

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

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

     Шаг 1

     За  ведущий выберем столбец 3 , так  как -9 наименьший элемент в L строке. Элемент L строки, принадлежащий столбцу  свободных членов не рассматриваем.

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

Базисные  переменные	X1	X2	X3	X4	X5	X6	Свободные члены	Отношение
X4	5	2	3	1	0	0	25	25/3
X5	1	6	2	0	1	0	20	10
X6	4	0	3	0	0	1	18	6
L	-6	-5	-9	0	0	0	0	-

Разделим  элементы строки 3 на 3.

Базисные  переменные	X1	X2	X3	X4	X5	X6	Свободные члены	Отношение
X4	5	2	3	1	0	0	25	25/3
X5	1	6	2	0	1	0	20	10
X6	4/3	0	1	0	0	1/3	6	6
L	-6	-5	-9	0	0	0	0	-