Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Определение исходного базиса
Чтобы приступить к решению задачи линейного программирования симплексным методом, необходимо выбрать исходный базис. Выбор исходного базиса зависит от системы ограничений. Система ограничений задачи линейного программирования может быть записана в трех основных формах. 1. Система записана неравенством вида ≤ (меньше или равно). 2. Ограничения задачи линейного программирования выражены линейными уравнениями 3. Ограничения задачи выражены неравенством вида ≥ (больше или равно). При ограничениях, записанных по первой форме, в уравнения вводятся свободные переменные (по одной свободной переменной в каждом соотношении), которые и включаются в исходный базис. Если ограничения записаны в виде равенств (вторая форма ограничений), то возможны следующие приемы. 1. Если некоторая переменная входит только в j-e уравнение (соотношение), причем с коэффициентом, равным единице, то ее можно включить в исходный базис. 2. Ограничения, выраженные в виде равенств, записываются в следующем виде: где: уi - искусственная переменная, ввод которой делается с целью построения исходного базиса. Чтобы окончательное решение имело смысл, каждая искусственная переменная у,- на заключительной симплекс-итерации должна обращаться в нуль. Если на последней симплекс-итерации по крайней мере одна из переменных уi войдет в базис с положительным значением, то это означает несовместимость условий задачи, т. е. задача не имеет допустимых решений. 3. Если ограничения задачи выражены неравенством ≥, то в левую часть неравенств вводятся неотрицательные переменные с коэффициентом (-1). В полученных уравнениях дополнительные переменные не могут быть приняты за базисные, так как они входят в уравнения с отрицательным коэффициентом. Для нахождения допустимого исходного базиса, в этом случае может быть задан конкретный набор переменных, предназначенный для формирования исходного базиса. При некоторых итерациях вычислительные процедуры, предписанные правилами 1 и 2, в части, касающейся перехода от одного базиса к другому, могут оказаться неоднозначно определенными. Например, когда в результате оценки коэффициентов в строке 0 две или более двух переменных являются по правилу 1 в равной степени «перспективными» с точки зрения улучшения пробного решения, выбор одной из этих переменных осуществляется произвольным способом.
Если, согласно правилу 2, две или более двух переменных промежуточного базиса должны одновременно принять нулевые значения в силу включения в очередной базис новой переменной, из старого базиса подлежит исключению только одна из них. Другие переменные из упомянутых переменных остаются в базисе, принимая при этом нулевые значения. Базис, полученный в результате такой замены, называется вырожденным. Если на этапе применения правила 1 при выполнении какой-либо итерации обнаруживается, что ни в одну из строк ограничений переменная, включенная в очередной базис, не входит с положительным коэффициентом, то оптимальное решение является неограниченным. В этом случае значение новой базисной переменной можно (без нарушения условия неотрицательности остальных переменных) выбирать сколь угодно большим, что приводит к неограниченному возрастанию значения целевой функции.
|
|||||
Последнее изменение этой страницы: 2021-01-14; просмотров: 234; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 18.119.131.178 (0.005 с.) |