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

 (3)

одно из таких представлений. Пусть s есть число неотрицательных коэффициентов в (3),  Надо доказать, что . Допустим, что

Мы будем считать, что коэффициенты  неотрицательны. Рассмотрим вектор

Тогда

Пусть M - множество всех решений системы (1) и ξ - любой вектор из М, тогда , если ; следовательно,

Кроме того, по условию,  поэтому

На основании (6) и (7) заключаем  для любого ξ из М, т.е. неравенство  есть следствие системы (1).

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

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

Ввиду (5) и (8)

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

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

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

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

Дана линейная форма (целевая функция)

и задана система  линейных неравенств (ограничений)

 (1)

которую перепишем в виде

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

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

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

системы (2.2) определяет в евклидовом n-мерном пространстве полупространство, состоящее из точек , расположенных «по одну сторону» от плоскости

и на самой этой плоскости. Точки же, принадлежащие всем полупространствам (2.2) (т.е. множество всех решений системы (2.2)) как пересечение выпуклых множеств, образуют некоторый выпуклый многогранник Ω (или многогранное множество).

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

в точке  можно рассматривать как уклонение точки  от плоскости

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

Равно числу

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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