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

УО «БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ ЭКОНОМИЧЕСКИЙ  УНИВЕРСИТЕТ» 
 
 

Кафедра прикладной математики и экономической кибернетики 
 
 
 
 
 
 
 
 

КУРСОВАЯ  РАБОТА 
 

по дисциплине: Линейная алгебра и аналитическая геометрия

на  тему: Методы построения решений системы линейных неравенств 
 
 
 
 
 
 
 
 
 
 
 

Студент

ФМ, 1-й курс, ДКК-1          

Руководитель

д-р экон. наук,

доцент           
 
 
 
 

МИНСК 2011 
РЕФЕРАТ

Курсовая  работа: 25 с., 4 табл., 6 источников. 

     Структура множества решений  системы линейных неравенств, системы линейных неравенств в оптимизационных задачах 

     Объект  исследования — системы линейных неравенств.

     Предмет исследования — методы построения решений систем линейных решений.

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

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

________________

 

Содержание

 

Введение

     Отдельные свойства систем линейных неравенств рассматривались еще в первой половине 19 века в связи с некоторыми задачами аналитической механики. Систематическое  же изучение систем линейных неравенств началось в самом конце 19 века, однако о теории линейных неравенств стало возможным говорить лишь в конце 20-x годов 20 века, когда уже накопилось достаточное количество связанных с ними результатов.

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

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

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

     Для написания этой работы были использованы различные источники, среди которых следует отметить «Математику в экономике» Солодовникова А.С., Бабайнева В.А, Браилова А.В., где рассмотрены вопросы линейной алгебры, а также статью «Оптимизация выпуска изделий и использования производственных ресурсов на промышленном предприятии» Читая Г.О., в которой раскрыты прикладные аспекты метода линейного программирования, позволяющего определить оптимальный план выпуска изделий предприятия и оценить эффективность использованных производственных ресурсов с помощью их двойственных оценок.

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

 

     1 Однородные и неоднородные системы линейных неравенств

     1.1 Совместимость и методы получения одного набора решений однородной системы линейных неравенств

     Пусть дана система неравенств вида

     

с вещественными  коэффициентами. Если в системе будут неравенства разного типа, то умножением на –1 (где необходимо) все неравенства можно привести к одному типу (≥ 0). В матричном виде данная система имеет вид АХ ≥ 0. Жестким называется неравенство этой системы в случае, если оно выполняется как равенство для всех решений системы.

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

     Выпуклый  многогранный конус (конус) К — это пересечение конечного числа полупространств. Например, в трехмерном пространстве конусами являются двугранный угол (х₁ ≥ 0, х₂ ≥ 0), неотрицательный квадрант (х₁ ≥ 0, х₂ ≥ 0, х₃ ≥ 0), плоскость (х₁ ≥ 0, –х₁ ≥ 0), четырехгранный конус (х₁ ≥ 0, х₂ ≥ 0, х₃ ≥ 0, х₁ + х – х₃ ≥ 0), плоский угол (х₁ ≥ 0, х₂ ≥ 0, х₃ ≥ 0, х₁ + х – х₃ ≥ 0,               –х₁ – х + х₃ ≥ 0); конусами также являются одномерное подпространство, луч, нулевой вектор.

     Если векторы х₁ и х₂ принадлежат выпуклому многогранному конусу К, то векторы х₁ + х₂ и сх₁ для любого с ≥ 0 также принадлежат конусу К (следует из непосредственной подстановки координат векторов в задающую конус систему неравенств). [5, с. 118]

     Справедливы следующие утверждения.

     1. Если r — ранг матрицы, составленной из коэффициентов жестких неравенств, то конус К, определяемый всей системой неравенств, лежит в        (n–r)-мерном подпространстве и определяется в нем системой, которая не содержит жестких неравенств.

     2. Если система однородных линейных неравенств не содержит жестких неравенств, то соответствующая система строгих неравенств

     

совместна. Действительно, поскольку все неравенства (нестрогие) исходной системы однородных линейных неравенств нежесткие, то для любого  i-го неравенства системы найдется такое решение Х_i, которому бы соответствовало соответствующее строгое неравенство. При подстановке в i-ое неравенство столбца

     X₁ + ... + X_m

получаем  обязательно строгое неравенство, поскольку слагаемое с Х_i строго больше нуля, а остальные слагаемые неотрицательны. Значит, X₁ +...+ X_m — это решение системы строгих неравенств.

     Если  в исходной системе однородных (нестрогих) неравенств нет жестких неравенств, то векторы, удовлетворяющие системе строгих неравенств, называются  внутренними векторами конуса. Внутренность конуса — это множество всех внутренних векторов. Относительной внутренностью конуса называется множество решений системы строгих неравенств. Каждый внутренний вектор конуса принадлежит ему вместе с некоторой своей окрестностью относительно произвольной нормы.

     Размерность конуса К равна размерности вещественного линейного пространства L_n, если система линейных неравенств, соответствующая конусу, не содержит жестких неравенств. Действительно, если вектор Х₀(х₀₁, …, х_0n) — внутренний вектор конуса К, то для любого положительного ε возьмем η такое, что |η| < ε (причем η не является характеристическим числом матрицы, все строки которой совпадают со строкой  х₀₁, …, х_0n), и тогда векторы с координатами

     

будут линейно независимыми и будут  принадлежать конусу К.

     Если  исходная система однородных нестрогих неравенств содержит жесткие неравенства, то размерность конуса К, соответствующего этой исходной системе, равна (n—r), где r — ранг матрицы, составленной из коэффициентов жестких неравенств.

     Если  в исходной системе некоторые  жесткие неравенства заменить на равенства, то для новой системы будет свой конус, размерностью меньше. Такие конусы являются гранями конуса К. Минимальная грань будет соответствовать системе линейных уравнений

     

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

     Теорема. Каждый замкнутый выпуклый многогранный конус является суммой конечного числа лучей, или, что то же, совокупностью линейных комбинаций конечного числа векторов с неотрицательными коэффициентами. Иная формулировка теоремы: Общее решение системы однородных линейных неравенств может быть записано в виде Х = α₁Х₁ +…+ α_NX_N, где X₁, ..., X_N — некоторый набор решений, а коэффициенты α₁, ..., α_N — неотрицательны. Данный набор решений называется полной системой решений. [5, с. 121]

     1.2 Совместимость и методы получения одного набора решений неоднородной системы линейных неравенств

     Пусть дана система неравенств вида

     

с вещественными  коэффициентами. Это есть неоднородная система линейных неравенств. Считаем, что все неравенства данной системы одного типа. Если в системе будут неравенства разного типа, то умножением на –1 (где необходимо) все неравенства можно привести к одному типу (≥ 0). В матричном виде данная система имеет вид  АХ ≥ В. Геометрически решение такой системы — точка в аффинном (точечном) пространстве, множество решений — плоскость, решение приведенной однородной системы — векторы.

     Множество решений неоднородной системы неравенств выпукло (т. е. в этом множестве для каждых двух точек содержится и соединяющий их отрезок). Выпуклыми комбинациями X называются такие линейные комбинации решений исходной системы неравенств

     X = α₁X₁ +...+ α_nX_n,

для коэффициентов  которых выполняются следующие  условия:

     α₁ ≥ 0, ..., α_n ≥ 0, α₁ + ... + α_n = 1. [5, с. 121]

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

     Выпуклое  многогранное множество — это пересечение полупространств аффинного пространства; если это множество ограниченно, то оно называется  выпуклым многогранником. Именно выпуклым многогранным множеством и является множество решений неоднородной системы линейных неравенств.

     Для того чтобы определить решение линейной неоднородной системы неравенств, приведем эту систему к однородному виду. Для этого добавим еще одну переменную х_n+1 и исходную систему неравенств запишем в следующем виде:

     АX – x_n+1В ≥ 0, x_n+1 ≥ 0

(добавилось  еще одно неравенство, т.е. как бы перешли от n-мерного пространства к (n+1)-мерному пространству). Если x_n+1 = 1, то первые n элементов получившейся однородной системы неравенств будут удовлетворять исходной системе неравенств АХ ≥ В.

     Пусть Р₁, …, Р_s — фундаментальная система решений однородной системы неравенств

     АX – x_n+1В ≥ 0, x_n+1 ≥ 0.

     Считаем, что в столбцах первых t решений последние компоненты равны единице (если не равны, то к этому можно прийти элементарными преобразованиями), а в столбцах оставшихся решений последние компоненты равны нулю. Если исходная система неоднородных неравенств АХ ≥ В совместна, то t ≥ 1.

     Решения однородной системы

     АX – x_n+1В ≥ 0, x_n+1 ≥ 0

имеют вид:

     

,

где коэффициенты α_i, β_j ≥ 0 (неотрицательные), причем последняя компонента Q равна единице только при выполнении условия: α₁ +...+ α_s = 1. Тогда общее решение системы неоднородных линейных неравенств АХ ≥ В получается при отбрасывании последних элементов всех столбцов в выражении