Главная | Обратная связь | Поможем написать вашу работу!
МегаЛекции

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

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

Условием оптимальности при отыскании максимального значения целевой функции симплексным методом является отсутствие отрица­тельных коэффициентов в 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»), то есть

 

Проверка.

Ответ:

 

Поделиться:





Воспользуйтесь поиском по сайту:



©2015 - 2024 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...