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

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

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

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

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

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

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

НАБИЕВА А.Б

АЛМАТЫ 2007 Г

СОДЕРЖАНИЕ

1. Общая задача линейного программирования
2. Элементы линейной алгебры и геометрии выпуклых множеств
3. Свойства задачи линейного программирования
4. Теоретические основы методов линейного программирования
5. Геометрические методы решения задач линейного программирования
6. Применение метода Жордана – Гаусса к решению системных линейных
уравнений
7. Библиографический список

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

α 11x1 + α12x2 + ...+ α1n xn ≤ b1,
α 21x1 + α22x2 + ...+ α2n xn ≤ b2,
... ... ... ... ... ... ... ... ... ... ... ...
α k1x1 + αk2x2 + ...+ αkn xn ≤ bk,
α k +l,l + αk+1,2x2 + ...+ αk+1,n xn = bk+1
α k+2,1x1 + αk+2,2x2 + ...+ αk+2,n xn = bk+2
... ... ... ... ... ... ... ... ... ... ... ...
α m1x1 + αm2x2 + ...+ αmn xn = bm
и линейная функция
F = c1 x1 + c2 x2 + ...+ cn xn

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

F = Σcjxj → max (или → min)
при ограничениях:

Σ αijxj ≤ bi(i = 1,2,...,k),
Σ αijxj ≤ bi(i =k + 1, k + 2,...,m),
Xj ≥0 (j = 1,2,...,l;l ≤ n).
Оптимальным решением задачи линейного программирования называется решения
Х=(x1, x2,...,хj,..., xn) система ограничений удовлетворяющее условию, при
котором линейная функция принимает оптимальное значение. Термины решение
и план – синонимы, однако первый используется чаще, когда речь идет о
формальной стороне задачи (ее математическом решении), а второй – о
содержательной стороне (экономические интерпретации). При условии, что все
переменные неотрицательны (Xj ≥0, j = 1,2,...,n), система ограничений состоит
лишь из одних неравенств ,- такая задача линейного программирования
называется стандартной, если система ограничений из одних уравнений, та
задача называется канонической. Так, в приведенном выше примерах задач
линейного программирования задачи 1 и 2 – стандартные, задача 4 –
каноническая, а задача, а задача 3 – общая.
Любая задача линейного программирования может быть сведена к
канонической, стандартной или общей задаче.
Ранг матрицы. Эквивалентные матрицы. Дана прямоугольная матрица.

α11 α12 ... α1n

A = α21 α22... α2n

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

С · С миноров которого порядка.
Рассмотрим всевозможные миноры матрицы А, отличные от нуля. Рангом матрицы
А называется наибольший порядок минора этой матрицы принимают равным нулю.
Всякий отличный от нуля минор матрицы, порядок которого равен рангу этой
матрицы называется базисным минором матрицы. Ранг матрицы А будем
обозначать через r(A). r(A) = r(B) , матрицы А и В называется
эквивалентными. В этом случае записывают А ~ В. ранг матрицы не изменяется
от элементарных приобретений. Под элементами преобразованиями понимается:
1. замена строк столбцами, α столбцов соответственно строками;
2. перестановка строк матрицы;
3. вычеркните строки, все элементы которой равны нулю;
4. умножение какой – либо строки на число не равно нулю;
5. прибавление к матрицам одной строки соответствующих элементов другой
строки.

ПРИМЕР 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. Сколько миноров второго порядка имеет матрица

α11 α12 α13

А = α21 α22 α23

α31 α32 α33

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

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

α11 x1 + α12 x2 +...+ α1nxn = b1
α21 x1 + α22 x2 +...+ α2nxn = b2
... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..
α m1 x1 + αm2 x2 +...+ αmnxn = bm

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

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

Матрица

α11 α12 ... α1n

А = α21 α22 ... α2n

... ... ... ... ... ..
α31 α32 ...α3n
называется матрицей системы. Матрица

α11 α12 ... α1n b1

А = α21 α22 ... α2n b2

... ... ... ... ... ... ..
αm1 αm2 ...αmn bm
называется расширенной матрицей этой системы.
Для совместной системы необходимо и достаточно, чтобы ранг матрицы
система равнялся рангу расширенной матрицы этой системы.
r(A) = r(A1) = r
Если b = b2 = ... bn = 0, то система линейного уравнения называется
однородной. Однородная система уровней всегда совместна. Если ранг
совместной системы равен числу неизвестных (т.е. r = n), то система будет
определенной. Если же ранг совместимой системы меньших числа неизвестных,
то система неопределенная.

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

F = CX → max (min)

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

АX = В,
X ≥ 0

где

α11 α12... α1n
x1 b1
α11 α11 ... α11
x2 b2
С = (с1,с2,...,сn); A = ... ... ... ... ; X = ... B = ...
α11 α11 ... α11
xn bm

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

F = CX → max (min)
при ограничениях
p1x1 + p2x2 + ...+ pnxn = p
x ≥ 0
где CX – скалярное произведение векторов С = (с1,с2,...,сn) и
X = (x1,x2,...,xn), векторы

α11 α11 α1n
b1
P1 = α11 , P2 = α11 , P1= α2n , P1= b1
... ... ... ...
α11 α11 αmn
b1
состоят соответственно из коэффициентов при переменных и свободных
членов. Векторное неравенство x ≥ 0 означает, что все компоненты вектора
неотрицательны, т.е. x j≥ 0, j = 1,2,...,n.
Множества всех допустимых решений систем ограничений задачи линейного
программирования является выпуклым. Пусть
Х1=(x1, x2,..., xn) и Х2=(x1, x2,..., xn) – два допустимых решения задачи,
заданной в матричной форме. Тогда АХ1 = В и АХ2=В

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

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

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

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

Заменим в выражении каждое значение этим максимальным значением М. тогда,
учитывая, что αj ≥0, Σ αj = 1,
F(x*) ≤ α1M + α2M + ...+ αpM = M Σ αj =M. Под предположению оптимальное
решение, поэтому, с одной стороны, F(x*)≥ F(xк) = М,
то с другой стороны, доказано, что F(x*)≤ М, следовательно,
F(x*) = М = F(xк), где xк – угловая точка. Итак, существует угловая точка
xк , линейная функция принимает максимальное значение более чем в одной
угловой точке, например, в точках
X1, X2,...,Xq 1≤ q ≤p ; F(X1,) = F(X2) = ...= F(Xq) = M.

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

F(X) = F(α,X1 + α2X2 + ...+ αqXq) = α1F(X1) + α2F(X2) + ...+ αq F(Xq) = = α1M +
α2M + ...+ αqM = MΣαj = M,
т.е. линейная функция. F принимает максимальное значение в произвольной
точке Х, является выпуклой линейной комбинацией угловых точек Х1,Х2,...,Хq.
Каждому допустимому базисному решению задачи линейного программирования
соответствует угловая точке многогранника решений соответствует допустимое
базисное решение.

Пусть Х1=(x1, x2,..., xm ;0,0,...,0) – допустимое базисное решение
системных ограничений задачи, в котором первые m компонент – основные
переменные, а остальные n – m компонент – не основанные переменные, равные
нулю в базисном решении (если это не так, то соответствующие переменные
можно перенумеровать). Покажем, что Х – угловая точка многогранника
решений. Предположим противное, т.е. что Х не является угловой точкой.
Точку Х можно представить внутренней точкой отрезка, соединяющего две
различные не совпадающие с Х, точки
Х1=(x1, x2,..., xm ;0,0,...,0) и
Х2=(x1, x2,..., xm ;0,0,...,0)
другими словами, - выпуклой линейной комбинацией точек x1 и x2
многогранника решений, т.е
X = α1 X1 + α2 X2
где α1≥0, α2≥0, α1 + α2 = 1 (полагаем, что α1 = 0, α2 = 0, ибо в противном
случае точка Х совпадает с точкой X1 или X2)
Запишим векторное равенство в координатной форме:

Х1 = α1 X1 + α2 X2,
... ... ... ... ... ... ..
Х1 = α1 Xm + α2 Xm,
0 = α1 Xm+1 + α2 Xm+1,
... ... ... ... ... ... ...
0 = α1 Xn + α2 Xn
Поскольку xj≥0, xj≥0 (j = 1,2,...,n), x10, x20, то из последних n – m
равенств следует, что Xm+1 = 0,..., Xn = 0, Xn = 0, т.е. в решениях x1, x2 и
... продолжение

Вы можете абсолютно на бесплатной основе полностью просмотреть эту работу через наше приложение.