КАТЕГОРИИ:

Главная
Случайная страница
Познавательное
Новые статьи
Контакты
Заказать работу

Архитектура-(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 Решение задач линейного программирования

Proof.

Курс

Вычислительная схема симплексного метода

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

Рассмотрим симплексный метод на примере следующей задачи:

;

; (3.6)

;

Решение. С помощью дополнительных неотрицательных переменных перейдем к системе уравнений вместо системы неравенств. Учитывая, что все неравенства имеют знак “”. Дополнительные переменные входят со знаком плюс. Исходная система ограничений после указанных преобразований имеет следующий вид:

; (3.7)

;

Для нахождения первоначального базисного решения разобьем переменные на две группы: основные (базисные) и не основные (небазисные). Легко видеть, что определитель при дополнительных переменных имеет следующий вид: и, следовательно, отличен от нуля. Исходя из этого переменные можно взять в качестве основных переменных на первом шаге решения задачи. При выборе основных переменных на первом шаге не обязательно составлять определитель и проверять равно ли нулю его значение. Можно воспользоваться следующим правилом.

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

Шаг 1. Основные переменные . Неосновные переменные . Выразим основные переменные через неосновные переменные:

;

; (3.8)

;

Положим неосновные переменные равными нулю, т.е. , получим базисное решение , которое является допустимым. Учитывая, что целевая функция, выраженная через неосновные переменные, имеет вид

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

В данном примере, учитывая, что в целевой функции коэффициенты при и положительны, в основные переменные можно переводить и и . Для определенности в основные переменные переведем ту переменную, коэффициент которой в целевой функции больше. В данном случае такой переменной является .

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

;

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

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

Очевидно, что сохранение неотрицательности возможно, если не нарушена ни одна из границ. Следовательно, в рассматриваемом случае

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

Шаг 2. Основные переменные . Неосновные переменные .

На этом шаге из уравнения (3.8) выразим новые основные переменные, начиная с разрешающего уравнения (оно используется при выражении записи для )

;

Преобразуя систему, получим:

;

; (3.9)

;

Второе базисное решение является допустимым.

Выразим значение целевой функции, получим:

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

; .

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

Второе уравнение является разрешающим, переменная переходит в неосновные при этом .

Шаг 3. Основные переменные . Неосновные переменные .

Повторяя процедуру шага 2, выражаем новые основные переменные через неосновные, начиная с разрешающего уравнения. Проведя необходимые преобразования, получим

;

; (3.10)

;

Базисное решение соответствует вершине, у которой ; . Выражаем линейную функцию через неосновные переменные:

;

Проверяем .

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

Третье уравнение является разрешающим и переменная переходит в неосновные .

Шаг 4. Основные переменные . Неосновные переменные .

После преобразований получим

;

; (3.11)

Базисное решение .

Целевая функция, выраженная через основные переменные, имеет вид

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

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

При решении задачи определения минимума целевой функции можно использовать один из следующих путей:

- если необходимо отыскать минимум , то решается задача максимизации функции , и это решение принимается за решение исходной задачи;

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

Рассмотрим симплексный метод решения следующей задачи на минимум.

; (3.12)

;

, .

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

Получим систему уравнений

;

Шаг 1. Выберем в качестве основных переменных переменные . Неосновные переменные .

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

;

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

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

Для нее наибольшее возможное значение определяется из соотношения . То есть первое уравнение становится разрешающим.

Следовательно, становится неосновной переменной, .

Шаг 2. Основные переменные . Неосновные переменные .