Министерство общего и профессионального образования

Российской Федерации

Южно-Уральский Государственный Университет

Кафедра АиУ.

Реферат

по математическим основам теории систем

ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

Выполнил: Подрезов Сергей Валерьевич

Группа: ПС-243

Преподаватель: Разнополов Олег Александрович

Челябинск, 2005

Содержание.

Линейное программирование. 3

Симплекс-метод. 6

Двойственная задача. 13

Список используемой литературы. 14

Линейное программирование.

Постановка задачи

Термин и линейное программирование связывается со следующей задачей. Дана система линейно независимых уравнений с неизвестными х1,….,х2 – система ограничений задач и линейного программирования:

, (1)

где bi?0. Требуется найти неотрицательное значение переменных (хi?0), которые удовлетворяют управлениям (1) и обращают в минимум целевую функцию q = c1x1+…+cnxn (2), называемой линейной формой.

Матричная запись:

(3)

Если m<n, то система (1) имеет бесчисленное множество решений. Любое решение системы (1), где xi?0 будем называть допустимым решением. Среди допустимых решений нужно выбрать такое, которое обращает в минимум целевую функцию.

В ограничения (1) могут входить не равенства aj1x1+..+ajnxn?bj или aj1x1+..+ajnxn?bj введя дополнительную переменную xn+j так, чтобы имело место: aj1x1+..+ajnxn+xn+j=bj или aj1x1+..+ajnxn-xn+j=bj что не меняет существа задачи. Задача максимизации сводится к рассмотренной путем замены знака целевой функции .

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

Геометрическая интерпретация

g=x2-x1 (4)

при ограничениях

. (5)

Удобнее решить задачу максимизации q/ = -q= x1-x2. (6)

Имеется m=3 базисных переменных и n-m=2 свободных. Выразим базисные переменные через свободные .

Область допустимых значений: xi?0, . Построим прямые x3, x4, x5 на плоскости x1, x2:

Для каждой прямой xi переменных xi=0. В точках пересечения 2-х прямых в нуль обращаются две переменные, что соответствует базисному решению. Вершины многоугольника допустимых решений соответствуют допустимым базисным решениям. Выражение (6) определяет прямую, причём увеличение q/ соответствует перемещению прямой в направлении стрелки. Эта прямая должна проходить через область допустимых решений. Максимум q/ получим в крайнем