Метод искусственного базиса реферат
Обновлено: 02.07.2024
М-метод применяется для решения любых задач линейного программирования, в том числе и тех, где начальная каноническая форма не задана.
М-метод состоит во введении новых искусственных переменных, которые сразу можно взять в качестве базисных, и дальнейшем решении полученной задачи симплекс-методом.
Предположим, что исходная задача линейного программирования представлена в основной форме:
Алгоритм М-метода:
В каждое i-ое ограничение вводим искусственную переменную хn+i >0. Всего m новых искусственных переменных.
Если, то в целевую функцию L вводим m дополнительных слагаемых вида: -M×xn+1, -M×хn+2, . -M×хn+m; если же, то слагаемые вида: M×xn+1, M×хn+2, . M×хn+m, где М — произвольная очень большая константа.
Получим новую, вспомогательную задачу линейного программирования:
F(X) = c1Х1 +… + сnXn -M*Xn+1 — … -M*Xn+m => max
ai,1X1+… + ai,nXn +Xn+i = bi, (i=1,m)
Новая система ограничений характерна тем, что искусственные переменные сразу можно взять в качестве базисных:
Формируем начальное базисное решение новой М-задачи :
Решаем М-задачу симплекс-методом
Анализируем решение М-задачи в соответствии со следующими правилами :
Если в оптимальном решении М-задачи:
X" = ( X"1,… X"n, X"n+1,… X"n+m )
все искусственные переменные равны 0, то вектор
является оптимальным решением исходной ЗЛП.
Если в оптимальном решении М-задачи хотя бы одна искусственная переменная не равна 0, то исходная ЗЛП не имеет решения в силу несовместимости ограничений.
Если М-задача не имеет решения, то исходная ЗЛП также не имеет решения в силу неограниченности целевой функции на допустимом множестве.
F(X) = 4X1 +4X2 +2X3 +4X4 +3X5 +1X6 => max
-3X1 +0X2 +2X3 +3X4 +3X5 +4X6 = 1
3X1 -2X2 -1X3 +4X4 +3X5 -3X6 = 2
4X1 -2X2 +1X3 -1X4 -1X5 -1X6 = 2
2X1 +3X2 +3X3 +1X4 +2X5 -3X6 = 3
Вводим в ограничения искусственные переменные :
-3X1 +0X2 +2X3 +3X4 +3X5 +4X6 +X7 = 1
3X1 -2X2 -X3 +4X4 +3X5 -3X6 +X8 = 2
4X1 -2X2 +X3 -X4 -X5 -X6 +X9 = 2
2X1 +3X2 +3X3 +X4 +2X5 -3X6 +X10 = 3
Вводим в целевую функцию дополнительные слагаемые:
F(X) = 4X1 +4X2 +2X3 +4X4 +3X5 +X6 — MX7 — MX8 — MX9 — MX10 => max
Т.о. мы получили новую ЗЛП.
Сформируем начальное базисное решение новой М-задачи :
X'=( 0, 0, 0, 0, 0, 0, 1, 2, 2, 3 );
После решения М-задачи симплекс методом мы получили следующее оптимальное решение: X"=( 1.2, 0.77, 0.00, 0.54, 0.00, 0.75, 0.00, 0.00, 0.00, 0.00 ); В этом решении все искусственные переменные равны 0, следовательно мы нашли оптимальное решение и для исходной ЗЛП: X = ( 1.2, 0.77, 0.00, 0.54, 0.00, 0.75 ).
Решение задачи, состоящей в определении максимального значения функции. Решение расширенной задачи симплекс-методом. Алгоритм метода искусственного базиса. Особые случаи применения симплекс-метода (Х.А. Таха). Правило выявления неограниченности решения.
| Рубрика | Математика |
| Вид | лекция |
| Язык | русский |
| Дата добавления | 06.09.2017 |
| Размер файла | 65,3 K |
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
HTML-версии работы пока нет.
Cкачать архив работы можно перейдя по ссылке, которая находятся ниже.
Подобные документы
Понятие линейного программирования и его основные методы. Формулировка задачи линейного программирования в матричной форме и ее решение различными методами: графическим, табличным, искусственного базиса. Особенности решения данной задачи симплекс-методом.
курсовая работа [65,3 K], добавлен 30.11.2010
Основные сведения о симплекс-методе, оценка его роли и значения в линейном программировании. Геометрическая интерпретация и алгебраический смысл. Отыскание максимума и минимума линейной функции, особые случаи. Решение задачи матричным симплекс-методом.
дипломная работа [351,2 K], добавлен 01.06.2015
Форма для ввода целевой функции и ограничений. Характеристика симплекс-метода. Процесс решения задачи линейного программирования. Математическое описание алгоритма симплекс-метода. Решение задачи ручным способом. Описание схемы алгоритма программы.
контрольная работа [66,3 K], добавлен 06.04.2012
Способы построения искусственного базиса задачи. Выражение искусственной целевой функции. Математическая модель задачи в стандартной форме. Получение симплекс-таблиц. Минимизации (сведения к нулю) целевой функции. Формы преобразования в задаче равенства.
задача [86,0 K], добавлен 21.08.2010
Сущность понятия "симплекс-метод". Математические модели пары двойственных задач линейного программирования. Решение задачи симплексным методом: определение минимального значения целевой функции, построение первого опорного плана, матрица коэффициентов.
То невозможно сразу получить начальное базисное решение, если матрица, составленная из коэффициентов при неизвестных системы ограничений, не позволяет образовать единичную матрицу. Причем уравнения отражают жесткие условия ограничений, но ресурсам, не допускающие никаких отклонений. Для соблюдения равенств вводятся искусственные переменные г/" равные нулю. Векторы искусственных переменных… Читать ещё >
- экономико-математические методы и модели в коммерческой деятельности
Метод искусственного базиса ( реферат , курсовая , диплом , контрольная )
Симплексный метод решения задач базируется на введении дополнительных переменных, позволяющих образовать единичную матрицу, в которую не допускаются отрицательные и другие числа, кроме нуля и единицы. Наличие единичной матрицы является необходимым условием при решении задач симплексным методом.
Если же ограничения задачи заданы в виде неравенств вида > или уравнений.
то невозможно сразу получить начальное базисное решение, если матрица, составленная из коэффициентов при неизвестных системы ограничений, не позволяет образовать единичную матрицу. Причем уравнения отражают жесткие условия ограничений, но ресурсам, не допускающие никаких отклонений. Для соблюдения равенств вводятся искусственные переменные г/" равные нулю. Векторы искусственных переменных образуют необходимую для решения единичную матрицу. Такой базис называется искусственным, а метод решения называется методом искусственного базиса, или М-методом. Причем искусственные переменные не имеют отношения к содержанию поставленной задачи, однако они позволяют построить стартовую точку, а процесс оптимизации вынуждает эти переменные принимать нулевые значения и обеспечить допустимость оптимального решения. Рассмотрим примеры постановки и решения задач такого рода.
Преобразование ограничений, заданных в виде уравнений, рассмотрим на примере:
В систему равенств вводим искусственные переменные зуь Уъ Уъ с коэффициентами, равными единице, позволяющими образовать искусственный базис решения.
Целевая функция имеет вид:
• при решении задачи на максимум.
• при решении задачи на минимум.
За использование искусственных переменных, вводимых в целевую функцию, накладывается так называемый штраф величиной М, очень большое положительное число, которое обычно не задается (М —? оо).
Преобразования ограничений в виде неравенств вида > рассмотрим на примере.
Для получения системы уравнений вводим дополнительные переменные х4, х$, х$:
Поскольку на главной диагонали единичной матрицы не могут находиться (-1), то в систему вводим искусственные переменные уи у2, Уз с коэффициентами (+1), которые образуют искусственный базис решения.
Целевая функция имеет вид:
• при решении задачи на максимум.
• при решении задачи на минимум.
Преобразование разнородных ограничений, представляющих собой смесь уравнений и неравенств разного вида, заключается в образовании базиса решения путем одновременного введения свободных и искусственных переменных, что придает симплексному методу большую гибкость. Например, ограничения заданы в виде системы.
Сначала образуем систему уравнений, для чего вводим в первое неравенство дополнительную переменную х4, а в третье неравенство — дополнительную переменную х$
Для образования единичной матрицы вводим недостающие элементы: во второе уравнение искусственную переменную Ух, а в третье у2
Целевая функция имеет вид:
• при решении задачи на максимум.
• при решении задачи на минимум.
Поставленные таким образом задачи можно решать симплексным методом.
Пример 2.8. Определим минимальное и максимальное значения целевой функции F (X) = Х + 3×2 при следующих смешанных условиях-ограничениях:
Запишем систему ограничений в виде равенств, для чего введем дополнительные переменные х% и х4, в результате получим следующую систему:
Затем введем искусственные переменные у и у2 в первое и второе уравнения.
Для постановки задачи на минимум целевую функцию запишем [10, "https://referat.bookap.info"].
С целью формулировки задачи для решения ее в табличной форме воспользуемся выражениями из системы уравнений для искусственных переменных.
которые подставим в целевую функцию.
Таким образом, стартовая точка решения определяется х=х2 = = *3 = 0, х4 = 5, у = 3, г/2 = 8, следовательно, уравнение целевой функции для симплексной таблицы будет иметь вид.
Последовательность решения задачи симплексным методом представлена в табл. 2.9.
Поскольку задача решается на минимум, то ведущий столбец выбирают по максимальному положительному числу в индексной строке в плане I (9М — 3), а все остальные преобразования проводятся по стандартной схеме до тех пор, пока не получатся в индексной строке только неположительные числа ( 2 S.
М-метод применяется для решения любых задач линейного программирования, в том числе и тех, где начальная каноническая форма не задана.
М-метод состоит во введении новых искусственных переменных, которые сразу можно взять в качестве базисных, и дальнейшем решении полученной задачи симплекс-методом.
Предположим, что исходная задача линейного программирования представлена в основной форме:
Алгоритм М-метода:
В каждое i-ое ограничение вводим искусственную переменную хn+i >0. Всего m новых искусственных переменных.
Если, то в целевую функцию L вводим m дополнительных слагаемых вида: -M×xn+1, -M×хn+2, . -M×хn+m; если же, то слагаемые вида: M×xn+1, M×хn+2, . M×хn+m, где М — произвольная очень большая константа.
Получим новую, вспомогательную задачу линейного программирования:
F(X) = c1Х1 +… + сnXn -M*Xn+1 — … -M*Xn+m => max
ai,1X1+… + ai,nXn +Xn+i = bi, (i=1,m)
Новая система ограничений характерна тем, что искусственные переменные сразу можно взять в качестве базисных:
Формируем начальное базисное решение новой М-задачи :
Решаем М-задачу симплекс-методом
Анализируем решение М-задачи в соответствии со следующими правилами :
Если в оптимальном решении М-задачи:
X" = ( X"1,… X"n, X"n+1,… X"n+m )
все искусственные переменные равны 0, то вектор
является оптимальным решением исходной ЗЛП.
Если в оптимальном решении М-задачи хотя бы одна искусственная переменная не равна 0, то исходная ЗЛП не имеет решения в силу несовместимости ограничений.
Если М-задача не имеет решения, то исходная ЗЛП также не имеет решения в силу неограниченности целевой функции на допустимом множестве.
F(X) = 4X1 +4X2 +2X3 +4X4 +3X5 +1X6 => max
-3X1 +0X2 +2X3 +3X4 +3X5 +4X6 = 1
3X1 -2X2 -1X3 +4X4 +3X5 -3X6 = 2
4X1 -2X2 +1X3 -1X4 -1X5 -1X6 = 2
2X1 +3X2 +3X3 +1X4 +2X5 -3X6 = 3
Вводим в ограничения искусственные переменные :
-3X1 +0X2 +2X3 +3X4 +3X5 +4X6 +X7 = 1
3X1 -2X2 -X3 +4X4 +3X5 -3X6 +X8 = 2
4X1 -2X2 +X3 -X4 -X5 -X6 +X9 = 2
2X1 +3X2 +3X3 +X4 +2X5 -3X6 +X10 = 3
Вводим в целевую функцию дополнительные слагаемые:
F(X) = 4X1 +4X2 +2X3 +4X4 +3X5 +X6 — MX7 — MX8 — MX9 — MX10 => max
Т.о. мы получили новую ЗЛП.
Сформируем начальное базисное решение новой М-задачи :
X'=( 0, 0, 0, 0, 0, 0, 1, 2, 2, 3 );
После решения М-задачи симплекс методом мы получили следующее оптимальное решение: X"=( 1.2, 0.77, 0.00, 0.54, 0.00, 0.75, 0.00, 0.00, 0.00, 0.00 ); В этом решении все искусственные переменные равны 0, следовательно мы нашли оптимальное решение и для исходной ЗЛП: X = ( 1.2, 0.77, 0.00, 0.54, 0.00, 0.75 ).
Читайте также: