Методы оптимальных решений

Методы оптимальных решений 4. Симплекс-метод 2 4. Симплекс-метод Разработан в 1947 году Джорджем Бернардом Данцигом (на фото). Позволяет решать ЗЛП с любым количеством переменных. Суть симплекс-метода состоит в целенаправленном последовательном улучшении решений с учетом изменений целевой функции. 3 4.1. Постановка задачи Если все ограничения системы заданы уравнениями и переменные неотрицательные, то такая модель задачи линейного программирования (ЗЛП) называется канонической. Если хотя бы одно ограничение является неравенством, то модель задачи не является канонической. Чтобы перейти от неканонической модели к канонической, необходимо в каждое неравенство ввести балансовую переменную. В целевую функцию балансовые переменные не вводятся. Кроме того, если правая часть какого-либо ограничения отрицательна, то обе части данного ограничения необходимо домножить на (-1). Также будем полагать, что целевую функцию необходимо минимизировать. 4 4.1. Постановка задачи Привести ЗЛП к каноническому виду. Z  X   3x1  2 x2  4 x3  min  2 x1  x2  2 x3  2,  3x1  4 x2  4,  2 x  x  x  4, 1 2 3  x1 , x2 , x3  0. Решение. Z  X   3x1  2 x2  4 x3  min  2 x1  x2  2 x3  x4  2,  3x1  4 x2  x5  4, 2 x  x  x  4,  1 2 3 x1 , x2 , x3 , x4 , x5  0. 5 4.1. Постановка задачи В дальнейшем считаем, что математическая модель задачи имеет вид: Z  X   c0  c1x1  c2 x2  ...  cn xn  min a11x1  a12 x2  ...  a1n xn  b1, a x  a x  ...  a x  b ,  21 1 22 2 2n n 2  ..............................................  am1x1  am 2 x2  ...  amn xn  bm , (4.1.) (4.2.) x j  0, j  1,2,..., n, (4.3.) bi  0, i  1,2,..., m (4.4.) где кроме того 6 4.1. Постановка задачи Пусть ранг матрицы А равен r0. Своб. член xr+1 … xj … xn Z γ0 γr+1 … γj … γn x1 β1 α1,r+1 … α1j … α1n … … … … … … … xi βi αi,r+1 … αij … αin … … … … … … … xr βr αr,r+1 … αr,r+1 … αrn 13 4.3. Симплекс-таблица Правило выбора генеральной строки: в столбце xj среди положительных чисел, не считая строки Z, выбрать то, для которого отношение к нему свободного i члена  минимально. ij Выбор генерального столбца и генеральной строки однозначно определяет. генеральный элемент αij Своб. член xr+1 … xj … xn Z γ0 γr+1 … γj … γn x1 β1 α1,r+1 … α1j … α1n … … … … … … … xi βi αi,r+1 … αij … αin … … … … … … … xr βr αr,r+1 … αr,r+1 … αrn 14 4.3.1. Пересчет симплекс-таблицы Переход к новому допустимому базисному решению осуществляется путем пересчета симплекс-таблицы. Правила пересчета симплекс-таблицы. 1. xi и xj меняются местами. 2. На месте генерального элемента пишется величина ему обратная. 3. Все элементы генеральной строки (кроме генерального элемента) делятся на генеральный элемент. 4. Все элементы генерального столбца (кроме генерального элемента) делятся на генеральный элемент и берутся с противоположным знаком. 5. Все остальные элементы пересчитываются по правилу прямоугольника 15 4.3.2. Правило прямоугольника , , Своб. член xr+1 … xj … xn Z γ0 γr+1 … γj … γn x1 β1 α1,r+1 … α1j … α1n … … … … … … … xi βi αi,r+1 … αij … αin … … … … … … … xr βr αr,r+1 … αr,r+1 … αrn , 16 4.3.3. Порядок работы по симплекс-методу , , , 1. Найти исходное допустимое базисное решение в стандартном виде и заполнить симплекс-таблицу. 2. Выбрать генеральный столбец. Если его выбрать нельзя, решение оптимально. 3. Выбрать генеральный элемент, а следовательно, и генеральную строку . Если ее выбрать нельзя, задача решений не имеет. 4. Пересчитать симплекс-таблицу, получив таким образом новое допустимое решение. 5. Перейти к п.2. 17 4.3.4. Пример решения ЗЛП с помощью симплекс-таблицы Решим симплекс-методом следующую ЗЛП Z  X   3x1  2 x2  min 3x1  2 x2  9,   2 x1  5 x2  25, x1, x2  0 Приведем ЗЛП к каноническому виду Z  X   3x1  2 x2  min 3x1  2 x2  x3  9,  2 x1  5 x2  x4  25, x1, x2 , x3 , x4  0 18 4.3.4. Пример решения ЗЛП с помощью симплекс-таблицы Стандартная форма записи допустимого базисного решения будет иметь вид  x3  9  3x1  2 x2 ,   x4  25  2 x1  5 x2 , x1 , x2 , x3 , x4  0 Z  X   0  3x1  2 x2   min Ей соответствует симплекс-таблица Своб. член x1 x2 Z 3 2 x3 9 3 -2 x4 25 2 5 Определим генеральный элемент 19 4.3.4. Пример решения ЗЛП с помощью симплекс-таблицы Исходная симплекс-таблица. Своб. член x1 x2 Z 3 2 x3 9 3 -2 x4 25 2 5 В новом допустимом базисном решении роли x1 и x3 изменятся на противоположные. Найдем это решение, перейдя к новой симплекстаблице. Своб. член x3 x2 Z x1 x4 20 4.3.4. Пример решения ЗЛП с помощью симплекс-таблицы Исходная симплекс-таблица. Своб. член x1 x2 Z 3 2 x3 9 3 -2 x4 25 2 5 На месте генерального элемента напишем число 1/3 Своб. член x3 x2 Z x1 x4 21 4.3.4. Пример решения ЗЛП с помощью симплекс-таблицы Исходная симплекс-таблица. Своб. член x1 x2 Z 3 2 x3 9 3 -2 x4 25 2 5 9/3= На месте элементов генеральной строки получим Своб. член 3 x2 Z x1 -2/3 x3 1/3 x4 22 4.3.4. Пример решения ЗЛП с помощью симплекс-таблицы Исходная симплекс-таблица. Своб. член x1 x2 Z 3 2 x3 9 3 -2 x4 25 2 5 -3/3= На месте элементов генерального столбца получим -1 Своб. член x3 x2 3 1/3 -2/3 Z x1 -2/3 x4 23 4.3.4. Пример решения ЗЛП с помощью симплекс-таблицы Исходная симплекс-таблица. Своб. член x1 x2 Z 3 2 x3 9 3 -2 x4 25 2 5 Пересчитаем остальные элементы по правилу прямоугольника Своб. член (0*3-9*3)/3= -9 Z x1 x4 x3 x2 -1 3 1/3 -2/3 -2/3 24 4.3.4. Пример решения ЗЛП с помощью симплекс-таблицы Исходная симплекс-таблица. Своб. член x1 x2 Z 3 2 x3 9 3 -2 x4 25 2 5 (2*3-(-2)*3)/3= 4 Пересчитаем остальные элементы по правилу прямоугольника Своб. член x3 Z -9 -1 x1 3 1/3 x4 x2 -2/3 -2/3 25 4.3.4. Пример решения ЗЛП с помощью симплекс-таблицы Исходная симплекс-таблица. Своб. член x1 x2 Z 3 2 x3 9 3 -2 x4 25 2 5 (25*3-9*2)/3= 19 Пересчитаем остальные элементы по правилу прямоугольника Своб. член x3 x2 Z -9 -1 4 x1 3 1/3 -2/3 x4 -2/3 26 4.3.4. Пример решения ЗЛП с помощью симплекс-таблицы Исходная симплекс-таблица. Своб. член x1 x2 Z 3 2 x3 9 3 -2 x4 25 2 5 (5*3-(-2)*2)/3= 19/3 Пересчитаем остальные элементы по правилу прямоугольника Своб. член x3 x2 Z -9 -1 4 x1 3 1/3 -2/3 x4 19 -2/3 27 4.3.4. Пример решения ЗЛП с помощью симплекс-таблицы Определим генеральный элемент в новой таблице Своб. член x3 x2 Z -9 -1 4 x1 3 1/3 -2/3 x4 19 -2/3 19/3 Выполним пересчет полученной симплекс-таблицы 28 4.3.4. Пример решения ЗЛП с помощью симплекс-таблицы Последняя симплекс-таблица. Своб. член x3 x2 Z -9 -1 4 x1 3 1/3 -2/3 x4 19 -2/3 19/3 В новом допустимом базисном решении роли x2 и x4 изменятся на противоположные. Найдем это решение, перейдя к новой симплекстаблице. Своб. член x3 x4 Z x1 x2 29 4.3.4. Пример решения ЗЛП с помощью симплекс-таблицы Последняя симплекс-таблица. Своб. член x3 Z -9 -1 4 x1 3 1/3 -2/3 x4 19 -2/3 19/3 На месте генерального элемента напишем число x2 3/19 Своб. член x3 x4 Z x1 x2 30 4.3.4. Пример решения ЗЛП с помощью симплекс-таблицы Последняя симплекс-таблица. Своб. член x3 x2 Z -9 -1 4 x1 3 1/3 -2/3 x4 19 -2/3 19/3 19/(19/3)= На месте элементов генеральной строки получим Своб. член 3 x3 x4 Z x1 (-2/3)/(19/3)= -2/19 x2 3/19 31 4.3.4. Пример решения ЗЛП с помощью симплекс-таблицы Последняя симплекс-таблица. Своб. член x3 x2 Z -9 -1 4 x1 3 1/3 -2/3 x4 19 -2/3 19/3 -4/(19/3)= На месте элементов генерального столбца получим -12/19 Своб. член x3 x4 3 -2/19 3/19 Z x1 (2/3)/(19/3)= 2/19 x2 32 4.3.4. Пример решения ЗЛП с помощью симплекс-таблицы Последняя симплекс-таблица. Своб. член x3 x2 Z -9 -1 4 x1 3 1/3 -2/3 x4 19 -2/3 19/3 Пересчитаем остальные элементы по правилу прямоугольника Своб. член (-9*19/3-4*19)/(19/3)= -21 x3 x4 Z -12/19 x1 2/19 x2 3 -2/19 3/19 33 4.3.4. Пример решения ЗЛП с помощью симплекс-таблицы Последняя симплекс-таблица. Своб. член x3 x2 Z -9 -1 4 x1 3 1/3 -2/3 x4 19 -2/3 19/3 Пересчитаем остальные элементы по правилу прямоугольника Своб. член (-1*(19/3)-4*(-2/3))/(19/3)= -11/19 Z x3 -21 -12/19 x1 x2 x4 2/19 3 -2/19 3/19 34 4.3.4. Пример решения ЗЛП с помощью симплекс-таблицы Последняя симплекс-таблица. Своб. член x3 x2 Z -9 -1 4 x1 3 1/3 -2/3 x4 19 -2/3 19/3 Пересчитаем остальные элементы по правилу прямоугольника Своб. член (3*(19/3)-19*(-2/3))/(19/3)= Z -21 x3 -11/19 x4 -12/19 5 x1 x2 2/19 3 -2/19 3/19 35 4.3.4. Пример решения ЗЛП с помощью симплекс-таблицы Исходная симплекс-таблица. Своб. член x3 x2 Z -9 -1 4 x1 3 1/3 -2/3 x4 19 -2/3 19/3 Пересчитаем остальные элементы по правилу прямоугольника Своб. член x3 x4 Z -21 -11/19 -12/19 x1 5 x2 3 (1/3*(19/3)-(-2/3)*(-2/3))/(19/3)= 5/19 2/19 -2/19 3/19 36 4.3.4. Пример решения ЗЛП симплекс-методом Своб. член x3 x4 Z -21 -11/19 -12/19 x1 5 5/19 2/19 x2 3 -2/19 3/19 Далее генеральный столбец выбрать нельзя. Значит, X min  5;3;0;0, Z min  21. 37 4.3.5. Некоторые замечания по симплекс-методу Как известно, в результате решения ЗЛП может возникнуть одна из четырех ситуаций (см. п.3.3.). Рассмотрим их. 1. Единственное решение возникает в тех случаях, когда в симплекстаблице, соответствующей оптимальному решению, все оценки γj<0 (j=1,…n). (ситуация рассмотрена в предыдущем примере). 2. Бесконечное множество решений (альтернативный оптимум) существует в тех случаях, когда в симплекс-таблице, соответствующей оптимальному решению, найдется оценка γj=0 (j=1,…n). 3. Отсутствие решений по причине неограниченности функции возникает в случае, когда в симплекс-таблице нельзя выбрать генеральную строку. 4. Отсутствие решений по причине противоречивости системы ограничений выясняется в процессе поиска исходного допустимого базисного решения (вызывает большие затруднения). 38 4.3.5. Некоторые замечания по симплекс-методу. Для решения задачи на максимум можно использовать один из двух способов. 1. Рассмотреть функцию Z1(X)=-Z(X) , которую следует минимизировать при заданных ограничениях. Соответственно, (Z1) min=-Zmax, и так как система ограничений одна и та же в обоих случаях, то точка оптимума не изменяется при переходе от одной задачи к другой. 2. Генеральным столбцом выбирать тот столбец, в котором γj<0 с целью получения строки Z(X) в которой все оценки γj>0 (j=1,…n). 39