Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Вопрос 1
Постановка и решение задач линейного программирования. Симплекс-метод решения.
Ответ.
Пусть - система линейных ограничений задана в виде линейных уравнений или линейных неравенств с n переменными ,
- линейная целевая функция вида
.
Требуется найти значения
при ограничениях и условии неотрицательности
, которое следует из реального смысла значений переменных .
Задачи линейного программирования в зависимости от вида ограничений подразделяются на два вида:
Стандартную задачу можно привести к каноническому виду путем введения для каждого из неравенств системы ограничений новой дополнительной переменной и замены этих неравенство двумя ограничениями:
линейным уравнением
и условием .
Полученная таким образом задача в каноническом виде эквивалентна исходной задаче линейного программирования заданной в стандартной форме.
Эквивалентность решений задач линейного программирования заданных в стандартной и в канонической форме следует из того что, если к значениям переменных решения задачи в стандартной форме добавить значения введенных дополнительных переменных, то получим решение этой же задачи заданной в канонической форме.
Пусть задача линейного программирования сформулирована как задача нахождения экстремума линейной функции на допустимом множестве , заданном системой линейных неравенств в пространстве , называемой выпуклой многогранной областью в .
Геометрический решение задачи линейного программирования состоит в отыскании максимума (минимума) заданной линейной функции на заданном выпуклом множестве .
Целевая функция в задаче линейного программирования ограничена, если в задаче на максимум на допустимом множестве она ограничена сверху, а в задаче на минимум – снизу.
Допустимое множество в задаче линейного программирования задается системой линейных ограничений в и поэтому является выпуклой многогранной областью, или выпуклым многогранником.
Теорема 1. Выпуклый многогранник совпадает с выпуклой оболочкой своих угловых точек.
Примечание: Системы линейных ограничений, возникающие в задачах экономического характера, почти всегда содержат условия неотрицательности для всех переменных, поэтому допустимое множество не содержит целиком ни одной прямой и допустимое множество(если только оно непусто) имеет хотя бы одну угловую точку.
Теорема 2. Если в задаче линейного программирования допустимое множество непусто и ограничено, то задача разрешима, а множество всех оптимальных решений является выпуклой оболочкой оптимальных угловых точек .
Примечание, Функция может быть ограничена снизу на допустимом множестве в то время как само допустимое множество не ограничено.
Симплекс-метод предназначен для решения канонической задачи линейного программирования.
Рассмотрим задачу линейного программирования с ограничениями в форме уравнений. Дана система
(1.1)
m линейных уравнений с n неизвестными и линейная функция
. (1.2)
Среди неотрицательных решений системы (1.1) нужно найти такое, которое минимизирует функцию (1.2).
Для решения задачи симплекс-методом требуется определить допустимое решение в котором некоторые из неизвестных должны быть выражены через остальные и свободные члены этих выражений должны быть неотрицательными.
Если система (1.1) совместна, то метод Гаусса позволяет выделить в ней базис неизвестных, при этом вопрос допустимости остается открытым.
Если допустимый базис неизвестных определен, то в выражении для целевой функции следует заменить каждое базисное неизвестное его выражением через свободные.
Пусть задача линейного программирования содержит пять неизвестных и система ограничений приведена к допустимому виду с базисом :
(1.3)
целевая функция имеет вид
. (1.4)
и решается задача минимизации при ограничениях (1.3) и условиях .
Положим все свободные неизвестные равными нулю:
,
Из системы (1.3) значения базисных неизвестных:
.
Получено неотрицательное решение системы : (1.5).
(1.5) - допустимое базисное решение, соответствующее базису
при котором значение функции равно .
Возможны три ситуации.
Тогда для любого неотрицательного решения системы (1.3) имеем , значит, . Таким образом, , т.е. базисное решение является оптимальным – задача решена.
Пусть, например, , а .В базисном решении (1.3), будем увеличивать значение (при ). Значения базисных неизвестных также будут меняться:
(1.5)
Решение остается неотрицательным. При этом , и ввиду значение с ростом будет неограниченно уменьшаться. Таким образом, в этом случае , т.е. задача конечного оптимума не имеет.
В этом случае производится шаг, а именно, на котором переходим к новому базису, так чтобы уменьшилось или по крайней мере не увеличилось: .
Пусть, например, и отрицательны, а - положительно или равно 0:
.
Если увеличивать значение , то:
При и значения и будут уменьшаться, а значение будет оставаться неотрицательным (). При возрастании наступит момент, когда одно из неизвестных или обратится в нуль: для таким моментом будет , а для будет . Выберем из этих отношений и наименьшее. Пусть, например, это будет . Тогда увеличение возможно только от до .
. Полагая в системе и , получим неотрицательное решение
,
для которого значение функции будет (поскольку и ).
Таким образом, с ростом первым из базисных неизвестных обращается в нуль неизвестное . Это произойдет при замене базиса на .
с базисным решением
,
которое является неотрицательным.
Новое значение функции равно
и ( и поэтому ). При переходе к новому базису система ограничений сохранила допустимую форму , где , а значение функции для базисного решения уменьшилось или осталось прежним.
Выражение для заменяется новым:
,
Если для полученной задачи имеет место случай 3, то выполняется следующий шаг перехода к новому базису для которого .
до тех пор, пока не придем к одному из случаев 1 или 2.
Задачи.