Реферат: Решение оптимизационной задачи линейного программирования
E= X1 + X2 + 2 X3 + 3 X4 + 3 X5 + 2 X6 Þ max
3. ОБОСНОВАНИЕ И ОПИСАНИЕ ВЫЧИСЛИТЕЛЬНОЙ ПРОЦЕДУРЫ
3.1. П РИВЕДЕНИЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ К СТАНДАРТНОЙ ФОРМЕ
Любая задача линейного программирования приводится к стандартной (канонической) форме основной задачи линейного программирования, которая формулируется следующим образом: найти неотрицательные значения переменных X1 , X2 , Xn , удовлетворяющих ограничениям в виде равенств:
A11X1 + A12X2 + … + A1nXn = B1;
A21X1 + A22X2 + … + A2nXn = B2;
……………………………………
Am1X1 + Am2X2 + … + AmnXn = Bm;
Xj ≥0 , j=1 ,…,n
и обращающих в максимум линейную функцию этих переменных:
E = C1X1 + C2X2 + … + CnXnÞ max
При этом также требуется, чтобы правые части равенств были неотрицательны, т.е. должны соблюдаться условия:
Bj ≥ 0, j=1,…,n
Приведение к стандартной форме необходимо, таккакбольшинство методов решения задач линейного программирования разработано именно для стандартной формы. Для приведения к стандартной форме задачи линейного программирования может потребоваться выполнить следующие действия:
- перейти от минимизации целевой функции к ее максимизации;
- изменить знаки правых частей ограничений;
- перейти от ограничений-неравенств к равенствам;
- избавиться от переменных, не имеющих ограничений на знак.
Для решения нашей задачи воспользуемся симплекс-методом, так как этот метод предназначен для решения задач линейного программирования любой размерности.
3.2. ОСНОВНАЯ ИДЕЯ СИМПЛЕКС-МЕТОДА
Экстремум целевой функции всегда достигается в угловых точках области допустимых решений. Симплекс-метод, называемый также методом последовательного улучшения плана, реализует перебор угловых точек области допустимых решений в направлении улучшения значения целевой функции. Основная идея этого метода следующая. Прежде всего, находится какое-либо допустимое начальное (опорное) решение, т.е. какая-либо угловая точка области допустимых решений. Процедура метода позволяет ответить на вопрос, является ли это решение оптимальным. Если "да", то задача решена. Если "нет", то выполняется переход к смежной угловой точке области допустимых решений, где значение целевой функции улучшается, т.е. к нехудшему допустимому решению. Если некоторая угловая точка имеет несколько смежных, то вычислительная процедура метода обеспечивает переход к той из них, для которой улучшение целевой функции будет наибольшим. Процесс перебора угловых точек области допустимых решений повторяется, пока не будет найдена точка, которой соответствует экстремум целевой функции Е.
При построении начального базиса в заданной задаче использовался метод искусственного базиса, поэтому найденное решение не является допустимым. В этом случае для решения задачи необходимо использовать двухэтапный симплекс-метод.
3.3. ДВУХЭТАПНЫЙ СИМПЛЕКС-МЕТОД
Задача с помощью этого метода решается в два этапа: сначала отыскивается начальное допустимое решение, не содержащее искусственных переменных, а затем на основе найденного решения ищется оптимальное решение исходной задачи. Основные шаги, реализации метода следующие.
1. Задача линейного программирования сводится к стандартной форме.
2. Строится искусственный базис.
3. Составляется искусственная целевая функция: сумма всех искусственных переменных.
4. Реализуется первый этап двухэтапного метода: с помощью обычных процедур симплекс-метода выполняется минимизация искусственной целевой функции. Если ее минимальное значение равно 0, то соответствующее решение является допустимым решением исходной задачи. Очевидно, что при нулевом значении искусственной целевой функции все искусственные переменные также нулевые (так как искусственная целевая функция - их сумма, и все они неотрицательны). Если минимальное значение искусственной целевой функции оказывается отличным от нуля, это означает, что задача не имеет допустимых решений.
5. Реализуется второй этап двухэтапного метода: найденное на шаге 4 допустимое решение используется в качестве начального решения исходной задачи для поиска ее оптимального решения.
4. РЕШЕНИЕ ЗАДАЧИ ОПТИМИЗАЦИИ НА ОСНОВЕ СИМПЛЕКС-ТАБЛИЦ
4.1. ПРИВЕДЕНИЕ ЗАДАЧИ К СТАНДАРТНОЙ ФОРМЕ
Для приведения данной задачи к стандартной форме необходимо лишь перейти от ограничений – неравенств к равенствам. Для этого введем дополнительные балансовые неотрицательные переменные. Также для упрощения дальнейших вычислений разделим обе части ограничений на комплектацию деталей на 5 :
X1 + X2 + X3 + X7 = 8 ;
X4 + X5 + X6 + X8 = 8 ;
2 X1 – X2 + 6 X4 – 3 X5 = 0 ;
2 X1 – 2 X3 + 6 X4 – 2 X6 =0 ;
X1 , X2 , X3 , X4 , X5 , X6 , X7 , X8≥0 .
E= X1 + X2 + 2 X3 + 3 X4 + 3 X5 + 2 X6 Þ max
где Х7 , Х8 – остаточные переменные.
Итак, нашу исходную задачу мы привели к стандартной форме основной задачи линейного программирования.
4.2. ОПРЕДЕЛЕНИЕ НАЧАЛЬНОГО ДОПУСТИМОГО РЕШЕНИЯ
Для задачи, представленной в стандартной форме, количество переменных обычно больше, чем количество ограничений. Поэтому для нахождения начального решения задачи требуется выразить m переменных (т.е. количество переменных, равное количеству уравнений) через остальные n-m переменных, принять эти n-m переменных равными нулю и, таким образом, найти значения m переменных (в заданной задаче m=4 и n=8 ). Переменные, значения которых принимаются равными нулю, называются небазисными, а остальные m переменных - базисными. Значения базисных переменных неотрицательны (некоторые из них могут оказаться равными нулю). Количество базисных переменных всегда равно количеству ограничений. Найденное таким образом решение называется начальным допустимым базисным решением. Оно соответствует всем ограничениям.
Начальное решение проще всего найти в случае, когда в каждом ограничении есть переменная, которая входит в него с коэффициентом 1 и при этом отсутствует в других ограничениях. Такие переменные принимаются в качестве базисных (они образуют начальный базис задачи). Остальные (небазисные) переменные принимаются равными нулю. Таким образом, базисные переменные принимают значения, равные правым частям ограничений.
Итак, для нахождения начального допустимого решения необходимо, чтобы в каждое из уравнений входила переменная с коэффициентом 1 и не входила в другие уравнения (базисная переменная). В нашем случае мы имеем только 2 базисные переменные (X7и X8) , не хватает еще двух базисных переменных. Их можно создать с помощью специального способа, который называется построением искусственного базиса.
4.3. П ОСТРОЕНИЕ ИСКУССТВЕННОГО БАЗИСА
Методы искусственного базиса предназначены для построения начального базиса (т.е. для получения начального решения) в случаях, когда его построение непосредственно на основе стандартной формы невозможно. При использовании искусственного базиса начальное решение оказывается недопустимым; от него по определенным алгоритмам выполняется переход к начальному допустимому решению.
Для того, чтобы построить искусственный базис, необходимо в каждое уравнение стандартной формы, не содержащее базисных переменных (т.е. полученное из ограничения-равенства или "не меньше"), добавить по одной искусственной переменной. В нашем случае это:
2 X1 – X2 + 6 X4 – 3 X5 + Х9 = 0 ;
2 X1 – 2 X3 + 6 X4 – 2 X6 + Х10 =0 .
где Х9 и Х10 – искусственные переменные, не имеющие никакого физического смысла, причем Х9 , Х10≥0.