Системы линейных неравенств

Московский государственный областной университет

(МГОУ) ФИЗИКО-МАТЕМАТИЧЕСКИЙ ФАКУЛЬТЕТ Кафедра высшей алгебры, элементарной математики и методики преподавания математики КУРСОВАЯ РАБОТА Изучение темы «Системы линейных неравенств»

Москва

Содержание Введение Глава 1. Системы линейных неравенств

1.1 Линейные неравенства

1.2 Геометрический смысл системы неравенств

1.3 Системы линейных неравенств (элементарная алгебра)

1.4 Системы линейных неравенств (высшая алгебра)

1.5 Однородные системы линейных неравенств и выпуклые конусы

1.6 Следствия однородной системы неравенств

1.7 Теорема Минковского Глава 2. Симплекс-метод

2.1 Основная задача линейного программирования

2.2 Симплекс-метод для отыскания опорного решения системы линейных неравенств

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

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

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

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

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

Глава 1. Системы линейных неравенств

1.1 Линейные неравенства Перед изучением систем линейных неравенств рассмотрим понятие — линейное неравенство.

Линейное неравенство — это неравенство вида

.

Различают два типа линейных неравенств:

1) Строгие неравенства: .

2) Нестрогие неравенства: .

1.2 Геометрический смысл системы неравенств Если линейное уравнение задаёт прямую, то линейное неравенство определяет полуплоскость.

Пример 1

Решить линейные неравенства:

.

Решить линейное неравенство — это значит найти полуплоскость, точки которой удовлетворяют данному неравенству (плюс саму прямую, если неравенство нестрогое). Решить неравенство можно аналитически и графически. Приведем пример графического решения неравенств а) и б) (рис. 1). Для этого построим прямые. Если неравенство строгое прямую построим пунктиром, что будет показывать, что точки принадлежащие прямой не являются решениями неравенства, при нестрогом неравенстве точки принадлежащие прямой являются решениями неравенства. Отметим полуплоскость, точки которой являются решениями неравенств. Неравенства решены.

1.3 Системы линейных неравенств (элементарная алгебра) Рис. 1. Системы линейных неравенств (элементарная алгебра) Система линейных неравенств — это система, составленная из нескольких неравенств.

Решить систему линейных неравенств — это значит найти множество точек плоскости, которые удовлетворяют каждому неравенству системы.

Система линейных неравенств может не иметь решений, то есть, быть несовместной.

Пример 2: .

Cамый распространённый случай, когда решением системы является некоторая область плоскости. Область решений может быть не ограниченной (например, координатные четверти) либо ограниченной. Ограниченная область решений называется многоугольником решений системы.

Пример 3: Решить систему линейных неравенств Построим графики всех прямых на одной координатной плоскости (рис. 2), отметим полуплоскости. Пересечение этих полуплоскостей и будет являться решением системы, а именно многоугольник OABCD.

Рис. 2. Помимо многоугольника решений системы, встречается открытая область

1.4 Системы линейных неравенств (высшая алгебра) Рассмотрим решение систем линейных неравенств с точки зрения высшей алгебры.

Основные понятия. Система вида

(1)

Где, , называется системой линейных неравенств.

Положим Систему (1) можно записать в векторной форме:

(2)

где

Обозначим через, А матрицу, составленную из коэффициентов системы (1):

Систему (1) можно записать в матричной форме:

Пусть есть n-мерное арифметическое пространство над полем действительных чисел? и — его основное множество.

Вектор из с координатами называется решением системы (1), если

.

Система (1) называется совместной, если она имеет хотя бы одно решение. Система (1) называется несовместной, если она не имеет решений.

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

Неравенство

(4)

Называется следствием системы (1), если каждое решение системы (1) является решением неравенства (4).

Неравенство вида

(5)

где называется неотрицательной линейной комбинацией неравенств системы (2).

ПРЕДЛОЖЕНИЕ 1.1. Любая неотрицательная линейная комбинация неравенств системы (2) являются следствием этой системы.

Доказательство. Пусть неравенство (5) есть неотрицательная линейная комбинация неравенств системы (2). Пусть есть любое решение системы (2),

(6)

Умноживе неравенство (6) на для и сложив все эти неравенства, получим Таким образом, неравенство (5) является следствием системы (2).

1.5 Однородные системы линейных неравенств и выпуклые конусы Пусть ?? — арифметическое векторное пространство над полем действительных чисел? , ??=, и — векторы пространства ??.

Система Называется однородной линейной системой неравенств.

ОПРЕДЕЛЕНИЕ. Непустое множество векторов векторного пространства ??, замкнутое относительно сложения и умножения на неотрицательные скаляры (неотрицательные действительные числа), называется выпуклым конусом пространства ??.

Примеры.

1 Пусть Множество

Есть выпуклый конус пространства. Этот конус называется полупрямой, порожденной вектором

2. Множество всех неотрицательных комбинаций системы векторов пространства есть выпуклый конус этого пространства; его мы будем обозначать через

3. Пусть ??=,? — подпространства ?? и L — его основное множество. Тогда L есть выпуклый конус пространства ??.

1.6 Следствия однородной системы линейных неравенств Для доказательства теоремы Минковского необходимы следующие две леммы.

ЛЕММА 1. Если

(3)

то неравенство

(2)

не является следствием системы Доказательство. Ранг системы векторов обозначим через r. Предположим, что выполняется условие (3), тогда

Ранг (4)

Пусть

;

.

Рассмотрим систему линейных уравнений

(5)

На основании (4) заключаем, что ранги основной и расширенной матриц системы (5) равны. Следовательно, система (5) совместна. Поэтому существует вектор о такой, что Вектор о является решением системы (1), не удовлетворяющим (2). Таким образом, неравенство (2) не является следствием системы (1).

СЛЕДСТВИЕ 1. Если неравенство (2) есть следствие системы (1), то По закону контрапозиции, это утверждение равносильно лемме 1.

ЛЕММА 2. Пусть неравенство

(2)

есть следствие системы и

. (3)

Тогда неравенство (2) является следствием системы Доказательство. Рассмотрим систему

Вектор с в силу (3) есть неотрицательная линейная комбинация векторов ,

В силу предложения 1.1. отсюда следует, что (2) является следствием системы (II):

(II) (5)

Надо доказать, что любое решение о системы (4) является решением неравенства (2). Возможны два случая: или. Если, то о есть решение системы (1) и, следовательно, по условию о является решением неравенства (2). Если же, то о есть решение системы (1'); следовательно, ввиду (4) является решением и неравенства (2). Итак, любое решение системы (4) является решением неравенства (2).

1.7 Теорема Минковского В теории линейных неравенств одной из основных является следующая теорема.

ТЕОРЕМА. Пусть неравенство

(2)

Есть следствие системы Тогда .

Доказательство.(проводится индукцией по m) ю Теорема верна при m=1. Действительно, пусть По условию, неравенство есть следствие неравенства. По следствию 1., где л Так как-то Поэтому вектор есть решение неравенства и, по условию, решение неравенства (2), т. е. Следовательно, л. Теорема, очевидно, верна также при .

Предположим, что теорема верна, когда система содержит неравенств. Так как (1)(2), то по следствию 1. Среди представлений вектора b существует представление с наибольшим числом неотрицательных коэффициентов. Пусть

(3)

— одно из таких представлений. Пусть s есть число неотрицательных коэффициентов в (3), Надо доказать, что. Допустим, что Мы будем считать, что коэффициенты неотрицательны. Рассмотрим вектор Тогда Пусть M — множество всех решений системы (1) и о — любой вектор из М, тогда, если; следовательно, Кроме того, по условию, поэтому На основании (6) и (7) заключаем для любого о из М, т. е. неравенство есть следствие системы (1).

По лемме 2, отсюда вытекает, что неравенство есть следствие системы

Состоящей из неравенств. По индуктивному предположению,, т. е с можно представить в виде Ввиду (5) и (8)

В этом представлении вектора b число неотрицательных коэффициентов больше, чем s. Это противоречит предположению, что представление (3) вектора b содержит наибольшее число неотрицательных коэффициентов. Мы пришли к противоречию, допустив, что Таким образом, этот случай невозможен. Следовательно, т. е (3) есть искомое представление вектора b в виде неотрицательных комбинации векторов .

Глава 2. Симплекс-метод

2.1 Основная задача линейного программирования

1.Формулировка основной задачи. Основная задача линейного программирования формулируется так:

Дана линейная форма (целевая функция) и задана система линейных неравенств (ограничений)

(1)

которую перепишем в виде Найти максимум (минимум формы (2.1) при выполнении (2.2).

Другими словами, среди решений системы (2.2) (образующих многогранник Щ) надо отыскать такое, для которого форма (2.1) принимает наибольшее (наименьшее) значение.

2.Геометрическая интерпретация. Основную задачу линейного программирования можно легко интерпретировать геометрически. Каждое неравенство системы (2.2) определяет в евклидовом n-мерном пространстве полупространство, состоящее из точек, расположенных «по одну сторону» от плоскости и на самой этой плоскости. Точки же, принадлежащие всем полупространствам (2.2) (т.е. множество всех решений системы (2.2)) как пересечение выпуклых множеств, образуют некоторый выпуклый многогранник Щ (или многогранное множество).

Значение функции

в точке можно рассматривать как уклонение точки от плоскости понимая под уклонением данной точки от этой плоскости число, которое получим, подставляя в левую часть уравнения (*) вместо координаты этой точки. Так, например, уклонение точки x (1,-2,5) от плоскости Равно числу

Уклонение точки x от плоскости (*) пропорционально растоянию от точки x до этой плоскости.

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

3.О методе решения задачи линейного программирования. Нетрудно понять, что обычные методы классического математического анализа для отыскания наибольшего (наименьшего значения функции неприменимы к рассматриваемой задаче.

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

Линейная же форма (2.1), определенная на многограннике Щ, заданном неравенствами (2.2), достигает своего наибольшего (наименьшего) значения в некоторой вершине этого многогранника, так что множество точек, «подозрительных на экстремум», является множество всех вершин многогранника Щ, число которых обычно бывает огромным.

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

Симплекс-метод состоит из алгоритма отыскания какого-нибудь опорного среди решений системы линейных неравенств (2.2), т. е. решения-вершины многогранника Щ (или из установления факта несовместности системы), и из алгоритма последовательного перехода от полученного уже опорного решения системы (2.2) к новому опорному решению, для которого форма (2.1) имеет большее (меньшее) значение (до получения максимизирующего (минимизирующего), т. е. оптимального решения).

Основу вычислительной схемы симплекс-метода составляют модифицированные жордановы исключения.

2.2 Симплекс-метод для отыскания опорного решения системы линейных неравенств

1.Переход к таблице. Форму (2.1) и условия (2.2) записываем в виде следующей таблицы (2.3):

Если среди ограничений (2.2) встречаются ограничения лишь на знак переменной, т. е. вида, то их не включают в таблицу (2.3). При этом заменой переводят каждое ограничение вида в ограничение вида .

Переменные, на знаки которых не наложены никакие ограничения, называют свободными; переменные же, на знаки которых наложены ограничения, называют несвободными.

2.Исключение свободных переменных. Будем считать, что все переменные свободны и что ранг матрицы коэффициентов системы (2.2) равен n. Тогда с помощью n последовательных шагов модифицированных жордановых исключений можно будет перенести все из верхней строки таблицы (2.3) в ее левый столбец и на их место поставить соответствующие. При этом никаких ограничений на выбор разрешающих элементов не налагается, лишь бы они были отличны от нуля.

Для удобства записи можно считать, что на верх таблицы переброшены, так что получена, например, таблица (2.4)

Выражения для замененных понадобятся лишь после получения решения, чтобы выразить его в старых координатах. Поэтому выписываем отдельно:

и продолжаем в дальнейшем работать лишь с оставшейся частью таблицы (2.4'):

Так как по условию (2.2), то мы перешли к следующей обычной формулировке задачи линейного программирования:

Дана линейная функция и система неравенств (ограничений) Причем Из всех неотрицательных решений системы найти такое, которое максимизирует линейную функцию

Пример: Максимизировать форму при выполнении ограничений и при

Переходим к таблице

Переменные неотрицательны, поэтому мы их не исключаем.

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

не содержащую уже отрицательных свободных членов, и можем перейти к отысканию оптимального решения. Над отрицательным коэффициентом zстроки -1 находится лишь один положительный коэффициент 2. Его делаем разрешающим. После шага модифицированного жорданова исключения получим

Над отрицательным коэффициентов zстроки -5/2 нет положительных, поэтому линейная форма может принимать сколь угодно большое значение.

Для решения минимизации формы достаточно решить задачу максимизации полученной формы при ограничениях (2.2) и

min z = - max Z

Алгоритм симплекс-метода монотонный, т. е. каждый шаг монотонно приближает нас к искомому значению.

2.3 Практическое применение симплекс метода Основную задачу линейного программирования можно экономически интерпретировать следующим образом.

Пусть для производства некоторого продукта имеется n различных технологий. При этом пусть используется m ингредиентов (различные виды сырья и прочие производственные факторы), причем по j-й технологии расходуется в единицу времени единиц i-го ингридиента, общий запас которого равен, и производится единиц продукта. Пусть — время, в течении которого производство ведется по j-й технологии. Тогда при «плане» будет произведено единиц продукта и израсходовано единиц i-го ингредиента. Естественно возникает задача: отыскать оптимальное сочетание. Математическая модель этой задачи и будет основная задача линейного программирования: максимизировать линейную форму.

Список литературы

линейный неравенство симплекс решение Зуховицкий С. И. и Авдеева Л. И. Линейное и выпуклое программирование, М. Наука 1967 — 460с.

Куликов Л. Я. Алгебра и теория чисел: Учебное пособие для педагогических институтов. — М.: Высшая школа, 1979. — 559 с.

Новоселов, С. И. Специальный курс элементарной алгебры [Текст]/С.И.Новоселов. 6-е изд. — М.: Высшая школа, 1962.-564с.