![]() Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь FAQ Написать работу КАТЕГОРИИ: ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву ![]() Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Искусственное начальное решение.Содержание книги
Похожие статьи вашей тематики
Поиск на нашем сайте
Часто при начальном допустимом базисном решении гарантировалось, что все последующие базисные решения, получаемые при выполнении симплекс-метода, также будут допустимыми. В задачах линейного программирования, где все ограничения являются неравенствами типа "≤" (с неотрицательной правой частью), дополнительные (остаточные) переменные позволяют сформировать начальное допустимое базисное решение. Естественно, возникает вопрос: как найти начальное допустимое базисное решение в задачах ЛП, где есть ограничения в виде равенств или неравенств типа "≥"? Наиболее общим способом построения начального допустимого базисного решения задачи ЛП является использование искусственных переменных. Эти переменные в первой итерации играют роль дополнительных остаточных переменных, но на последующих итерациях от них освобождаются. Разработано два тесно связанных между собой метода нахождения начального решения, которые используют искусственные переменные: · М-метод · Двухэтапный метод. М-метод. Пусть задача ЛП записана в стандартной форме. Для любого равенства i, в котором не содержится дополнительная остаточная переменная, введем искусственную переменную Ri, которая далее войдет в начальное базисное решение. Но, поскольку эта переменная искусственна (другими словами, не имеет никакого "физического смысла" в данной задаче), необходимо сделать так, чтобы на последующих итерациях она обратилась в нуль. Для этого в выражение целевой функции вводят штраф. Переменная Ri, с помощью достаточно большого положительного числа М штрафуется путем ввода в целевую функцию выражения -MRi в случае максимизации целевой функции и выражения +MRi, — в случае минимизации. Вследствие этого штрафа естественно предположить, что процесс оптимизации симплекс-метода приведет к нулевому значению переменной Ri. Следующий пример проясняет детали этого метода. Пример. Минимизировать При выполнении условий Стандартная форма этой задачи получается в результате добавления дополнительной (избыточной) переменной х3 во второе неравенство и дополнительной (остаточной) переменной х4 в третье неравенство. Эта задача в стандартной форме будет записана следующим образом:
Минимизировать z = 4x1 + х2 При выполнении условий В полученной задаче первое и второе уравнения не имеют дополнительных (остаточных) переменных, которые можно ввести в базисное решение. Поэтому введем в эти уравнения искусственные переменные R1 и R2, а в целевую функцию добавим штраф MRl + MR2. В результате получим следующую задачу ЛП. Минимизировать При выполнении условий В этой модифицированной задаче переменные R1 и R2 и х4 можно использовать в качестве начального допустимого базисного решения. В результате получим следующую симплекс-таблицу. Прежде чем применять симплекс-метод, надо согласовать значения в z-строке с остальной частью таблицы. В частности, значение функции z, соответствующее начальному базисному решению R1 = 3, R2 = 6 и х4 = 4, должно равняться ЗМ+ 6М + 0 = 9M, а не 0, как показано в таблице. Это противоречие связано с тем, что переменным R1 и R2 соответствуют ненулевые коэффициенты (-М, -М) в строке z. Чтобы сделать эти коэффициенты нулевыми, следует умножить элементы строк R1 и R2 на величину М, и затем сложить эти строки с z-строкой. (Обратите внимание на "подсвеченные" единицы в этих строках — если бы эти коэффициенты были отличны от единиц, то необходимо было бы сначала разделить все элементы этих строк на данные коэффициенты). Кратко это действие можно записать следующим образом. Новая z-строка = старая z-строка + М х R1-строка + М х R2-строка Измененная симплекс-таблица примет следующий вид: Отметим, что теперь z = 9М, что соответствует базисному решению R1 = 3, R2 = 6 и x4 =4. Последняя таблица готова к применению симплекс-метода с использованием условий оптимальности и допустимости. Поскольку мы минимизируем целевую функцию, находим наибольший положительный коэффициент в z-строке. Наибольший коэффициент -4 + 7М соответствует переменной x1, которая и будет вводимой. Условие допустимости указывает на переменную R1 в качестве исключаемой. Поскольку вводимая и исключаемая переменные определены, новую симплекс- таблицу можно вычислить с помощью метода Гаусса-Жордана. Заметим, что вычисления в z-строке, где присутствует М, следует проводить алгебраически. Так, для получения новой z-строки надо новую ведущую строку умножить на -(-4 + 7М) и сложить с текущей z-строкой. В результате получим следующую таблицу:
Отметим, что уже первая итерация исключила из базисного решения искусственную переменную R1, что является результатом включения штрафа в целевую функцию. Последняя таблица показывает, что следующими (вводимой и исключаемой) переменными будут х2 и R2 соответственно. Конечно, для получения оптимального решения может потребоваться больше двух итераций. В данной задаче оптимальным решением будет х1 = 2/5, х2 = 9/5, х3 = 1 и z = 17/5. При использовании М-метода следует обратить внимание на следующие два обстоятельства: 1. Использование штрафа М может и не привести к исключению искусственной переменной в конечной симплекс-итерации. Если исходная задача линейного программирования не имеет допустимого решения (например, система ограничений несовместна), тогда в конечной симплекс-итерации по крайней мере одна искусственная переменная будет иметь положительное значение. Это "индикатор" того, что задача не имеет допустимого решения. 2. Теоретически применение М-метода требует, чтобы М —> °°. Однако с точки зрения компьютерных вычислений величина М должна быть конечной и, вместе с тем, достаточно большой. Как понимать термин "достаточно большая" — это открытый вопрос. Величина М должна быть настолько большой, чтобы выполнять роль "штрафа", но не слишком большой, чтобы не уменьшить точность вычислений. На практике вы должны помнить о возможных
|
||||||
Последнее изменение этой страницы: 2016-08-01; просмотров: 724; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.15.179.238 (0.011 с.) |