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

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. перераспределение поставок в транспортной задаче

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

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

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

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

Если в симплекс-таблице, содержащей некоторый опорный план, все элементы 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)

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

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

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

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)

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

123 страницы (Word-файл)

Посмотреть все страницы

Фрагмент текста работы

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

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

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

Теорема 1.2 (о существовании опорного плана)

Если линейная форма ограничена сверху на непустом множестве D, то ЗЛП разрешима, то есть существует такая точка , что .

Теорема 1.3 (признак оптимальности опорного плана)

Опорный план задачи (1.18) является оптимальным, если для всех j , выполняется, где величина

(1.21)

называется симплекс – разностью или оценкой .

Теорема 1.4 (признак отсутствия оптимального плана)

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

Теорема 1.5 (признак существования лучшего опорного плана)

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

Алгоритм симплекс-метода

1. Задача должна быть приведена к каноническому виду. Система ограничений приведена к единичному базису, т.е. разрешена относительно некоторых базисных переменных (не умоляя общности, будем считать, что относительно первых m переменных) с помощью метода Жордана – Гаусса (система (1.19)). Получено соответствующее исходное опорное решение .

2. Для удобства ведения вычислений записываем все в симплекс-таблицу (табл. 1.1). Столбец «Базис» содержит список базисных переменных; следующий столбец «c j базиса» содержит коэффициенты целевой функции при базисных переменных; следующие столбцы содержат коэффициенты системы ограничений при соответствующих переменных; столбец «b i » - столбец свободных членов системы ограничений. Последняя строка содержит симплекс – разности, рассчитанные по формуле (1.21) и последняя ячейка содержит значение целевой функции =. Отметим, что симплекс – разности базисных переменных всегда равны нулю.

Таблица 1.1

c j базиса

3. Если все симплекс – разности неотрицательны, т.е. , то опорный план оптимален.

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

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

6. Выбираем разрешающий столбец «р», которому соответствует наименьшая отрицательная оценка.

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

8. Переходим к новой симплекс – таблице, в которой будет новый базис: базисная переменная на «к» - ом месте в старом базисе меняется на новую переменную . Соответствующий вектор новой базисной переменной нужно превратить в единичный. Для этого разрешающую строку делим на , чтобы на месте разрешающего элемента появилась единица. Умножая разрешающую строку на подходящие числа и складывая её с остальными строками получаем нули в разрешающем столбце. После этого выписываем новый опорный план и пересчитываем строчку оценок. Переходим к пункту 3.

Замечание об альтернативном плане.

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

В этом случае множество все оптимальных планов можно представить в виде выпуклой линейной комбинации опорных оптимальных планов:, где .

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

(1.22)

Приводим систему линейных неравенств (1.22) к каноническому виду, вводя в каждое неравенство дополнительную неотрицательную переменную. Получим систему линейных уравнений:

(1.23)

Целевая функция будет иметь вид

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

Таблица 1.2

c j базиса

Опорный план не является оптимальным, т.к. в строке оценок есть отрицательные элементы = - 3 и = - 2. Выбираем разрешающий столбец – первый, т.к. ему соответствует минимальная из отрицательных оценок = - 3. Для всех положительных элементов первого столбца вычисляем отношение . Находим минимальное из этих отношений: . Оно соответствует второй строке, следовательно, она будет разрешающей. Таким образом, разрешающий элемент показывает, что из базиса выводится переменная x 4 , а вместо неё в базисе будет переменная x 1 . Заполняем новую симплекс – таблицу (табл. 1.3). Для этого превращаем первый столбец в единичный. Умножаем вторую строку на (-1/2) и складываем с первой, записываем результат в первую строку новой симплекс – таблицы; аналогично, умножаем вторую строку на (1/2) и складываем с третьей; разрешающую строку делим на 2; четвертую переписываем без изменений.

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

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

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

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

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

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

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-е уравнение введем искусственные переменные:

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