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

Рефераты / Экономико-математическое моделирование / Решение задачи линейного программирования симплекс-методом

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

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

если переменная не ограничена в знаке, то ;

если , то .

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

После приведения ДЗ к стандартному виду используется симплекс - метод. Алгоритм получения решения тот же, что и для прямой задачи.

II. Практическая часть

1. Решение задачи линейного программирования графическим методом.

Дана следующая задача линейного программирования (ЗЛП).

1.1. Все ограничения задачи .

1.2. Переменная ограниченна в знаке, поэтому . Переменная не ограничена в знаке, поэтому вводим замену , где .

Область допустимых решений будет ограничиваться I и IV квадрантом.

1.3. Построение ограничений и градиента целевой функции :

1.4. Область допустимых решений – отрезок AB.

1.5. Точка А – оптимальная. Координаты т. А:

; ; .

2. Решение задачи линейного программирования симплекс-методом.

Прямая задача.

Задачу линейного программирования для любой вершины в компактной форме можно представить в виде:

Для получения используем алгоритм, приведённый в теоретической части.

1. Переход от неравенств к равенствам по правилам введения дополнительных переменных. Исходную задачу необходимо привести к стандартной форме: введем замену по переменной , и дополнительные переменные:

Полученный вид ЗЛП не позволяет сформировать начальный допустимый базис, т. к. нельзя выделить единичные орты во втором и третьем равенствах. Для получения начального допустимого базиса введём искусственные переменные. В результате получим:

2. Общее число переменных определим по формуле: =3+2+2=7, где - число искусственных переменных. Число базисных переменных определяется числом ограничений, т. к. , то система имеет три базисные переменные и небазисные переменные .