Справочник от Автор24
Высшая математика

Конспект лекции
«Методы оптимальных решений»

Справочник / Лекторий Справочник / Лекционные и методические материалы по высшей математике / Методы оптимальных решений

Выбери формат для чтения

pdf

Конспект лекции по дисциплине «Методы оптимальных решений», pdf

Файл загружается

Файл загружается

Благодарим за ожидание, осталось немного.

Конспект лекции по дисциплине «Методы оптимальных решений». pdf

txt

Конспект лекции по дисциплине «Методы оптимальных решений», текстовый формат

Методы оптимальных решений 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. Постановка задачи Пусть ранг матрицы А равен r<n. Тогда общее решение системы уравнений-ограничений (4.2.) будет содержать r базисных переменных (число различных уравнений системы) и n-r свободных переменных. Это решение можно получить, например, методом Жордана-Гаусса. Будем считать, что свободные переменные xr+1, xr+2,…, xn а базисные x1, x2,…, xr. Тогда общее решение системы (4.2.) запишется в виде  x1  1   1,r 1xr 1   1,r  2 xr  2  ...   1n xn ,   x2   2   2,r 1xr 1   2,r  2 xr  2  ...   2n xn ,  .................................................................  xr   r   r ,r 1xr 1   r ,r  2 xr  2  ...   rn xn ,  7 4.1. Постановка задачи Пусть общее решение системы (4.2.) имеет вид  x1  1   1,r 1xr 1   1,r  2 xr  2  ...   1n xn ,   x2   2   2,r 1xr 1   2,r  2 xr  2  ...   2n xn ,  .................................................................  xr   r   r ,r 1xr 1   r ,r  2 xr  2  ...   rn xn ,  (4.6.) Тогда целевая функция запишется в виде Z  X    0   r 1xr 1   r 2 xr 2  ...   n xn . (4.7.) 8 4.1. Постановка задачи Решение системы уравнений называется базисным, если свободные неизвестные равны нулю. В нашем случае базисное решение имеет вид    X   1,  2 ,...,  r , 0,0,...     nr  Базисное решение системы уравнений называется допустимым базисным, если базисные неизвестные неотрицательны. Формулы (4.6) и (4.7) будем называть стандартной формой записи допустимого базисного решения. (если все βi неотрицательны). 9 4.2. Идея и принципы симплекс-метода  Решение ЗЛП, если оно существует всегда находится на границе области допустимых решений (ОДР).  Если оптимальное решение единственно, то оно всегда достигается в одной из вершин ОДР.  Для того, чтобы найти оптимальное решение, достаточно перебрать все вершины многогранника и выбрать ту, в которой целевая функция принимает оптимальное значение. Такие решения называют допустимыми базисными решениями.  Этап нахождения допустимых базисных решений - координат вершин ОДР -является составной частью любого алгоритма поиска оптимального решения.  Алгоритм перебора допустимых решений для поиска оптимума в симплекс-методе организуется целенаправленно, так чтобы при переходе от одной вершины к другой значение целевой функции не возрастало (в задаче на минимум). • Если на одном из этапов переход к соседним вершинам ОДР не приводит к уменьшению (в задаче на минимум) целевой функции, то поиск прекращается, а найденное допустимое базисное решение является оптимальным. 10 4.3. Симплекс-таблица При переходе от одного допустимого базисного решения к другому удобно пользоваться так называемой симплекс-таблицей. Пусть имеется допустимое базисное решение ЗЛП, записанное в стандартной форме (все βi≥0)  x1  1   1,r 1xr 1   1,r  2 xr  2  ...   1n xn ,   x2   2   2,r 1xr 1   2,r  2 xr  2  ...   2n xn ,  .................................................................  xr   r   r ,r 1xr 1   r ,r  2 xr  2  ...   rn xn ,  Z  X    0   r 1 xr 1   r 2 xr 2  ...   n xn   min . 11 4.3. Симплекс-таблица Этой задаче будет соответствовать следующая симплекс-таблица Своб. член 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 12 4.3. Симплекс-таблица Правило выбора генерального столбца: в строке Z, не считая свободного члена выбрать любое положительное число. Если положительных чисел нет, решение оптимально. Пусть γj >0. Своб. член 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

Рекомендованные лекции

Смотреть все
Высшая математика

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

МЕТОДЫ ОПТИМАЛЬНЫХ РЕШЕНИЙ Конспект лекций СОДЕРЖАНИЕ ВВЕДЕНИЕ В МЕТОДЫ ОПТИМАЛЬНЫХ РЕШЕНИЙ ..................................... 3 МЕТОДЫ НЕЛИНЕЙНОЙ ...

Высшая математика

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

Министерство образования и науки Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего образования «Тульский г...

Автор лекции

Гучек Н.Е.

Авторы

Высшая математика

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

Дисциплина: МЕТОДЫ ОПТИМАЛЬНЫХ РЕШЕНИЙ Лекция 2. Многокритериальные задачи и методы принятия оптимальных решений в условиях определенности. Методы при...

Автор лекции

Гвоздкова Ирина Александровна

Авторы

Высшая математика

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

Министерство образования и науки Российской Федерации федеральное государственное бюджетное образовательное учреждение высшего образования «САНКТ-ПЕТЕ...

Автор лекции

В. В. Потихонова, Л. И. Король

Авторы

Высшая математика

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

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

Информатика

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

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования ФИНАНСОВЫЙ УНИВЕРСИТЕТ ПРИ ПРАВИТЕЛЬСТВЕ РФ БАР...

Автор лекции

Ильина М. А., Копылов Ю. Н., Копылова Н. Т.

Авторы

Высшая математика

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

ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ КАФЕДРА МАТЕМАТИКИ И ЕСТЕСТВЕННОНАУЧНЫХ ДИСЦИПЛИН Вилисов В.Я. Конспект лекций по курсу «МЕТОДЫ ОПТИМАЛЬНЫХ РЕШЕНИЙ» Специ...

Автор лекции

Вилисов В. Я.

Авторы

Высшая математика

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

НВУЗ АНО «Региональный финансово-экономический институт» МЕТОДЫ ОПТИМАЛЬНЫХ РЕШЕНИЙ ________________________________ http://elearning.rfei.ru СОДЕРЖАН...

Бухгалтерский учет и аудит

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

НВУЗ АНО «Региональный финансово-экономический институт» МЕТОДЫ ОПТИМАЛЬНЫХ РЕШЕНИЙ ________________________________ http://elearning.rfei.ru СОДЕРЖАН...

Высшая математика

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

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «ФИНАНСОВЫЙ УНИВЕРСИТЕТ ПРИ ПРАВИТЕЛЬСТВЕ РОССИ...

Автор лекции

Луценко А. Г.

Авторы

Смотреть все