Задачи линейного программирования и методы их решения

Тип работы: Реферат
Бесплатно: Антиплагиат
Объем: 13 страниц
В избранное:

МИНИСТЕРСТВА ОБРАЗОВАНИЯ И НАУКИ РЕСПУБЛИКИ КАЗАХСТАН

ДЕПАРТАМЕНТ ОБРАЗОВАНИЯ ГОРОДА АЛМАТЫ

АЛМАТИНСКИЙ КОЛЛЕДЖ УПРАВЛЕНИЯ И РЫНКА

НА ТЕМУ: “ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ И МЕТОДЫ ИХ РЕШЕНИЯ”

ПРОВЕРИЛА: АЙМУХАНБЕТОВА Ш. Е

ВЫПОЛНИЛА: УЧАЩИЕСЯ III КУРСА СПЕЦИАЛЬНОСТИ ПРОГРАММНОЕ

ОБЕСПЕЧЕНИЕ ВТ И АС

НАБИЕВА А. Б

АЛМАТЫ 2007 Г

СОДЕРЖАНИЕ

1. Общая задача линейного программирования

2. Элементы линейной алгебры и геометрии выпуклых множеств

Свойства задачи линейного программирования
Теоретические основы методов линейного программирования
Геометрические методы решения задач линейного программирования
Применение метода Жордана - Гаусса к решению системных линейных уравнений
Библиографический список

Примеры задач линейного программирования позволяют сформировать общую задачу линейного программирования. Дана система m линейных уравнений и неравенств с n переменными

α ₁₁ x ₁ + α ₁₂ x ₂ + …+ α _1n x _n ≤ b ₁ ,

α ₂₁ x ₁ + α ₂₂ x ₂ + …+ α _2n x _n ≤ b ₂ ,

. .

α _k1 x ₁ + α _k2 x ₂ + …+ α _kn x _n ≤ b _k ,

α _k +l, l + α _{k+1, 2} x ₂ + …+ α _{k+1, n} x _n = b _k+1

α _{k+2, 1} x ₁ + α _{k+2, 2} x ₂ + …+ α _{k+2, n} x _n = b _k+2

α _m1 x ₁ + α _m2 x ₂ + …+ α _mn x _n = b _m

и линейная функция

F = c ₁ x ₁ + c ₂ x ₂ + …+ c _n x _n

Необходимо найти такое решение системы Х=(x ₁ , x ₂ , …, х _j , …, x _n ), где х _j ≥0 (j = 1, 2, …, l:l ≤ n), при котором линейная функция F принимает оптимальное значение. Система называется системой ограничений, а функция F - линейной функцией цели. Более кратко общую задачу линейного программирования можно представить в виде:

F = Σc _j x _j → max ( или → min)

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

Σ α _ij x _j ≤ b _i (i = 1, 2, …, k),

Σ α _ij x _j ≤ b _i (i =k + 1, k + 2, …, m),

X _j ≥0 (j = 1, 2, …, l; l ≤ n) .

Оптимальным решением задачи линейного программирования называется решения Х=(x ₁ , x ₂ , …, х _j , …, x _n ) система ограничений удовлетворяющее условию, при котором линейная функция принимает оптимальное значение. Термины «решение» и «план» - синонимы, однако первый используется чаще, когда речь идет о формальной стороне задачи (ее математическом решении), а второй - о содержательной стороне (экономические интерпретации) . При условии, что все переменные неотрицательны ( X _j ≥0, j = 1, 2, …, n), система ограничений состоит лишь из одних неравенств, - такая задача линейного программирования называется стандартной, если система ограничений из одних уравнений, та задача называется канонической. Так, в приведенном выше примерах задач линейного программирования задачи 1 и 2 - стандартные, задача 4 - каноническая, а задача, а задача 3 - общая.

Любая задача линейного программирования может быть сведена к канонической, стандартной или общей задаче.

Ранг матрицы. Эквивалентные матрицы. Дана прямоугольная матрица.

α ₁₁ α _{12 …} α _1n

A = α ₂₁ α _22… α _2n

α _n1 α _n2…. _… α _nn

выделим в этой матрице к произведенных столбцов и к произведенных строк (k ≤ m, k ≤ n) . Определитель которого порядка, составлений из элементов матрицы А, расположенных на пересечении выделенных строк и столбцов, называются минором которого порядка матрицы А . матрица А имеет

С · С миноров которого порядка.

Рассмотрим всевозможные миноры матрицы А, отличные от нуля. Рангом матрицы А называется наибольший порядок минора этой матрицы принимают равным нулю. Всякий отличный от нуля минор матрицы, порядок которого равен рангу этой матрицы называется базисным минором матрицы. Ранг матрицы А будем обозначать через r(A) . r(A) = r(B) , матрицы А и В называется эквивалентными. В этом случае записывают А ~ В. ранг матрицы не изменяется от элементарных приобретений. Под элементами преобразованиями понимается:

замена строк столбцами, αстолбцов соответственно строками;
перестановка строк матрицы;
вычеркните строки, все элементы которой равны нулю;
умножение какой - либо строки на число не равно нулю;
прибавление к матрицам одной строки соответствующих элементов другой строки.

ПРИМЕР 1

Определить ранг матрицы

2 3 4

4 6 8

6 9 12

определитель матрицы второго и третьего порядка.

4 6 1 2

М = = 0; М =

6 9 2 4

все миноры второго и третьего порядка равны нулю, следовательно, ранг матрицы r (A) = 1

ПРИМЕР 2

1 0 0 0 5

0 0 0 0 0

2 0 0 0 11

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

1 5

2 11

так как 1 5

= 0 = 1, то ранг матрицы r (A) = 2

2 11

ПРИМЕР 3. Сколько миноров второго порядка имеет матрица

α ₁₁ α ₁₂ α ₁₃

А = α ₂₁ α ₂₂ α ₂₃

α ₃₁ α ₃₂ α ₃₃

С • С = 3·3 = 9 миноров второго порядка

Исследования систем m линейных уравнений с n неизвестными. Дана система m линейной уравнений с n неизвестными.

α ₁₁ x ₁ + α ₁₂ x ₂ +…+ α _1n x _n = b ₁

α ₂₁ x ₁ + α ₂₂ x ₂ +…+ α _2n x _n = b ₂

_{. .}

α _m1 x ₁ + α _m2 x ₂ +…+ α _mn x _n = b _m

Решением этой системы называется совокупность n чисел

( x ₁ , x ₂ , …, x _n ), которое при подстановки в уравнения, обращают их в тождества. Система уравнений называется совместный, если она имеет хотя бы одно решение. Если же система не имеет ни одного решения, то она называется несовместной. Совместная система называется определенной, если она имеет больше одного решения.

Матрица

α ₁₁ α ₁₂ … α _1n

А = α ₂₁ α ₂₂ … α _2n

α ₃₁ α ₃₂ …α _3n

называется матрицей системы. Матрица

α ₁₁ α ₁₂ … α _1n b ₁

А = α ₂₁ α ₂₂ … α _2n b ₂

. .

α _m1 α _m2 …α _mn b _m

называется расширенной матрицей этой системы.

Для совместной системы необходимо и достаточно, чтобы ранг матрицы система равнялся рангу расширенной матрицы этой системы.

r(A) = r(A ₁ ) = r

Если b = b ₂ = … b _n = 0, то система линейного уравнения называется однородной. Однородная система уровней всегда совместна. Если ранг совместной системы равен числу неизвестных (т. е. r = n), то система будет определенной. Если же ранг совместимой системы меньших числа неизвестных, то система неопределенная.

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

Матричная форма записи:

F = CX → max (min)

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

АX = В,

X ≥ 0

где

α ₁₁ α _12… α _1n x ₁ b ₁

α ₁₁ α _{11 …} α ₁₁ x ₂ b ₂

С = (с ₁ , с ₂ , …, с _n ) ; A = ; X = … B = . . .

α ₁₁ α _{11 …} α ₁₁ x _n b _m

здесь С - матрица - строка, А - матрица систем, Х - матрица - столбец переменных, В - матрица - столбец свободных членов.

Векторная форма записи:

F = CX → max (min)

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

p ₁ x ₁ + p ₂ x ₂ + …+ p _n x _n = p

x ≥ 0

где CX - скалярное произведение векторов С = (с ₁ , с ₂ , …, с _n ) и

X = ( x ₁ , x ₂ , …, x _n ), векторы

α ₁₁ α ₁₁ α _1n b ₁

P ₁ = α ₁₁ , P ₂ = α ₁₁ , P ₁ = α _2n , P ₁ = b ₁

… … . . . …

α ₁₁ α ₁₁ α _mn b ₁

состоят соответственно из коэффициентов при переменных и свободных членов. Векторное неравенство x ≥ 0 означает, что все компоненты вектора неотрицательны, т. е. x _j ≥ 0, j = 1, 2, …, n.

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

Х ₁ =(x ₁ , x ₂ , …, x _n ) и Х ₂ =(x ₁ , x ₂ , …, x _n ) - два допустимых решения задачи, заданной в матричной форме. Тогда АХ ₁ = В и АХ ₂ =В

Рассмотрим выпуклую линейную комбинацию решений Х ₁ и Х ₂ , т. е. х = α ₁ х ₁ + α ₂ х ₂ при α ₁ ≥0, α ₂ ≥0 и α ₁ + α ₂ = 1 и покажем, что она также является допустимым решением системы самом деле

AX = A(α ₁ х ₁ + α ₂ х ₂ ) = α ₁ AX ₁ + (1 - α ₁ ) AX ₂ = α ₁ B + (1 - α ₁ ) B = B, т. е. решение Х удовлетворяет систему. Но так как х ₁ ≥0, х ₂ ≥0, α ₁ ≥0,

Α ₂ ≥0, то и х ≥0, т. е решение Х удовлетворяет и условно. Итак, доказано, что множество всех допустимых решений задачи линейного программирования выпуклым, а точнее, представляет выпуклый многогранник или выпуклую многогранную область, которое в дальнейшем будет называть одним термином - многогранником решений. Ответ на вопрос, в какой точке многогранника решений возможно оптимальное решение задачи линейного программирования, дается в следующей фундаментальной теореме. В этом разложении среди значений

F(x _j ) (j = 1, 2, …, p) выберем максимальную. Пусть оно соответствует угловой точке x _к (1≤ k ≤ p) ; обозначим его через M, т. е. F(x _к ) = М.

Заменим в выражении каждое значение этим максимальным значением М. тогда, учитывая, что α _j ≥0, Σ α _j = 1,

F(x*) ≤ α ₁ M + α ₂ M + …+ α _p M = M Σ α _j =M. Под предположению оптимальное решение, поэтому, с одной стороны, F(x*) ≥ F(x _к ) = М ,

то с другой стороны, доказано, что F(x*) ≤ М , следовательно,

F(x*) = М = F(x _к ), где x _к - угловая точка. Итак, существует угловая точка x _к , линейная функция принимает максимальное значение более чем в одной угловой точке, например, в точках

X ₁ , X ₂ , …, X _q 1≤ q ≤p ; F(X ₁ , ) = F(X ₂ ) = …= F(X _q ) = M.

Пусть Х - выпуклая линейная комбинация этих угловых точек, т. е

F(X) = F(α, X ₁ + α ₂ X ₂ + …+ α _q X _q ) = α ₁ F(X ₁ ) + α ₂ F(X ₂ ) + …+ α _q F(X _q ) = = α ₁ M + α ₂ M + …+ α _q M = MΣα _j = M,

т. е. линейная функция. F принимает максимальное значение в произвольной точке Х, является выпуклой линейной комбинацией угловых точек Х ₁ , Х ₂ , …, Х _q .

Каждому допустимому базисному решению задачи линейного программирования соответствует угловая точке многогранника решений соответствует допустимое базисное решение.

Пусть Х ₁ =(x ₁ , x ₂ , …, x _m ; 0, 0, …, 0) - допустимое базисное решение системных ограничений задачи, в котором первые m компонент - основные переменные, а остальные n - m компонент - не основанные переменные, равные нулю в базисном решении (если это не так, то соответствующие переменные можно перенумеровать) . Покажем, что Х - угловая точка многогранника решений. Предположим противное, т. е. что Х не является угловой точкой. Точку Х можно представить внутренней точкой отрезка, соединяющего две различные не совпадающие с Х , точки