Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Решение задач ЛП.docx
Скачиваний:
44
Добавлен:
22.03.2016
Размер:
282.38 Кб
Скачать

1.2. 0Бщая и основная задачи линейного программирования

 

Общая задача. Найти максимальнoe значение линейной целевой функции

Z=C1X1+C2X2+…CnXn  (1.1)

при линейных ограничениях

где сj, аij, bi - действительные числа, хj- переменные.

Определение 1.1. Совокупность чисел х=(x1,x2,...,Xn), удовлетворяющих ограничениям (1.2), называется допустимым решением или планом.

Определение 1.2. План х*=(x*1, x*2,...,x*n), при котором целевая функция (1.1) принимает свое максимальное значение, называется оптимальным.

Каноническая форма. Задачу линейного программирования будем считать приведенной к каноническому виду, если

1) требуется найти максимум целевой функции;

2) система ограничений (1.2) содержит только равенства;

3) правые части системы ограничений неотрицательны.

 

Переход от общей формы к канонической:

1) если в задаче требуется найти минимум целевой функции, то вводим новую целевую функцию z1 =-z, тогда max z1 =-min z;

2) чтобы перейти от неравенства к равенству в системе ограничений, необходимо прибавить (вычесть) дополнительную неотрицательную переменную к левой части неравенства;

3) если в правой части системы ограничений имеются отрицательные числа, то необходимо умножить на "-1" обе части равенства, в котором в правой части стоит отрицательное число.

Задачу линейного программирования в канонической форме называют основной задачей.

 

 

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

 

1.3. Свойства задач линейного программирования

 

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

Z=C1X1+C2X2+…+CNXN  max

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

Перепишем ограничения этой задачи в векторной форме:

x1P1+x2P2+…+xnPn=P0          (1.3

где Р1,..., Рn и Р0 - k-мерные вектор-столбцы, составленные из коэффициентов при неизвестных и свободных членов системы ограничений основной задачи:

Определение 1.3. План х=(x1,x2,...,Xn) называется опорным планом основной задачи линейного программирования, если его положительные коэффициенты (хj>0) стоят при линейно независимых векторах Рj.

Так как векторы Рj являются k-мерными, то из определения опорного плана следует, что число его положительных компонент не может быть больше числа k.

Определение 1.4. Опорный план называется невырожденным, если он содержит ровно k положительных компонент, в противном случае он называется вырожденным.

Свойства задач линейного программирования тесным образом связаны со свойствами выпуклых множеств.

Определение 1.5. Пусть х(1),...х(m)- произвольные точки евклидова пространства Rn. Выпуклой линейной комбинацией этих точек называется сумма: a1х(1)+...+ аmх(m), где аi (альфа) - произвольные неотрицательные числа, сумма которых равна 1.

Определение 1.6. Множество называется выпуклым, если вместе с любыми двумя своими точками оно содержит и отрезок прямой, соединяющий эти точки.

Определение 1.7. Точка X выпуклого множества называется угловой, если она не может быть представлена в виде выпуклой линейной комбинации каких-нибудь двух других различных точек данного множества.

Сформулируем первое свойство задач ЛП.

Теорема 1.1. Множество планов любой задачи линейного программирования является выпуклым (если оно не пусто).

Определение 1.8. Непустое множество планов задачи линейного программирования называется многогранником решений, а всякая угловая точка многогранника решений -вершиной.

Сформулируем второе свойство задач ЛП.

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

Теорема 1.3. Если система векторов Р1,... Рm (m <= n) линейно независима и такова, что

1Р+...+ mP= Р0

где все j>=0, то точка х=(1,2,...,m,0,...,0) является вершиной многогранника решений.

Теорема 1.4. Если =(12,..., n)- вершина многогранника решений, то векторы Рj , соответствующие положительнымj >= 0, линейно независимы.