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

В приложении кратко изложены некоторые понятия и вопросы из математики и линейного программирования. Более подробный обзор по рассматриваемым вопросам математики можно найти у Апостола; Флеминга; Финкбейнера; Халмоша; Хедли (1961); по линейному программированию — у Чарнса и Купера (1961); Данцига (1963); Гейла; Гасса; Хедли (1962); Рейли и Гасса; Симмонарда; и Фаркаша.

П.1. Математические понятия

Векторы-столбцы. Все векторы, используемые в книге, являются векторами-столбцами. Так, если где означает -мерное евклидово пространство, то

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

Обозначение означает, что а является элементом точно также указывает на то, что а не является элементом

Расстояние и пределы. Рассмотрим точки из Евклидово расстояние между определяется как

Говорят, что данная последовательность точек сходится к пределу и обозначают это в виде или

если справедливо следующее. Для заданного существует такое Р, что для всех

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

Перечислим некоторые свойства пределов. Пусть причем все точки принадлежат Тогда

Если все точки принадлежат то

Функция. Обозначение указывает на то, что функция переводит точки в точки из . Значения функции являются векторами: Другими словами, функция — векторная функция.

Непрерывность. Функция непрерывна в точке если из условия следует соотношение

Другое эквивалентное определение заключается в следующем: для данного существует такое при котором из вытекает, что

Здесь

Функция является непрерывной, если она непрерывна во всех точках, в которых она определена.

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

также непрерывна.

Частные производные. Пусть дана функция Если имеет первые частные производные, то она имеет градиент

Если имеет вторые частные производные, она обладает квад» ратной матрицей Гесса порядка

Пример. Если то Разложение в ряд Тейлора. Если функция имеет непрерывные первые частные производные, то она допускает разложение в ряд Тейлора первого порядка в точке

где Точка представляет собой некоторую точку на отрезке прямой между

Если имеет непрерывные частные производные второго порядка, то она допускает разложение в ряд Тейлора второго порядка

где

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

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

Цепное правило (правило дифференцирования сложной функции). Пусть имеют непрерывные первые частные производные. Тогда составная функция где имеет частные производные первого порядка

где означает первую частную производную функции в точке по аргументу

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

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

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

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

является замкнутым множеством. Если само X замкнуто, то

Пример. замкнуто; замкнуто.

Множество не является замкнутым. Его замыкание представляет собой

Гиперплоскость и полупространство. Гиперплоскость в представляет собой множество вида где Гиперплоскость определяет два (замкнутых) полупространства

П.2. Линейное программирование

Задача программирования вида

где А представляет собой матрицу размера является задачей ЛП.

Теорема двойственности линейного программирования. Двойственная задача заключается в нахождении

Здесь и не ограничена по знаку.

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

Другие две двойственные задачи составляют задачи

и

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

Лемма Фаркаша. Лемма Фаркаша представляет собой следующую теорему:

Теорема. Утверждение о том, что

для всех х, для которых эквивалентно утверждению, что существует такое что

Доказательство. Рассмотрим задачу

Двойственной является задача

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

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

Симплексный метод. Кратко опишем симплексный метод для решения задачи

Задача ЛП имеет вид

где размерность А равна

Симплексный метод оперирует определенными матрицами Т, которые называются симплексными таблицами. Каждая таблица Т обладает свойством

где С — базисная квадратная матрица порядка составленная из линейно независимых столбцов матрицы А. Так, если то, полагая, что означает столбец А, получаем

где означают номера столбцов А. Столбцы А, составляющие С, образуют базис и называются базисными. Обратите внимание на то, что столбец Т представляет собой столбец из нулей, за исключением одной единицы в позиции.

Полагая вадим, что любое решение системы является решением системы и наоборот.

Базисным допустимым решением или опорным планом является точка х, для которой где, кроме того, а все другие (небазисные) компоненты являются нулями. Компоненты соответствуют столбцам А, входящим в базис, и называются базисными компонентами. Обратите внимание на то, что для всех

Ясно, что любой заданной таблице Т соответствует некоторый опорный план.

Алгоритм симплексного метода. Чтобы описать алгоритм симплексного метода, положим

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

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

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

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

Преобразовывая таблицу таким образом, мы получаем таблицу, соответствующую новой базисной матрице. Новая базисная матрица отличается от старой лишь тем, что теперь столбец матрицы С занят столбцом

Направляющий элемент, элемент столбца определяется по формуле

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