Курсовая работа (т): Системы линейных неравенств

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

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

(МГОУ)

ФИЗИКО-МАТЕМАТИЧЕСКИЙ ФАКУЛЬТЕТ

Кафедра высшей алгебры, элементарной математики и методики преподавания математики

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

Изучение темы «Системы линейных неравенств»

Москва

Содержание

Введение

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

.1 Линейные неравенства

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

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

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

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

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

.7 Теорема Минковского

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

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

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

.3 Практическое применение симплекс-метода

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

Введение

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

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

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

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

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

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

.1 Линейные неравенства

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

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

.

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

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

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

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

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

Пример 1

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

.

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

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

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

Система линейных неравенств - это система, составленная из нескольких неравенств.

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

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

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

Пример 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).

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

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

Система

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

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

Примеры.

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

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

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

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

.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 существует представление с наибольшим числом неотрицательных коэффициентов. Пусть