КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Симплекс-метод для решения задач линейного программирования. 1 страница
С увеличением числа неизвестных геометрический метод решения ЗЛП становится затруднительным при трех переменных и невозможным при большем числе переменных. Поэтому был разработан универсальный метод решения ЗЛП – симплекс-метод, позволяющий решать ЗЛП в канонической форме. Изложим суть симплекс-метода на примере задач с 5 неизвестными. Пусть ЗЛП приведена к виду
(20)
при ограничениях:
, (21)
где ,
(22)
Про систему ограничений (21) говорят, что она имеет допустимый вид, если одни неизвестные () выражаются через остальные (), причем свободные члены этих выражений неотрицательны (). Неизвестные и называются базисными, а неизвестные – свободными. Возможны два принципиальных случая: 1Å Все коэффициенты при свободных неизвестных в выражении для F неположительны: и . Тогда для всякого неотрицательного решения системы уравнений (21) имеем и , а потому
или .
Следовательно, базисное решение является оптимальными, т. е. задача решена. 2Å Имеется свободное неизвестное, коэффициент при котором в выражении для F положителен, а все коэффициенты при этом неизвестном в уравнениях (21) – неотрицательны. Для определенности положим . Исходя из базисного решения, станем наращивать значение , не меняя . Тогда значения базисных неизвестных будут оставаться неотрицательными:
,
а значение будет неограниченно возрастать, т.е. и задача решения не имеет. Решения ЗЛП редуцируются к одному из случаев 1Å или 2Å путем перехода к новому базису, в котором целевая функция не уменьшит своего значения для базисного решения, а новая система ограничений должна иметь допустимый вид. Преобразование базиса и перестройку целевой функции и системы ограничений называют шагом в решении ЗЛП. Таким образом, сделав нужное число шагов, решают ЗЛП (20) – (22). Применим симплекс-метод к первой задаче. I. Основная задача в примере 1 имеет вид
Сначала приведем ее к каноническому виду, вводя балансовые неизвестные , и :
(23)
(24)
Теперь приведем (23) к допустимому виду – неизвестные , и выразим через и , при этом свободные члены в правых частях полученных уравнений неотрицательны:
(25)
Здесь , и – базисные неизвестные, а и – свободные неизвестные. Шаг 1: положим в (25) и , тогда , , . Получим неотрицательное решение системы уравнений (25). Его называют базисным решением. Для него . Шаг 2: положим в (25) , а начнем наращивать так, чтобы , и оставались неотрицательными, т. е. . Решая эти неравенства, найдем наименьшее значение . Тогда . Объявив и свободными неизвестными, приведем (25) к допустимому виду:
(26)
Получим неотрицательное решение системы уравнений (26). Для него
(27)
примет значение . Сделаем выводы. Во-первых, значение F по сравнению с 1-ым шагом увеличилось. Во-вторых, в (27) коэффициент при отрицательный и для дальнейшего увеличения значения F надо положить и наращивать . Шаг 3: положим в (26) , а начнем наращивать так, чтобы , и оставались неотрицательными, т. е. . Откуда находим наименьшее значение . Тогда . Объявив и свободными неизвестными, приведем (27) к допустимому виду:
(28)
Получили неотрицательное решение системы уравнений (28). Для него
(29)
примет значение . Сделаем выводы. Во-первых, значение F по сравнению со 2-ым шагом увеличилось. Во-вторых, в (29) оба коэффициента при свободных неизвестных отрицательны и дальнейшее увеличение значения F невозможно:
при . Задача решена. Учитывая экономический смысл неизвестных, приходим к выводу: предприятие получит наибольшую прибыль 1104 единиц при изготовлении 36 единиц товара и 6 единиц товара , при этом остатки ресурсов и равны нулю (), а остаток ресурса равен 12 единицам. Если решается ЗЛП, в которой требуется найти минимум целевой функции, то задачу либо сводят к рассмотренной выше задаче с целевой функцией , либо с помощью шагов приводят к одному из двух принципиальных случаев: 1Å Все коэффициенты при свободных неизвестных в выражении для F неотрицательны: и . Тогда базисное решение является решением задачи. 2Å Имеется свободное неизвестное, коэффициент при котором в выражении для F (20) отрицателен, а все коэффициенты при этом неизвестном в уравнениях (21) – неотрицательны. Тогда задача решения не имеет. Применим симплекс-метод ко второй задаче, Основная задача в примере 2 имеет вид
Сначала приведем ее к каноническому виду, вводя балансовые неизвестные , и :
(30)
(31)
Приведем ограничения (30) к допустимому виду. Как показано выше, в качестве базисных неизвестных следует выбирать такие неизвестные, каждая из которых входит только в одно из уравнений системы ограничений (31), при этом нет таких уравнений системы, в которые не входит ни одна из этих неизвестных, и каждая базисная неизвестная имеет тот же знак, что и свободный член. Нетрудно видеть, что , и не могут быть базисными неизвестными. Действительно,
(32)
и знаки , и противоположны знакам свободных членов. Для выделения базисных неизвестных из системы ограничений (30) необходима ее перестройка. Полагая в (32) (или ) найдем из условий неотрицательности , и :
.
наибольшее значение . Тогда и систему (32) запишем в виде
(33)
Получили систему ограничений, имеющую допустимый вид: , и – базисные неизвестные, и – свободные неизвестные. Перейдем к процедуре шагов. Шаг 1: положим в (33) и , тогда получим базисное решение , для которого целевая функция
(34)
примет значение . В (5.15) коэффициент при положительный и для дальнейшего уменьшения значения f надо положить и наращивать . Шаг 2: положим в (33) , а начнем наращивать так, чтобы , и оставались неотрицательными, т. е.
.
Откуда находим . Тогда . Объявив и свободными неизвестными, приведем (33) к допустимому виду:
(35)
Из (35) получим базисное решение . Для него
(36)
примет значение . В (36) коэффициенты при свободных неизвестных положительны и дальнейшее уменьшение значения f невозможно: при . Задача решена. Учитывая экономический смысл неизвестных, приходим к выводу. Ежесуточная диета, обеспечивающая необходимое количество питательных веществ, состоит из единиц продукта , единиц продукта и ее минимальная стоимость единиц. При этом потребности организма в питательных веществах A и B отвечают требуемым минимальным объемам единиц и единиц соответственно (т.к. и ), а потребности в питательном веществе С больше требуемого минимального объема единиц на единиц. В заключение рассмотрим вопрос: всегда ли после конечного числа шагов симплекс-метод закончится либо нахождением оптимального решения, либо установлением того факта, что задача не имеет решения. Ответ утвердительный и содержится в следующей теореме. Теорема. Если существует оптимальное решение ЗЛП, то существует и базисное оптимальное решение. Последнее всегда может быть получено с помощью симплекс-метода.
Симплекс-таблицы для решения ЗЛП. Метод искусственного базиса (М-метод).
Описанный процесс решения ЗЛП симплекс-методом довольно трудоемкий и требует выполнения однообразных преобразований. Причем с возрастанием числа неизвестных растет и число шагов. Оказывается, эти преобразования можно записать в виде последовательности однотипно заполненных таблиц, называемых симплекс-таблицами. Изложим способ составления и преобразования таких таблиц на примерах первой и второй основных задач. I. Первая основная задача. Для заполнения первой симплекс-таблицы необходимо переписать целевую функцию F и систему ограничений в виде:
Заполним таблицу
В выражении для F выясняем, имеются ли в последней строке таблицы, кроме столбца «свободные члены», отрицательные числа. Если таковых нет, то задача решена. Если же есть, то выполняем преобразование: в столбце имеем (из двух отрицательных чисел –25 и –34 выбирают меньшее по модулю), над этим элементом ищем положительные числа. Если таковых нет, то задача не имеет решения. В нашем случае над –25 есть три положительных числа: 1; 1 и 1. Найдем
Элемент, стоящий на пересечении строки () и столбца (), называем разрешающим. В нашем случае он равен 1. (Если разрешающий элемент равен числу , то всю строку делят на разрешающий элемент m, чтобы получить 1). Неизвестная вводится в базис, а неизвестная выводится из него. Заполняем вторую симплекс-таблицу. Строка () из первой таблицы становится в ней строкой (). Далее преобразуем строки (), () и (F) первой таблицы так, чтобы их элементы, стоящие в столбце (), обратились в 0. С этой целью 1) вычтем элементы строки () из соответствующих элементов строки (), и запишем полученные результаты в строку () второй таблицы; 2) вычтем элементы строки () из соответствующих элементов строки (), и запишем полученные результаты в строку () второй таблицы; 3) умножим элементы строки () на 25, сложим с соответствующими элементами строки (F), и запишем полученные результаты в строку (F) второй таблицы. В результате получим следующую симплекс-таблицу
В строке (F) есть отрицательное число –9. Поэтому продолжим поиск оптимального решения. Над –9 есть три положительных числа: 1; 1 и 3. Найдем
Элемент, стоящий на пересечении строки () и столбца () разрешающий и равен 1. Неизвестная вводится в базис, а неизвестная выводится из него. Заполняем третью симплекс-таблицу. Строка () из второй таблицы становится в ней строкой (). Далее преобразуем строки (), () и (F) второй таблицы так, чтобы их элементы, стоящие в столбце (), обратились в 0. С этой целью 1) вычтем элементы строки () из соответствующих элементов строки (), и запишем полученные результаты в строку () третьей таблицы; 2) умножим элементы строки () на 3, вычтем из соответствующих элементов строки (), и запишем полученные результаты в строку () третьей таблицы; 3) умножим элементы строки () на 9, сложим с соответствующими элементами строки (F), и запишем полученные результаты в строку (F) третьей таблицы. В результате получим следующую симплекс-таблицу
Дата добавления: 2014-12-25; Просмотров: 512; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |