Учебное пособие: Практикум по решению линейных задач математического программирования. Возможность переход от одного опорного плана к другому

34. Признак единственности оптимального плана, множества оптимальных планов и отсутствия оптимального плана при решении задача ЛП симплекс-методом.

При решении задач симплекс-методом возможны следующие виды оптимальных решений:

1. Единственность . Если оценки всех свободных векторов строго отрицательные, то полученный опорный план является оптимальным и единственным. (см. пример в предыдущем параграфе).

2. Альтернативный оптимум (множество оптимальных решений).

Если среди неположительных оценок свободных векторов имеется хотя бы одна нулевая, то полученный опорный план будет оптимальным, но не единственным. В этом случае можно перейти к другим опорным планам (вводятся в базис векторы, которым соответствуют нулевые оценки) и, затем, общее оптимальное решение записать в виде выпуклой комбинации полученных оптимальных опорных планов.

3. ЗЛП не имеет оптимального решения, так как целевая функция не ограничена снизу . Если в симплекс таблице имеется положительная оценка, а все элементы данного столбца отрицательны и нулевые, то данный вектор можно ввести в базис. Однако никакой из базисных векторов нельзя вывести из базиса. Из этого следует, что дальнейшее уменьшение целевой функции возможно при переходе к неопорному плану.

4. ЗЛП не имеет оптимального решения, так как система ограничений противоречива. Поскольку при решении ЗЛП обычным симплекс-методом должен быть исходный опорный план, то система линейных уравнений заведомо не противоречива. Следовательно, такой случай не может встретиться при решении обычным симплекс методом.

5. Если ОДЗ состоит из одной точки, то решение такой задачи является тривиальным, и может быть получено без использования симплекс-метода.

35. В каких случая применяется метод искусственного базиса

искусственной.

36. Построение М-задачи в методе искусственного базиса

Если задача линейного программирования находится в канонической форме, однако, не во всех уравнениях присутствуют базисные переменные, т. е. исходный опорный план отсутствует. В этом случае в те уравнения, в которых нет базисных переменных, необходимо добавить с коэффициентом +1 некоторую неотрицательную переменную. Такая переменная называется искусственной.

Искусственную переменную необходимо добавить в целевую функцию с очень большим положительным числом (так как целевая функция на нахождения минимума). Это число обозначается латинской буквой M. Его можно считать равным +∞. В связи с этим иногда метод искусственного базиса называют М- методом. Такое преобразование исходной задачи называется построением расширенной задачи. Если решается задача с целевой функцией на нахождение искусственную переменную необходимо добавить в целевую функцию с очень большим положительным числом (так как целевая функция на нахождения минимума). Это число обозначается латинской буквой M. Его можно считать равным +∞. В связи с этим иногда метод искусственного базиса называют М- методом. Такое преобразование исходной задачи называется построением расширенной задачи. Если решается задача с целевой функцией на нахождение максимума, то искусственные переменные входят в целевую функцию с коэффициентом –М.

Таким образом, в расширенной задаче мы имеем опорный план (хотя некоторые из базисных переменных и являются искусственными).

Строится исходная симплекс таблица.

37. построение индексной строки в методе искусственного базиса

Строится исходная симплекс таблица, в которой индексная строка разбивается на две строки, поскольку оценки состоят из двух слагаемых. В верхней строке записывается слагаемое оценки без M, в нижней строке – коэффициенты при М. Знак оценки определяется знаком коэффициента при M, независимо от величины и знака слагаемого без M, так как M очень большое положительное число.

Таким образом, для определения вектора, который вводится в базис необходимо провести анализ нижней индексной строки. Если выводится из базиса искусственный вектор, то соответствующий столбец в последующих симплексных таблицах можно не вычислять, если нет необходимости в получении решения двойственной задачи (см. следующую тему).

После того, как все искусственные векторы будут выведены из базиса, нижняя строка будет иметь все нулевые элементы, за исключением оценок, соответствующих искусственным векторам. Они будут равны –1. Такую строку можно удалить из рассмотрения и дальнейшее решение проводить обычным симплекс-методом, если нет необходимости в получении решения двойственной задачи (см. следующую тему).

38. Критерий оптимальности в методе искусственного базиса. Признак построение начального опорного плана исходной задачи.

39. Алгоритм двойственного симплекс-метода

Алгоритм двойственного симплекс-метода:

обычным способом заполняют первую симплекс-таблицу не обращая внимания на знаки свободных членов. Считается, что такая задача должна иметь исходный единичный базис.

Выбирают направляющую строку по наибольшему по абсолютной величине отрицательному элементу столбца свободных членов А0

Выбирают направляющий столбец по наименьшему по абсолютной величине отношению элементов индексной строки к отрицательным элементам направляющей строки.

Пересчитывают симплексную таблицу по правилу полных жордановых исключений

проверяют полученный план на допустимость. Признаком получения допустимого опорного плана является отсутствие в столбце А0 отрицательных элементов. Если в столбце А0 имеются отрицательные элементы то переходят ко второму пункту. Если же их нет, то переходят к решению полученной задачи обычным способом.

признаком получения оптимального решения двойственным симплекс-методом является критерий оптимальности обычного симплекс-метода.

41. Открытые и закрытые транспортные модели. Переход от открытой транспортной модели к закрытой.

Типы транспортных задач.

Имеются m поставщиков однородной продукции с известными запасами продукции и n потребителей этой продукции с заданными объёмами потребностей. Известны так же удельные затраты на перевозку.

Если сумма объёмов запасов продукции равна объёму потребностей всех потребителей, то такая задача называется закрытой транспортной задачей

(т. е. если ∑ Ai = ∑ Bj), в противном случае транспортная задача называется открытой . Для решения транспортной задачи необходимо, чтобы она была закрытой.

Открытую транспортную задачу можно преобразовать к закрытой следующим образом.

Пусть ∑Ai > ∑Bj. В этом случае необходимо ввести фиктивного n+1 потребителя с объёмом потребностей ∑Ai – ∑Bj Удельные затраты на перевозку от поставщиков к фиктивному потребителю полагаются равными 0, так как на самом деле такие перевозки осуществляться не будут и некоторая часть продукции останется у поставщиков.

Если ∑Bj > ∑Ai . В этом случае необходимо ввести фиктивного m+1 поставщика с объёмом запасов∑Bj – ∑Ai . Удельные затраты на перевозку от фиктивного поставщика к потребителям полагаются равными 0, так как на самом деле такие перевозки осуществляться не будут и некоторую часть продукции потребители недополучат.

42. Способы построения первоначального распределения в транспортной задаче: метод северо-западного угла и метод наименьшего элемента в матрице.

Северо-западный прием построения опорного плана. Согласно этому приему формирование величин перевозок начинается с с.-з. уголка таблицы, т.е. с клетки x11. По этому приему прежде всего распределяется товар первого поставщика. Причем первый поставщик сначала предельно возможно удовлетворяет первого потребителя. Затем, если у поставщика товар еще остался,

Метод наименьшего элемента в матрице.

Сущность метода заключается в том, что максимально возможная поставка всегда проставляется в клетку, которой соответствует наименьший тариф матрицы.

Сначала делаем пометки (например, знаком ▼) в тех клетках строк, в которых наблюдается самая меньшая цена по строке. Затем обходим таблицу по столбикам и делаем такие же пометки в клетках, в которых самая маленькая цена по столбикам.

Дальнейшее распределение делается сначала предельно возможно по клеткам с двумя отметками, потом - с одной, а затем делается добалансировка задачи до (m + n – 1) заполнений. Заполнения организуем при прохождении таблицы слева направо и сверху вниз.

43. Свойства транспортных задач

Транспортная задача обладает некоторыми свойствами, которые можно отразить следующими теоремами.

Теорема 1. Закрытая транспортная задача всегда имеет решение.

Теорема 2. Если объёмы запасов продукции и объёмы потребностей является целыми числами, то и решение транспортной задачи также будет целочисленным.

Теорема 3. система ограничений закрытой транспортной задачи всегда линейно-зависима.

Из этой теоремы следует, что распределение закрытой транспортной задачи всегда имеет m + n – 1 базисную переменную и (m – 1) (n – 1) свободные временные.

44. Вырожденное распределение в транспортных задачах, избавление от вырожденности. Вычеркиваемая комбинация.

Распределение называется вырожденным, если количество клеток меньше чем m + n – 1.

45. Теорем оптимальности транспортной задачи.

Теорема. Если для некоторого распределения транспортной задачи вы-

полняются условия:

а). ui+vj = сij для занятых клеток

б) ui+vj ≤ сij, для свободных клеток,

то данное распределение является оптимальным.

Величины ui называют потенциалами строк, а величины vj называют потенциалами столбцов.

46. Потенциалы и способы их расчета.

Для нахождения потенциалов строк и столбцов пользуются следующими рассуждениями, исходя из условия а) теоремы оптимальности.

Количество уравнений исходя из этого условия равняется m + n – 1, а количество неизвестных ui и vj равняется m + n. Т.о. количество переменных больше количества уравнений, причем все уравнения линейно независимы. Решение такой системы линейных уравнений является неопределенным, поэтому одному из потенциалов нужно присвоить любое значение. На практике ui = 0. получается система из m + n – 1 уравнений с m + n – 1 неизвестными переменными. Эту систему можно решить любым методом. На практике для расчета потенциалов рассматриваются занятые клетки, для которых один их потенциалов известен, и исходя из условия а) теоремы вычисляются значения остальных неизвестных потенциалов.

47. расчет оценок оптимальности распределения транспортных задач и критерий оптимальности.

Исходя из соотношения б) теоремы можно записать следующую формулу для вычисления оценок: δ ij = ui +vj – сij. Для того, чтобы оценки не перепутать с объёмами перевозок, они (оценки) заключаются в круги.

Оценки оптимальности в свободных клетках ТЗ представляют собой критерий оптимальности, с помощью которого осуществляется проверка распределения на оптимальность. Если оценки всех свободных клеток меньше или равны нулю, то данное распределение является оптимальным.

48. перераспределение поставок в транспортной задаче

Если распределение не является оптимальным, то необходимо осуществить перераспределение поставок.

Для перераспределения осуществляют построение цикла пересчета. В качестве клетки выбирается клетка с наибольшей положительной оценкой. Эта клетка помечается знаком «+», то есть в неё необходимо записать некоторый объём поставки. Но тогда нарушится баланс по данному столбцу, следовательно, одну из занятых клеток данного столбца необходимо пометить знаком «-», то есть уменьшить объём поставки на такую же величину. Но тогда изменится баланс по данной строке, следовательно, какую-то занятую клетку данной строки необходимо пометить знаком «+». Данный процесс продолжается до тех пор, пока не поставлен знак «-» в строке, где находилась исходная клетка.

Для любой свободной клетки существует цикл пересчета и притом единственный.

Симплекс-метод решения задач линейного программирования

Симплексный метод – это аналитический метод решения ЗЛП, реализующий алгоритм графического метода аналитически, без построения чертежа.

Таким образом, суть симплексного метода состоит в направленном переборе допустимых решений, при котором значение целевой функции на каждом шаге лучше, чем на предыдущем. Процесс повторяется до тех пор, пока не будет получено оптимальное по значению целевой функции решение.

Симплекс метод может использоваться для решения ЗЛП с любым количеством неизвестных.

Техническая реализация симплексного метода связана с решением систем линейных уравнений, для чего используют метод Гаусса, разработаны табличные формы и правила преобразования симплексных таблиц.

Симплекс-метод с естественным базисом применяется, если ЗЛП задана в канонической форме записи, и матрица в КЗЛП содержит единичную подматрицу размером m´m . Для определённости положим, что первые m векторов матрицы системы уравнений составляют единичную матрицу. Тогда первоначальный план выбирается следующим образом:

Проверка на оптимальность опорного плана проходит с помощью признака оптимальности, переход к другому плану проводится с помощью преобразования Жордана-Гаусса при использовании математического признака оптимальности. Полученный опорный план снова проверяется на оптимальность и т.д.

Математический признак оптимальности состоит из следующих двух теорем:

1. Если для всех векторов A 1 , A 2 , … , A n выполняется условие , где , то полученный опорный план является оптимальным. В сумме для определения Z j участвуют m слагаемых, то есть в ней участвуют не все коэффициенты целевой функции c j , а лишь с номерами соответствующими номерам текущих базисных векторов A i , количество которых равно m .

2. Если для некоторого вектора, не входящего в базис, выполняется условие , то следует искать новый опорный план, для которого значение ЦФ больше, чем для текущего. При этом возможны два случая:

а) если все компоненты вектора A k , подлежащего вводу в базис, неположительны, то ЗЛП не имеет решения (конечного оптимума нет);

б) если имеется хотя бы одна положительная компонента у вектора A k , подлежащего ввода в базис, то можно получить новый опорный план.

На основании признака оптимальности в базис вводится вектор A k , давший минимальную отрицательную величину симплекс-разности:

Чтобы выполнялось условие неотрицательности значений опорного плана, выводится из базиса вектор A r , который даёт минимальное положительное оценочное отношение

Строка A r , в которой находился старый базисный вектор, называется направляющей, столбец A k и элемент a rk - направляющими.

Элементы направляющей строки в новой симплекс-таблице вычисляются по формулам:

а элементы любой другой i -й строки - по формулам:

Значения нового опорного плана рассчитываются по аналогичным формулам:

,

Процесс продолжают либо до получения оптимального плана, либо до установления неограниченности ЦФ. Если среди разностей Δ j , j=1, 2, … , n оптимального плана нулевыми являются только разности, соответствующие базисным векторам, то это говорит о единственности оптимального плана. Если же нулевая оценка соответствует вектору, не входящему в базис, то в общем случае это означает, что оптимальный план не единственный.

Пример. Решить ЗЛП по модели:

найти ,

при ограничениях

Эта ЗЛП сводится к каноническому виду путём введения дополнительных переменных x 3 и x 4 :

КЗЛП имеет необходимое количество (два) нулевых столбцов при x 3 и x 4 , то есть обладает очевидным начальным опорным планом (0,0,300,150).

Решение осуществляется симплекс-методом с естественным базисом с оформлением расчётов в симплекс-таблицах:

Номер симплекс-таблицы	Базис	с j	с j					Q
B	A 1	A 2	A 3	A 4
	← A 3
A 4
Δ	-		-2	-3			-
I	→ A 2			1/3		1/3
← A 4			2/3		-1/3
Δ	-		-1				-
II	A 2					1/2	-1/2	-
→ A 1					-1/2	3/2	-
Δ	-				1/2	3/2	-

Остановимся подробнее на заполнении симплекс-таблиц и, соответственно, получении решения КЗЛП.

В верхнюю строку общей таблицы внесены коэффициенты c j , j=1, 2, 3, 4 при переменных в ЦФ. В первые две строки нулевой симплекс-таблицы внесены вектор-столбцы B, A 1 , A 2 , A 3 , A 4 , соответствующие векторной форме записи КЗЛП. Поскольку исходным базисом является пара векторов A 3 , A 4 , они внесены в колонку под названием “Базис” нулевой симплекс-таблицы. При этом, A 3 внесён в первую строку, что определяется единицей, являющейся первым элементов этого вектора, а вектор A 4 - во вторую строку, у этого вектора единица находится во второй строке. В столбец под названием “ c i ” внесены коэффициенты целевой функции, соответствующие базисным векторам A 3 , A 4 , то есть c 3 , c 4 . Они оба равны нулю. Далее вычисляются значения разностей Δ для векторов B, A 1 , A 2 , A 3 , A 4 и заносятся в третью строку нулевой таблицы. Для вектора A 1 :

для вектора :

Аналогично , .

Для вектора B вычисление разности несколько упрощается, поскольку ему нет соответствующего коэффициента c j , j=1, 2, 3, 4 в ЦФ:

Не для всех векторов A 1 , A 2 , A 3 , A 4 полученные разности являются неотрицательными, поэтому выбранный нами опорный план не является оптимальным. Нам необходимо искать новый опорный план, а для этого нужно заменить один из входящих в базис векторов A 3 , A 4 .

Для определения вектора, который мы должны ввести, ищем вектор, для которого значение разности получилось минимальным. Таким является вектор, A 2 , ему соответствует минимальное значение разности: -3. То есть индекс k из формулы (8.4) равен 2. Для определения вектора, который мы должны будем вывести из базиса, вычисляем значения Q для каждой строки по формуле (8.5) и вносим их в последнюю колонку. В данном случае в каждой строке мы должны величину элемента вектора B разделить на величину элемента вектора A 2 . В первой строке получим 300/3=100, во второй: 150/1=150. Меньше получилось отношение в первой строке, ей соответствовал базисный вектор A 3 , следовательно, индекс r в формуле (8.5) равен 1, a rk =3 (выделен в таблице рамкой), а выводить из базиса мы будем вектор A 3 (обозначено в таблице стрелкой).

Поскольку среди элементов вектора A 2 , который должен быть введён в базис, имеются положительные, то можно получить новый опорный план и решение следует продолжить.

После этого заполняется вторая симплекс-таблица. Для перерасчёта элементов векторов B, A 1 , A 2 , A 3 , A 4 используются формулы (8.6)-(8.8). Они несколько отличаются для определения элементов направляющей строки (в нашем случае первая) и для определения элементов прочих строк. Распишем вычисления нескольких элементов:

Другие элементы первой симплекс-таблицы вычисляются аналогично тому, как мы это делали для нулевой таблицы. Поскольку не все разности в первой симплекс-таблице неотрицательны, возникает необходимость продолжить расчёты.

Как мы видим, в результате расчётов во второй симплекс-таблице с базисными векторами A 2 , A 1 все разности получились неотрицательные, что означает достижение оптимального плана (75; 75; 0; 0). Симплекс-разность для вектора В равна искомому максимальному значению ЦФ - 375.

Теорема (о конечности симплекс-алгоритма). Если существует оптимальное решение ЗЛП, то существует и базисное оптимальное решение. Последнее всегда может быть получено с помощью симплекс-метода, причём начинать можно с любого исходного базиса.

Признак оптимальности опорного плана

Если в симплекс-таблице, содержащей некоторый опорный план, все элементы f-строки (не считая свободного члена) неотрицательны, то этот опорный план является оптимальным.. Пусть в f-строке табл. 2.b 0j > (i=1, ..., n m). В опорном плане х 0 , содержащемся в этой таблице, значения всех свободных переменных x m+j равны нулю и f(х 0) =b 00 . Если же увеличивать какую-либо из свободных переменных x m+ j, то, как видно из равенства (2.5), в силу неотрицательности b 0j значение f(х) начнет уменьшаться. Следовательно, при x о функция f(х) достигает наибольшей величины, а значит, х 0 действительно является оптимальным опорным планом.

Возможность переход от одного опорного плана к другому

Как уже говорилось выше, суть симплекс-метода в процессе доказательства следующего признака: если в f-строке симплекс-таблицы, содержащей некоторый опорный план, есть хотя бы один отрицательный элемент (не считая свободного члена), которому соответствует столбец с хотя бы одним положительным элементом, то можно, преобразовав базис, перейти к другому опорному плану с большим значением целевой функции.

Докажем этот признак. Установим правила выбора переменных для такого преобразования начального базиса Б о с опорным планом х 0 в новый базис Б 1 с опорным планом х 1 при котором; значение функции f увеличивается, т. е. f(x i)>f(x 0). Тогда по правилу пересчета элементов из симплекс-таблицы преобразуем к новому базису, что позволит найти компоненты нового опорного плана.

Допустим, что в табл. 2.1, например, b 0s <0, а среди элементов b is s-го столбца есть хотя бы один положительный. Полагая в равенстве (2.5) все свободные переменные х m+j кроме x m+s , равными нулю, получаем f = b oo -- b os xm+s . Из этого равенства видно, что при увеличении x m+s значение f тоже возрастает. Таким образом, при указанных в признаке условиях действительно есть возможность увеличить f(x), переходя к планам, в которых x m+s принимает положительные значения, а все остальные компоненты x m+j по-прежнему равны нулю. Покажем, что среди таких планов существует и опорный. Тем самым будет найден путь направленного преобразования базиса Б о в новый базис Б 1 . В самом деле, если переменная x m+s принимает положительное значение в некотором опорном плане, значит, она является в нем базисной компонентой (в опорном плане x о она была свободной компонентой и равнялась нулю). Поэтому прежний базис следует преобразовать за счет включения в него переменной x m+s . Но здесь предстоит решить два вопроса:

1) какую из переменных следует вывести из прежнего базиса, чтобы освободить место для переменной x m+s ;

2) какое значение должна принимать новая базисная переменная x m+s в новом опорном плане.

Для решения поставленных вопросов допустим, что в равенствах (2.4) все x m+j , кроме x m+s , равны нулю. Тогда

x i = b io -b is x m+s (i=l, ..., m)

Из этих равенств видно, что с возрастанием x m+s значения тех базисных переменных х i для которых коэффициенты b is <0, тоже будут расти, оставаясь положительными. Значит, на отрицательные коэффициенты b is можно внимания не обращать, так как они не влияют на знак базисных переменных. Иначе обстоит дело с базисными переменными, у которых b is >0. С увеличением x m+s значения этих переменных станут уменьшаться, и наступит момент, после которого они будут принимать отрицательные значения и перестанет выполняться условие (2.3). Этого допустить нельзя. Поэтому выясним, до какого предельного значения можно увеличивать x m+s , не нарушая условия неотрицательности базисных переменных. С этой целью выпишем из системы (2.6) те равенства, в которых b is >0. Допустим, что это касается равенств с номерами i=d,…,k,…,p:

x d =b do -- b ds x m+s ,

…………………..

x k =b k0 - b ks x m+s ,

………………….

x p =b p0 - b ps x m+s .

Базисные переменные х d , ..., x k , ..., x p будут оставаться неотрицательными до тех пор, пока x m+s удовлетворяет системе неравенств

b do - b ds x m+s >0, x m+s

……………… ………………

b k0 - b ks x m +s >0 или x m+s < b ko /b ks

……………… ………………

b p0 - b ps x m+s >0 x m+s < b po /b ps

т. е. при x m+s

Пусть наименьшая из дробей b io /b is соответствует i = k, т.е.

min { b io /b is }= b k0 /b ks .

Тогда можно сказать, что пока x m+s не превышает величины b k0 /b ks , т. е. x m+s 0, то переменная х k станет равной пулю: x k = b k0 -- b ks b ko /b ks =0, и тем самым будет произведено преобразование базиса Б о = {х 1 ; ...; x k ; ...; х m } в новый базис, при котором переменная x m+s из группы свободных переходит в базисные, а переменная х k занимает место x m+s в группе свободных. При этом все остальные свободные переменные по-прежнему равны нулю, а остальные базисные переменные по-прежнему положительны. Следовательно, базисный план х 1 в новом базисе Б 1 ={х 1 ; ...; x m+s ; ...; x m } будет иметь m положительных компонент и m-n нулевых. В плане x 1 некоторые базисные переменные могут принять нулевые значения в двух случаях:

1) когда в плане х 0 имеются базисные переменные, равные нулю;

2) когда наименьшая из дробей b io /b is будет соответствовать двум или нескольким номерам i.В нашем же случае она соответствует только i = k.

Переменная, подлежащая включению в базис, определяется отрицательным элементом f-строки. Из равенства f =b oo - b os x m+s ясно, что при b 0s <0 и фиксированном x m+s >0, значение f(х) зависит от абсолютной величины коэффициента b 0s: чем больше |b 0s |, тем большее значение получит f(х) в новом базисе. Но из этого равенства видно также, что значение целевой функции в новом базисе зависит и от величины, принимаемой новой базисной переменной x m+s . Будем выбирать переменную, вводимую в базис, ориентируясь лишь на отрицательные элементы f-строки. Поэтому, когда в f-строке несколько отрицательных элементов, в базис будем вводить переменную x m+j ,соответствующую отрицательному элементу с наибольшей абсолютной величиной. Столбец коэффициентов при переменной, включаемой в базис, называют разрешающим. Таким образом, выбирая переменную, вводимую в базис (или выбирая разрешающий столбец) по отрицательному элементу f-строки, мы обеспечиваем возрастание функции f.

Немного сложней определяется переменная, подлежащая исключению из базиса. Для этого составляют отношения свободных членов к положительным элементам разрешающего столбца (такие отношения называют симплексными) и находят среди них наименьшее, которое и определяет строку (разрешающую), содержащую исключаемую переменную. Выбор переменной, исключаемой из базиса (или выбор разрешающей строки), по минимальному симплексному отношению гарантирует положительность базисных компонент в новом опорном плане.

Итак, мы доказали, что при указанных в признаке условиях действительно можно перейти от одного опорного плана к другому с большим значением целевой функции f(х).

Отметим, что нам уже известно значение новой базисной переменной x m+s в новом опорном плане: оно равно b ko /b ks . Что же касается численных значений остальных базисных переменных в новом опорном плане и соответствующего значения f(х), то их можно найти лишь после того, как измененная система базисных переменных х 1 ;..., x m+s ; ...,х m будет выражена через измененную систему свободных переменных x m+1 ,…,x k ,…, х n . Для этого установим; правила, по которым осуществляется преобразование условий задачи от одного базиса к другому.

Коэффициент b ks = 0 при x m+s в этом уравнении называют разрешающим элементом. В равенстве (2.7) новая базисная переменная x m+s выражена через свободные переменные, среди которых находится теперь и бывшая базисная переменная х k . Таким образом, переменные x m+s и x k поменялись ролями.

Аналогично выразим через новый набор свободных переменных и остальные базисные переменные. С этой целью значение x m+s из подставим в остальные равенств (обозначим f через x 0 ,тогда равенство будет входить в систему при i= 0)

Приведение системы к новому базису называется симплексным преобразованием. Если симплексное преобразование рассматривать как формальную алгебраическую операцию, то можно заметить, что в результате этой операции происходит перераспределение ролей между двумя переменными, входящими в некоторую систему линейных функций: одна переменная из зависимых переходит в независимые, а другая, наоборот, - из независимых в зависимые. Такая операция известна в алгебре под названием шага жорданова исключения.

Признак оптимальности опорного плана. Симплекс таблица

Для решения задач обычно условия заносят в таблицу, которая называется симплексной. Перед занесением систему ограничений приводят к предпочтительному виду.

при ограничениях

Система ограничений данной задачи имеет предпочтительный вид. Составим симплексную таблицу.

Находим начальный опорный план

Обозначим через Б множество базисных переменных, через В- множество свободных переменных. Очевидно, при, . Значения называются оценками свободных переменных.

Признак оптимальности опорного плана:

1) Опорный план доставляет целевой функции минимальное значение, если для него все оценки свободных переменных неположительны.

2) Опорный план доставляет целевой функции максимальное значение, если все оценки свободных переменных неотрицательны.

Строка функции цели называется Z-строкой или индексной строкой. Начальный опорный план Х 0 =(1/2;3/2;0;2;0) и Z(Х 0)=-9/2. Т.к. все оценки индексной строки неположительны, то план Х 0 - оптимален.

Переход к нехудщему опорному плану. Симплексные преобразования

Рассмотрим задачу

Начальный опорный план

Если все оценки свободных переменных, то план Х 0 - оптимальный. Если существуют положительные оценки свободных переменных, то столбец, которому соответствует наибольшее значение?j называется разрешающим. Обозначим его номер j o , а величину x jo введем в базис.

Т.к. ? jо > 0, то, не изменяя нулевых значений всех свободных переменных, можно уменьшить функцию Z за счет увеличения x jo .

Чтобы перейти к новому опорному плану из базиса нужно вывести одну из переменных.

Значение xj o нужно увеличить так, чтобы ни одно из значений базисных переменных x i не было отрицательным. Т.е.

Возможны два случая.

1) Все элементы разрешающего столбца j o неположительны, т.е. a ijo ? 0. Если при решении задачи на min (max) в индексной строке имеются положительные (отрицательные) оценки свободных переменных, а в столбце переменной xj o нет ни одного положительного элемента, то целевая функция не ограниченна снизу (сверху) на множестве допустимых планов задачи.

2) Если среди элементов разрешающего столбца имеются положительные, то x jo можно увеличивать до тех пор, пока не нарушается система неравенств:

Отсюда получаем

Пусть данное выражение выполняется при i=i o , тогда

Если условие выполняется при нескольких i, то в качестве i o можно выбрать любое. Строку i o называют разрешающей, элемент - разрешающим.

Новое значение целевой функции:

В результате преобразований целевая функция уменьшилась. Теперь новую базисную переменную нужно выразить через свободные и подставить в систему ограничений и целевую функцию. Причем старая базисная переменная становится свободной.

Правила симплексного преобразования:

1) В индексной строке симплекс-таблицы найти наибольший положительный (или отрицательный) элемент. Столбец соответствующий этому элементу - разрешающий.

2) Вычислить отношение свободных членов уравнения к положительным элементам разрешающего столбца. Данное отношение называется симплекс-отношением. Найти наименьшее из симплекс-отношений, оно соответствует разрешающей строке.

3) На пересечении разрешающей строки и разрешающего столбца находится разрешающий элемент. Если имеется несколько одинаковых по величине симплекс-отношений, то выбирают любое из них.

4) Неизвестные элементы, соответствующие разрешающим столбцу и строке, меняются местами.

5) Переход к следующей таблице. Элементы разрешающей строки новой таблицы будут равны

6) Элементы разрешающего столбца равны нулю, за исключением, т.к. x jo - базисная величина.

7) Все остальные элементы находятся по формулам

Для нахождения элементов в исходной таблице выделяется прямоугольник, вершинами которого служат нужные для вычисления элементы. Диагональ, содержащую разрешающий и искомый элемент новой таблицы, называется главной, а другая - побочной. Из произведения угловых элементов главной диагонали вычитается произведение угловых элементов побочной диагонали и полученное число делят на разрешающий элемент. Это правило прямоугольника.

8) вычисляем элементы индексной строки

Для контроля вычислений можно вычислить

9) алгоритм продолжается до тех пор, пока не будет достигнуто условие оптимальности.

а) Опорный план доставляет целевой функции минимальное значение, если для него все оценки свободных переменных неположительные.

б) Опорный план доставляет целевой функции максимальное значение, если все оценки свободных переменных неотрицательны.

Пример: Решить симплекс-методом задачу линейного программирования

Оптимальный план X (7;0;0;42;2) и Z(x)=72.

Пример задачи с искусственным базисом .

Приведем задачу к каноническому виду:

Во 2-е и 3-е уравнение введем искусственные переменные:

Составим симплексную таблицу:

Табличный вид ЗЛП. Симплекс - таблицы.

СИМПЛЕКСНЫЙ МЕТОД РЕШЕНИЯ ЗЛП

3.1. Общая характеристика и основные этапы симплекс – метода

Основоположниками симплекс-метода являются советский математик Л.В. Канторович и американский математик Дж. Данциг.

Симплекс-методом можно решить любую ЗЛП или обнаружить ее неразрешимость. Многие специальные классы ЗЛП можно решить другими, более эффективными для этих классов методами. Однако преимущество симплекс-метода - его универсальность. Почти для всех ЭВМ разработаны стандартные программы для решения ЗЛП симплекс - методом.

Опишем общую идею симплекс-метода.

Считаем, что ЗЛП записана в каноническом виде и целевую функцию нужно минимизировать. Как мы уже знаем, оптимальный план следует искать среди опорных планов ЗЛП. Симплекс-метод не перебирает все опорные планы (что было бы часто невозможно из-за их огромного количества), а, начиная с некоторого исходного опорного плана, он последовательно переходит к другим опорным планам с уменьшением целевой функции. Симплекс-метод прекращает свою работу тогда, когда либо будет найден оптимальный опорный план, либо установлена неразрешимость задачи.

При решении ЗЛП симплекс-методом можно выделить следующие этапы:

1) приведение ЗЛП к каноническому виду;

2) приведение системы линейных уравнений к жордановой форме с неотрицательными правыми частями с одновременной проверкой на неразрешимость ЗЛП из-за противоречивости системы линейных ограничений;

3) исследование опорного плана на оптимальность;

4) исследование ЗЛП на неразрешимость из-за неограниченности снизу на ОДР целевой функции;

5) переход к новому, "лучшему" опорному плану.

Для сокращения и упорядочения записей при решении ЗЛП симплекс-методом используются так называемые симплекс-таблицы. Чтобы воспользоваться симплекс-таблицей, ЗЛП нужно привести к табличному виду. Делается это так.

Пусть ЗЛП записана в каноническом виде (2.3-2.5). Для приведения ЗЛП к табличному виду систему (2.4) следует сначала привести к жордановой форме с неотрицательными правыми частями. Предположим, что эта жорданова форма имеет вид (2.6). Выразим из (2.6) базисные переменные через свободные:

Подставив в целевую функцию (2.3) вместо базисных переменных их выражения через свободные переменные по формулам (3.1), исключим тем самым из целевой функции базисные переменные. Целевая функция примет вид:

В табличном виде целевая функция записывается так:

где .

Отметим следующие особенности табличного вида ЗЛП:

а) система линейных уравнений приведена к жордановой форме с неотрицательными правыми частями;

б) из целевой функции исключены базисные переменные и она записана в форме (3.3).

Перейдем теперь к описанию симплекс-таблицы. Пусть ЗЛП записана в табличном виде:

(3.4)

Тогда заполненная симплекс-таблица выглядит так.