ПОСТАНОВКА ЗАДАЧИ ОПТИМИЗАЦИИ
ОСНОВНАЯ ИДЕЯ СИМПЛЕКС-МЕТОДА
ПОСТРОЕНИЕ ИСКУССТВЕННОГО БАЗИСА
Реализуем
первый этап двухэтапного метода: с помощью процедур симплекс-
ВТОРОЙ ЭТАП ДВУХЭТАПНОГО СИМЛЕКС-МЕТОДА
АНАЛИЗ МОДЕЛИ НА ЧУВСТВИТЕЛЬНОСТЬ
АНАЛИЗ НА ЧУВСТВИТЕЛЬНОСТЬ К ИЗМЕНЕНИЯМ КОЭФФИЦИЕНТОВ ЦЕЛЕВОЙ ФУНКЦИИ
Навигация
ПОСТРОЕНИЕ ИСКУССТВЕННОГО БАЗИСА
Решение оптимизационной задачи линейного программирования
59893
знака
13
таблиц
0
изображений
4.3. ПОСТРОЕНИЕ ИСКУССТВЕННОГО БАЗИСА
Методы искусственного базиса предназначены для построения начального базиса (т.е. для получения начального решения) в случаях, когда его построение непосредственно на основе стандартной формы невозможно. При использовании искусственного базиса начальное решение оказывается недопустимым; от него по определенным алгоритмам выполняется переход к начальному допустимому решению.
Для того, чтобы построить искусственный базис, необходимо в каждое уравнение стандартной формы, не содержащее базисных переменных (т.е. полученное из ограничения-равенства или "не меньше"), добавить по одной искусственной переменной. В нашем случае это:
2X1 – X2 + 6X4 – 3X5 + Х9 = 0;
2X1 – 2X3 + 6X4 – 2X6 + Х10 =0.
где Х9 и Х10 – искусственные переменные, не имеющие никакого физического смысла, причем Х9 , Х10 ≥0.
После построения искусственного базиса, придав нулевые значения всем переменным, кроме базисных, получим начальный базис: Х7 , Х8 , Х9 , Х10 . Всего в базисе имеется четыре переменные и их значения равны правым частям ограничений, т.е.:
Х7 = 8;
Х8 = 8;
Х9 = 0;
Х10 = 0.
Теперь необходимо решить эту задачу, т.е. найти оптимальное допустимое решение. Для этого воспользуемся двухэтапным симплекс-методом.
4.4. ПЕРВЫЙ ЭТАП ДВУХЭТАПНОГО СИМПЛЕКС-МЕТОДА
Итак, на первом этапе двухэтапного метода отыскивается начальное допустимое решение. Для этого выполним следующие действия:
1. Строим искусственную целевую функцию – сумму всех искусственных
переменных:
W = X9 + X10 Þ min
2. Так как целевая функция должна быть выражена только через небазисные
переменные, то выражаем искусственные переменные X9 и X10 через небазисные переменные, а затем, упростив полученное выражение, переписываем искусственную целевую функцию:
X9 = - 2X1 + X2 - 6X4 + 3X5;
X10 = - 2X1 + 2X3 - 6X4 + 2X6.
W = - 4X1 + X2 + 2X3 – 12X4 + 3X5 + 2X6 Þ min
3. Для приведения к стандартной форме направим искусственную целевую
функцию на максимум, для этого умножим обе ее части на –1:
-W = 4X1 - X2 - 2X3 + 12X4 - 3X5 - 2X6 Þ max
4. Определяем начальное, недопустимое решение. Базис состоит из четырех
переменных, из них две искусственные, остальные две - остаточные. Базисные переменные принимают значения, равные ограничениям задачи. Остальные переменные считаем равными нулю. В этом случае целевая функция Е принимает значение 0, искусственная целевая функция –W также принимает значение 0.
5. Составляем исходную симплекс-таблицу:
| БП | X1 | X2 | X3 | X4 | X5 | X6 | X7 | X8 | X9 | X10 | БР |
| E | -1 | -1 | -2 | -3 | -3 | -2 | 0 | 0 | 0 | 0 | 0 |
| -W | -4 | 1 | 2 | -12 | 3 | 2 | 0 | 0 | 0 | 0 | 0 |
| X7 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 8 |
| X8 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 1 | 0 | 0 | 8 |
| X9 | 2 | -1 | 0 | 6 | -3 | 0 | 0 | 0 | 1 | 0 | 0 |
| X10 | 2 | 0 | -2 | 6 | 0 | -2 | 0 | 0 | 0 | 1 | 0 |
Таблица 2. Симплекс-таблица №1.
Итак, в первом столбце таблицы указаны базисные переменные, в последнем столбце - их значения, а так же значения целевой и искусственной целевой функций. В заголовке таблицы перечисляются все используемые переменные. В строках таблицы указываются коэффициенты ограничений задачи.
Похожие работы
... . При этом значения cij соответствуют коэффициентам целевой функции исходной замкнутой транспортной задачи (1) и в последующем не изменяются. Элементы xij соответствуют значениям переменных промежуточных решений транспортной задачи линейного программирования и изменяются на каждой итерации алгоритма. Если в некоторой ячейке xij=0, то такая ячейка называется свободной, если же xij>0, то такая ...
... задачи линейного программирования, они очень сложны и решаются специальными, обычно многостадийными приемами с использованием эвристических элементов. 3. Решение задач 3.1. Решение задачи линейного программирования 3.1.1.Постановка задачи Сформулируем задачу: Определить значения переменных, обеспечивающие минимизацию целевой функции. Составим целевую функцию и зададим ограничения. ...
... имеет вид найти переменные задачи удовлетворяющие системе ограничений: и условию неотрицательности 0 (j = ), которая обеспечивает экстремум целевой функции Z(Y) = Допустимым решением задачи линейного программирования называется любой набор значений переменных удовлетворяющий системе ограничений и условной неотрицательности. Множество допустимых решений образует область допустимых ...
... 0 505/103 0 792/103 669/103 500/103 Анализ Таблицы 6 позволяет сделать вывод о допустимости и оптимальности базиса XБ4=(x5, x7, x1, x2, x4)T. 3.4 Результат решения задачи планирования производства В результате решения поставленной задачи симплекс-методом получили набор производимой продукции x=(x1, x2, x3, x4, x5)=( 15145/103, 8910/103, 0, 1250/103, 3255/103), который удовлетворяет всем ...
0 комментариев