Признак неограниченности целевой функции — КиберПедия 

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

Общие условия выбора системы дренажа: Система дренажа выбирается в зависимости от характера защищаемого...

Признак неограниченности целевой функции



 

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

С экономической точки зрения неограниченность целевой функции ЗЛП свидетельствует только об одном: разработанная модель недостаточно точна.

Пример 2. Решить симплексным методом задачу

Решение

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

Ограничения-неравенства имеют вид £, следовательно, целевая функция должна быть на максимум. В нашем случае задачу на минимум можно заменить задачей максимизации. Умножив целевую функцию на –1, получаем

Итак, запишем задачу в каноническом виде. Для этого добавим к левым частям неравенств дополнительные переменные x3, x4, x5. В целевую функцию они сводятся с коэффициентами, равными нулю:

Задача имеет предпочтительный вид.

Переменные x3, x4, x5 – базисные, а x1, x2 – свободные. Положим, что x1 = x2 = 0, тогда x3 = 14, x4 = 3, x5 = 36. Следовательно, x0 = (0; 0; 14; 3; 36) является начальным опорным планом.

При этом 6 × 0 + 3 × 0 + 0 × 14 + 0 × 3 + 0 × 36 = 0. Заносим условие задачи в симплексную табл. 2.

Таблица 2

БП сБ А0 x1 x2 x3 x4 x5  
 
x3 (2)
x4  
x5  
–6 –3  
               

 

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

 

Таблица 3

БП сБ А0 x1 x2 x3 x4 x5
x1
x4
x5 –5 –2

 

Разрешающий столбец находим по max{|–6|; |–3|} = 6. Разрешающая строка определяется по минимуму отношений свободных членов к положительным элементам разрешающего столбца, т. е.

 

.

 

На пересечении разрешающего столбца и разрешающей строки находится разрешающий элемент 2.

В табл. 3 вместо x3 в базис вводим переменную x1.

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



В индексной строке табл. 3 нет отрицательных элементов. Следовательно, мы получаем оптимальный план x* = хопт = (7; 0; 0; 3; 8). Тогда = z(хопт) = 42, zmin = z(хопт) = –42.

Ответ: хопт = (7; 0; 0; 3; 8), zmin = –42.

 

Пример 3. Решить задачу

 

 

Решение

Сведем задачу к каноническому виду. Получим

 

 

Занесем условие в симплексную табл. 4. Начальный опорный план имеет вид x0 = (0; 0; 3; 10), z(x0) = 0.

Таблица 4

БП сБ А0 x1 x2 x3 x4
x3 –1
x4
zjcj –2 –1
           

 

Задача решается на максимум. Опорный план x0 неоптимальный, так как существуют отрицательные оценки. Находим разрешающий столбец по max{|–2|, |–1|} = 2.

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

Ответ: .

2.9. Метод искусственного базиса (М-задача)

 

Решение задачи линейного программирования симплекс-методом начинается с нахождения какого-либо опорного плана.

Рассмотрим третий случай построения начального опорного плана (первый и второй описаны в пункте 2.1).

Пусть система ограничений имеет вид

 

.

 

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

 

.

 

Теперь система ограничений не имеет предпочтительного вида, так как дополнительные переменные xn+i входят в левую часть (при bi 0) с коэффициентами, равными –1. В этом случае вводится так называемый искусственный базис путем перехода к М-задаче.

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



Пусть исходная задача линейного программирования имеет вид

; (7)
; (8)
(9)

 

При этом ни одно из ограничений не имеет предпочтительной переменной. М-задача будет записываться следующим образом:

 

; (10)
(11)
(12)

 

При этом знак “–” в функции (10) относится к задаче на максимум. Задача (10)–(12) имеет предпочтительный вид. Ее начальный опорный план имеет вид

 

.

 

Если некоторые из уравнений (8) имеют предпочтительный вид, то в них не следует вводить искусственные переменные.

Теорема 5.Если в оптимальном плане хопт = М-задачи (10)–(12) все искусственные переменные , то план является оптимальным планом исходной задачи (7)–(9).

 

Теорема 6 (признак несовместности системы ограничений). Если в оптимальном плане М-задачи хотя бы одна из искусственных переменных отлична от нуля, то система ограничений исходной задачи несовместна.

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

 

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

Решение

Сведем задачу к каноническому виду. Получим

 

 

Первое ограничение имеет предпочтительную переменную х3, а второе – нет. Поэтому вводим в него искусственную переменную w1. Приходим к М-задаче

 

Занесем условие М-задачи в симплексную табл. 5. Начальный опорный план имеет вид x0 = (x1; x2; x3; x4; w1) = (0; 0; 2; 0; 12), z(x0) = 0 – 12M.

Таблица 5

БП сБ А0 x1 x2 x3 x4 w1  
M  
x3 (1)
w1 M –1  
zjcj –6 –4  
–12M –3M –4M M  
               
                   

 

Сделаем необходимые пояснения.

Индексную строку удобно разбить на две. В первой из них записываются свободные члены выражений D0 = cБ × А0 и Dj = cБ × Ajcj, а во второй – коэффициенты, содержащие M. Например, для табл. 5:

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

Переходим к новой табл. 6.

Разрешающий столбец находим по max{|–3M|; |–4M|} = 4M, разрешающая строка определяется по . Следовательно, 1 – разрешающий элемент.

Таблица 6

БП сБ А0 x1 x2 x3 x4 w1
M
x2
w1 M –5 –4 –1
zjcj
–4M 5M 4M M

 

В индексной строке нет отрицательных оценок. Следовательно, по признаку оптимальности опорный план (0; 2; 0; 0; 4) оптимален. Но так как в оптимальном плане искусственная переменная w1 не равна 0, то по теореме 6 система ограничений исходной задачи несовместна. Задача решения не имеет.

Ответ:нет решения.

 

Пример 5. Решить с использованием искусственного базиса задачу

 

 

Решение

Упорядочим запись исходной задачи. Умножим второе неравенство на –1:

 

Сведем задачу к каноническому виду. Получим

 

Первое и четвертое ограничения имеют предпочтительные переменные, а второе и третье – нет. Поэтому вводим в них искусственные переменные w1 и w2. Приходим к М-задаче

Занесем условие М-задачи в симплексную табл. 7. Начальный опорный план имеет вид x0 = (0; 0; 10; 0; 0; 4; 3; 9), z(x0) = 0 + 12M.

Таблица 7

БП сБ А0 x1 x2 x3 x4 x5 x6 w1 w2  
–1 M M  
x3  
w1 M (1) –3 –1
w2 M –1  
х6 –1  
zjcj –1  
12M 4M –2M M M  
                   

 

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

Таблица 8

БП сБ А0 x1 x2 x3 x4 x5 x6 w2  
–1 M  
x3  
x1 –3 –1  
w2 M (10) –1
x6 –2 –1  
zjcj –2 –1  
10M 3M M  
                   
                       

По мере вывода из базиса искусственных переменных соответствующие им столбцы можно опускать. Разрешающий столбец находим по max{4M} = 4M, разрешающая строка определяется по . Следовательно, 1 – разрешающий элемент.

Так как существуют положительные оценки, то план x1 = (3; 0; 7; 0; 0; 7; 0; 0) не является оптимальным.

Переходим к табл. 9. Разрешающий столбец находим по max{10M; 3M} = 10M, разрешающая строка определяется по .

Итак, 10 – разрешающий элемент.

Таблица 9

БП сБ А0 x1 x2 х3 x4 x5 x6
–1
x3
x1
x2 –1
x6
zjcj

Так как все оценки неположительны, то получен оптимальный план. Итак, x* = хопт = (3; 0; 7; 0; 0; 7), zmin = (x*) = 3.

Ответ: хопт = (3; 0; 7; 0; 0; 7), zmin = 3.

 

 

Вопросы для самоконтроля

 

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

2. Последовательность этапов практической реализации алгоритма симплекс-метода при решении задач линейного программирования.

3. Построение начального опорного плана (3 случая).

4. Случаи, когда опорный план оптимален.

5. Переход к нехудшему опорному плану.

6. Симплексные преобразования.

7. Признак бесконечности множества оптимальных планов.

8. Понятие о вырождении. Монотонность и конечность симплексного метода. Зацикливание.

9. Признак неограниченности целевой функции.

10. Необходимость использования симплекс-метода с искусственным базисом (М-метода). Суть этой модификации симплекс-метода.

11. Определение искусственной переменной. Случаи, при которых она вводится. Коэффициент, соответствующий ей в линейной функции. Проведение анализа плана по индексной строке.

12. Признак несовместности системы ограничений.

 

 






Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов (88‰)...

Поперечные профили набережных и береговой полосы: На городских территориях берегоукрепление проектируют с учетом технических и экономических требований, но особое значение придают эстетическим...

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

Индивидуальные и групповые автопоилки: для животных. Схемы и конструкции...





© cyberpedia.su 2017-2020 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав

0.02 с.