Определение оптимального решения задачи линейного программирования — КиберПедия 

История создания датчика движения: Первый прибор для обнаружения движения был изобретен немецким физиком Генрихом Герцем...

Археология об основании Рима: Новые раскопки проясняют и такой острый дискуссионный вопрос, как дата самого возникновения Рима...

Определение оптимального решения задачи линейного программирования

2017-10-01 2892
Определение оптимального решения задачи линейного программирования 5.00 из 5.00 3 оценки
Заказать работу

После получения опорного решения задачи линейного программи­рования переходим к определению оптимального решения. Оптималь­ным решением (планом) задачи линейного программирования называ­ется такое решение, при котором целевая линейная функция принимает экстремальные (максимальное или минимальное) значения.

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

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

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

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

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

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

Пример 4.3

Для реализации трех видов товаров предприятие располагает тремя видами ресурсов b1 = 180, b2 = 50 и b3 = 40. Для продажи первой группы товаров на одну тысячу рублей товарооборота расходуется ресурсов пер­вого вида в количестве а11 = 3 единицы, ресурсов второго вида а21 = 2 еди­ницы и третьего а31 = 2 единицы. Для продажи второй и третьей групп товаров на 1 тысячу рублей товарооборота расходуется соответственно:

a2l = 6 единиц, al3 = 4 единицы, а22 = 1 единицу, a23 = 2 единицы, а32 =3 еди­ницы, а33 = 1 единицу.

Прибыль, полученная от продажи трех групп товаров на единицу то­варооборота, составляет: с1 = 6, с2 = 5 и с3 = 5.

Определить максимальную прибыль предприятия.

Математическая модель задачи имеет вид:

(4.20)

 

при ограничениях-неравенствах:

(4.21)

 

и условиях:

(4.22)

 

Решение

1. Вводим зависимые переменные yi ≥ 0 удовлетворяющие условиям:

и перепишем ограничения (4.16) и целевую функцию Z (4.20) в виде:

(4.23)

 

(4.24)

2. Составляем симплексную табл. №1, включая в нее независимые пере­менные -x1 -x2,,-х3, на верху таблицы, зависимые переменные y1,y2,у3 и целевую функцию Z, записывая в левом столбце таблицы с соот­ветствующими знаками у коэффициентов - aik. Ограничения на знак в таблицу не включаем.

Первоначальный план (исходное решение) является опорным, так как при х1 = х2 = х3 = 0 (все переменные, расположенные на верху таблицы, равны нулю) и зависимые переменные у1 = 180, у2 = 50, уъ = 40 удов­летворяют условиям уi 0.

3. Определяем оптимальное (максимальное) решение задачи линейного программирования. Находим разрешающий элемент ars. В качестве разрешающего выбираем столбец, содержащий наиболь­ший отрицательный по абсолютной величине коэффициент Z-строки, равный «-6». В табл. № 1 указано вертикальной стрелкой. Разрешающую строку определяем из условия min

Такой строкой будет третья (указана горизонтальной стрелкой). Сле­довательно ars = а31 = 2.

Выполним шаг модифицированного жорданова исключения с раз­решающим элементом а31 = 2, отмечено квадратиком. Получим табл. №2 в виде:

Разрешающий элемент а31 = 2, заменяем обратной величиной, рав­ной 1/2. Все остальные элементы разрешающего столбца делим на «-2», получаем

Остальные элементы разрешающей строки делим на 2 и получаем:

Все элементы табл. №2 получаем, вычисляя по правилу «прямо­угольника».

Вычисления элементов таблицы запишем по строкам:


 

Решение, представленное табл. № 2, не является оптимальным, так как в Z-строке имеется отрицательный коэффициент, равный -2. Выпол­ним шаг модифицированного жорданова исключения с разрешающим элементом а23 = 1 (третий столбец — разрешающий, а строка определена из условия min

и получим табл. № 3 в виде:

Вычисления для заполнения табл. № 3 выполняем, начиная с разре­шающих строки и столбца, а затем определяем элементы столбца сво­бодных членов и Z-строки. Так как свободные члены и коэффициенты Z-строки неотрицательны, то решение является оптимальным. Осталь­ные элементы симплекс-таблицы можно не вычислять.

Решение задачи выписываем из табл. № 3:

у3 = х2 = у2 = 0, так как все переменные, расположенные на верху табли­цы равны нулю. Тогда переменные, находящиеся в левом столбце таблицы равны соответствующим значениям свободных членов (элементы в столбце под «1»), то есть

 

Проверка.

Ответ:

Пример 4.4

Для заданной целевой линейной функции

(4.25)

Найти максимальное значение при линейных ограничениях-неравен­ствах:

(4.26)

и условиях:

(4.27)

Решение

1. Введем зависимые переменные, удовлетворяющие условиям уi > 0, и перепишем систему ограничений (4.26) и целевую функцию (4.25) в виде:

(4.28)

(4.29)

2. Составляем симплексную табл. № 1, включая в нее зависимые yj не­зависимые переменные к (4.28) и целевую функцию Z (4.29). Огра­ничения на знак переменных хк в таблицу не включаем. Номера таб­лиц будем указывать в левом верхнем углу:

Исходный (первоначальный) план является неопорным, так как в третьей строке уз = -5 (свободный член, т.е. элемент табл. № 1 в столб­це под 1 величина отрицательная).

Полученное решение представлено табл. № 2:

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

Решение задачи, представленное табл. № 2, показывает, что план яв­ляется опорным, но неоптимальным, так как в Z-строке все коэффи­циенты отрицательные.

4. Определяем оптимальное решение, выполняя шаг модифицирован­ного жорданова исключения с разрешающим элементом а21 = 1. В ка­честве разрешающего столбца берем наибольший по модулю отрица­тельный коэффициент — 16, т.е. столбец под переменной х1 (отмечен­ный вертикальной стрелкой), а разрешающей будет строка с единст­венным положительным коэффициентом равным 1. Следовательно, a21 = 1, а решение будет представлено табл. № 3:

Решение задачи, представленное табл. № 3, является оптимальным, так как все коэффициенты Z-строки — положительные величины. Выписываем решения задачи из табл. № 3:

 
 

Проверка зависимых переменных и целевой функции:

Пример 4.5

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

(4.30)

удовлетворяющие линейным ограничениям-неравенствам:

(4.31)

и условиям:

(4.32)

 

 

Решение

1. Введем зависимые переменные yt > 0 и ограничения (4.31) перепишем в виде:

 
 

2. Составляем симплексную табл. № 1, включая в нее зависимые, неза­висимые переменные и целевую функцию (4.30):

 
 

Исключаем из табл. № 1 свободную независимую переменную xv вы­бирая в качестве разрешающего элемента любой коэффициент в этом столбце (под переменной хх ), так как согласно правилу выбора разрешаю­щего элемента при исключении свободной переменной ограничений на выбор его нет.

Разрешающий элемент отмечен квадратиком, а соответствующие раз­решающие строка и столбец указаны стрелками. Выполним шаг модифи­цированного жорданова исключения с разрешающим элементом а31 = 1 и получаем табл. № 2:

 
 

 

В табл. № 2 вписываем значение для х1 и вычеркиваем третью строку

 
 

(4.33)

 

 
 

Перепишем табл. № 3 в виде:

 

Решение задачи, представленное табл. № 3, указывает, что получен­ный план является опорным, так как все элементы столбца, расположен­ные под 1, — неотрицательны, но неоптимальны.

Определяем оптимальное решение задачи, выполняя шаг модифици­рованного жорданова исключения с разрешающим элементом а22 = 2. Разрешающим является столбец с коэффициентом -5 в Z-строке, а раз­решающую строку определяем из условия

 
 

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

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

Так как в отношении коэффициент, стоящий в знаменателе, отри­цательный, то в качестве разрешающей строки принимаем третью строку с коэффициента равным 7. Выполним шаг модифицированного жордано­ва исключения с а31 = 7 и табл. № 5 будет иметь вид (вычисляем элементы разрешающего столбца, разрешающей строки, столбца свободных членов и Z-строки. Остальные элементы табл. № 5 можно не вычислять).

План, представленный табл. № 5, является оптимальным. Выписыва­ем решения задачи:

Вычисляем значение свободной переменной х1 на основании (4.33):

Вычисляем значения зависимых переменных у{ и целевой функции, подставляя найденные значения в (4.30) и (4.31).

Пример 4.6

Для заданной целевой функции найти максимальное значение:

при линейных ограничениях-неравенствах

(4.34)

и условиях:

(4.35)

(4.36)

 

 

Решение

1. Вводим зависимые переменные и перепишем условие задачи (4.34)-(4.36) в виде:

(4.37)

(4.38)

2. Составляем симплексную табл. № 1:

 


3. Исключаем свободную независимую переменную х3, выполняя шаг модифицированного жорданова исключения с разрешающим элемен­том а43 = 1. Получаем табл. № 2:

Выписываем значение переменной х3:

(4.39)

и вычеркиваем четвертую строку в табл. № 2.

Получаем табл. № 3 в виде:

 
 

Так как в табл. № 3 в столбце свободных членов два отрицательных элемента -5 и -10, то план неопорный. В качестве разрешающего прини­маем 1 столбец, так как в третьей строке находится элемент с наиболь­шим отрицательным по модулю значением -10 и коэффициент -8 распо­ложен в этом столбце, а разрешающую строку определяем из условия:

Следовательно, выполним шаг модифицированного жорданова ис­ключения с разрешающим элементом а11 = -8, получим табл. № 4:

Решение, представленное табл. № 4, не является опорным, так как в столбце свободных членов имеется отрицательный элемент, равный -5. Выполнив шаг модифицированного жорданова исключения с разрешаю­щим элементом а31 = -1, получим табл. № 5:

Решение, полученное в виде табл. № 5, является опорным, но не оп­тимальным, поскольку в Z-строке коэффициент равный – 15/8 в первом столбце отрицательный, но в этом столбце нет положительных коэффи­циентов. Следовательно, целевая функция ограничений на максимум не имеет.


 

 


Поделиться с друзьями:

Таксономические единицы (категории) растений: Каждая система классификации состоит из определённых соподчиненных друг другу...

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

Семя – орган полового размножения и расселения растений: наружи у семян имеется плотный покров – кожура...

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



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

0.073 с.