Солодовников А.С., Бабайцев В.А., Браилов А.В. Математика в экономике - файл n1.doc

приобрести
Солодовников А.С., Бабайцев В.А., Браилов А.В. Математика в экономике
скачать (3829.5 kb.)
Доступные файлы (1):
n1.doc3830kb.10.09.2012 14:34скачать

n1.doc

1   ...   24   25   26   27   28   29   30   31   32

§ 9.4. Доказательство основной теоремы двойственности. Метод одновременного решения пары двойственных задач



Рассмотрим снова взаимно двойственные задачи I и I'. Между их решениями существует, как мы знаем, связь, выражаемая равенством mах f = min ?.

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

Для сокращения записей снова будем считать, что задача I имеет размеры 2 х 3, а задача I' размеры 3 х 2. Произведем ряд уточнений.

1. Представим обе задачи как задачи на нахождение минимума, для чего перейдем в задаче I от функции f к функции F = -f. Наконец (смысл этого станет ясен позднее), введем в выражения для f и ? некоторый свободный член d. Тогда в выражении для F появится свободный член -d.

Итак, имеем две задачи:

2. Преобразуем эти задачи в канонические, введя дополнительные (балансовые) переменные х4, х5 для задачи I и у3, у4, у5 для задачи I'. В итоге системы ограничений примут вид:

Если в системе (9.29) числа b1 и b2 неотрицательны, то переменные x4 и x5 образуют в этой системе допустимый базис. Аналогично если –c1 ? 0, -c2 ? 0, -c3 ? 0, то переменные у3, у4, у5 образуют допустимый базис в (9.29'). Чтобы не связывать себя условием неотрицательности свободных членов, расширим на некоторое время понятие допустимого базиса, сняв условие неотрицательности свободных членов. Тогда можно считать, что переменные х4, х5 независимо от того, какие знаки имеют числа b1, b2, 1, 2, 3 являются базисными для задачи I, а переменные у3, у4, у5 базисными для задачи I'.

3. Между переменными обеих задач можно установить естественное соответствие. Рассмотрим, например, переменную х4, являющуюся базисной в (9.29). В выражении х4 = b1a11x1а12х2 – а13х3 коэффициенты при свободных переменных, т. е. числа –a11, -a12, -a13, лишь знаками отличаются от коэффициентов а11, а12, а13, при y1 в (9.29'). В соответствии с этим будем считать, что переменной x4 соответствует у1. Аналогичным образом, если взять, например, переменную у3, являющуюся базисной в (9.29'), то можно видеть, что в ее выражении через свободные переменные коэффициенты при последних лишь знаками отличаются от коэффициентов при x1 в (9.29). Поэтому считаем, что переменной у3 соответствует x1. В итоге устанавливаем следующее соответствие:

при котором базисным переменным одной задачи отвечают свободные переменные другой задачи.

Будем считать соответствие взаимным и писать:

Установленное соответствие между переменными позволяет следующим образом охарактеризовать связь между задачами I и I:

1. Пусть xi — базисная, а хj. — свободная переменная в задаче I; им отвечают (соответственно) переменные уk и уe в задаче I':

Тогда коэффициент, с которым хj входит в выражение для xi, лишь знаком отличается от коэффициента, с которым уk входит в выражение для уe:

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

3. Свободный член в выражении для F через свободные переменные лишь знаком отличается от свободного члена в выражении для ?.

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

Указанная выше связь (см. 1, 2, 3) между записями задач I и I' сохраняется при согласованных заменах базисов в этих задачах.
Поясним сказанное. Пусть в задаче I производится, например, следующая замена базиса:

т. е. переменная x1 из свободных переводится в базисные, а переменная x4, наоборот, из базисных переводится в свободные. Разумеется, для осуществления такой замены необходимо, чтобы было а14 ? 0. В этом случае возможна и замена

Выделенное курсивом предложение означает, что после осуществления таких согласованных замен связь между записями задач I и I', указанная в положениях 1, 2, 3, сохраняется.

Предоставляем читателю убедиться в справедливости этого предложения, выполнив соответствующие преобразования над записями задач I и I'.

Предположим, что в одной из систем (9.29), (9.29') свободные члены в правых частях неотрицательны (именно так и обстояло дело в производственной задаче из § 9.1, где было b1 > 0 и b2 > 0). Пусть, например, b1 ? 0, b2 ? 0. Тогда к задаче I можно непосредственно применить симплекс-метод. Исходная симплекс-таблица будет иметь вид

Заметим, что соответствующая таблица для задачи I' может быть составлена исходя из таблицы I автоматически на основании соответствия (9.30) и правил 1, 2, 3. Она запишется как таблица I'.

Однако следует иметь в виду, что таблица I' не обязательно является симплекс-таблицей в полном смысле, поскольку числа –c1, -c2, -c3 не обязательно больше или равны 0.

Итак, будем решать симплекс-методом задачу I. После ряда шагов придем к оптимальному решению. В заключительной симплекс-таблице все числа столбца свободных членов (кроме, может быть, последнего числа) и все числа строки F (кроме, быть может, первого числа) неотрицательны. Но тогда на основании правил 1, 2, 3 можем заключить, что в соответствующей таблице для задачи I' также не будет отрицательных чисел — ни в столбце свободных членов, ни в строке для ? (за указанными исключениями). Это означает, что в задаче I' также достигнуто оптимальное решение. При этом, поскольку числа, стоящие на пересечении столбца свободных членов и строки для целевой функции, в обеих таблицах отличаются лишь знаком, приходим к заключению, что min F = -min ? или, что то же самое, mах f = min ?, что и доказывает основную теорему двойственности.

Попутно мы получили следующий метод одновременного решения пары взаимно двойственных задач I и I'. Приводим обе задачи к каноническому виду и устанавливаем соответствие между переменными обеих задач. Далее решаем с помощью симплекс-метода ту из двух задач, где свободные члены в выражениях для базисных неизвестных неотрицательны (предполагается, что одна из задач таким свойством обладает). Из последней симплекс-таблицы выделяем строку для целевой функции. Если числа, стоящие в ней, начиная со второго, взять с противоположными знаками, а затем воспользоваться соответствием между переменными обеих задач, то получим оптимальное решение двойственной задачи. Первое же число в указанной строке дает искомый оптимум целевой функции.
Пример. Пусть в результате решения задачи I получена следующая симплекс-таблица Т:

Предположим также, что соответствие между переменными обеих задач имеет вид (9.30). На основании этих данных запишем решение задачи I'.

Для этого нам достаточно знать лишь фрагмент таблицы Т:

Учитывая соответствие (9.30), получаем, что оптимальное решение задачи I' будет

причем


§ 9.5. Несимметричные двойственные задачи



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

От соответствующих задач I и I' § 9.1 (матричная форма записи задач) они отличаются тем, что:

а) все ограничения в задаче L имеют вид уравнений, в то время как в задаче I это неравенства;

б) в задаче L' отсутствует условие неотрицательности неизвестных; таким образом, неизвестные в этой задаче могут быть любого знака.

Для упрощения записей будем считать, как и в § 9.1, что задача L имеет размеры 2 х 3. Итак:

Ясно, что любое линейное уравнение а1х1 + а2x2 + a3x3 = b может быть заменено эквивалентной ему системой из двух неравенств a1x1 + а2х2 + a3x3 ? b и a1x1 + а2х2 + а3x3 ? b, т. е. системой вида

Проделав такую замену с каждым из уравнений (9.31), запишем задачу L в следующем виде:

Двойственная задача в смысле § 9.1 будет иметь размеры 3 х 4. Обозначим неизвестные в этой задаче u1, v1, u2, v2. Итак:

или, что то же самое:

Если существует решение задачи I, то в силу теоремы двойственности существует и решение задачи I', причем mах f = min Ф.

Сравнивая задачи L' и I, замечаем, что они, в сущности, эквивалентны. В самом деле, если у1, у2 какое-либо решение задачи L', то, взяв любые четыре неотрицательных числа u1, v1, u2, v2, удовлетворяющих условиям

(что, очевидно, возможно), получим решение задачи I'. Наоборот, если u1, v1, u2, v2 есть решение задачи I', то числа у1, у2, найденные по формулам (9.34), дают решение задачи L'. Таким образом мы приходим к следующей теореме, которая является, по существу, одним из вариантов теоремы двойственности.
Теорема. Если задача L имеет решение, то задача L' также имеет решение; при этом max f = min ?.
В заключение укажем общую постановку взаимно двойственных задач, когда система ограничений включает как уравнения, так и неравенства.

Здесь предполагается, что:

1. В системе (9.35) некоторые ограничения являются неравенствами (типа ?), а некоторые — уравнениями. Вектор Y1 является частью вектора Y; неизвестное уi входит в Y1 тогда и только тогда, когда i-е ограничение в системе (9.35) является неравенством.

2. Система (9.35') также состоит из неравенств (типа ?) и уравнений. Вектор Х1 является частью X; неизвестное хj входит в Х1 тогда и только тогда, когда j-e ограничение в системе (9.35') является неравенством.

Теорема двойственности (общая) утверждает, что если разрешима задача I, то разрешима и задача I, причем max f = min ?.
Пример. Если в качестве исходной задачи взять

то двойственная задача будет


Литература



1. Ашманов С.Л. Введение в математическую экономику.— М.: Наука,1984.

2. Гейл Д.. Теория линейных экономических моделей.— М. : Иностранная литература, 1963.

3. Гольштейн Е.Г., Юдин Д.Б. Линейное программирование (теория, методы и приложения).— М.: Наука, 1969.

4. Леонтьев В.В. Экономические эссе.— М.: Политиздат, 1990.
Содержание


Введение 3

Глава 1. Арифметические векторы и системы линейных уравнений 3

§ 1.1. Арифметические векторы и действия над ними. Пространство Rn 3

§ 1.2. Скалярное произведение векторов 5

§ 1.3. Линейно зависимые и линейно независимые системы векторов 7

§ 1.4. Система линейных уравнений и ее решение методом Гаусса 11

§ 1.5. Применения метода Гаусса 16

§ 1.6. Ортогональные векторы 18

§ 1.7. Базис пространства Rn 19

Глава 2. Матрицы и определители 21

§ 2.1. Операции над матрицами 21

§ 2.2. Матричная запись системы линейных уравнений 25

§ 2.3. Умножение квадратных матриц. Вырожденные и невырожденные матрицы. Обратная матрица 26

§ 2.4. Способ нахождения обратной матрицы 27

§ 2.5. Решение системы n х n с помощью обратной матрицы 31

§ 2.6. Понятие определителя порядка n. Основная теорема об определителях 32

§ 2.7. Свойства определителей 35

§ 2.8. Практический способ вычисления определителей 38

§ 2.9. Применения определителей 39

Глава 3. Линейные экономические модели 43

§ 3.1. Модель Леонтьева многоотраслевой экономики 43

§ 3.2. Продуктивные модели Леонтьева 45

§ 3.3. Вектор полных затрат 49

§ 3.4. Модель равновесных цен 50

§ 3.5. Модель международной торговли. Собственные векторы и собственные значения матриц 51

§ 3.6. Собственные векторы неотрицательных матриц 56

§ 3.7. Собственные значения матрицы Леонтьева 60

Глава 4. Элементы аналитической геометрии 62

§ 4.1. Арифметическое точечное пространство Аn 62

§ 4.2. Прямая в Аn. Отрезок 64

§ 4.3. Различные виды плоскостей в пространстве Аn 65

§ 4.4. Специальные формы уравнения плоскости в А3 67

Глава 5. Метод наименьших квадратов и его приложения 68

§ 5.1. Метод наименьших квадратов 68

§ 5.2. Применение метода наименьших квадратов 71

§ 5.3. Случай линейной зависимости между переменными 76

Глава 6. Выпуклые множества 79

§ 6.1. Выпуклые множества в пространстве Аn. Полупространство как выпуклое множество 79

§ 6.2. Угловые точки выпуклых многогранных областей 81

§ 6.3. Выпуклая оболочка системы точек 83

Глава 7. Введение в линейное программирование 86

§ 7.1. Общая задача оптимизации. Линейное программирование. Примеры задач 86

§ 7.2. Геометрия задачи линейного программирования 92

§ 7.3. Строение множества оптимальных решений 96

§ 7.4. Графический метод решения задачи линейного программирования при малом числе переменных 98

Глава 8. Решение общей задачи линейного программирования 103

§ 8.1. Симплекс-метод 103

§ 8.2. Симплекс-таблицы 108

§ 8.3. Работа с целевой функцией 111

§ 8.4. М-метод 114

§ 8.5. Теорема о конечности симплекс-алгоритма 119

Глава 9. Теория двойственности 123

§ 9.1. Взаимно двойственные задачи линейного программирования 123

§ 9.2. Основная теорема двойственности и ее следствия 128

§ 9.3. Применение двойственности в однопродуктовой задаче 131

§ 9.4. Доказательство основной теоремы двойственности. Метод одновременного решения пары двойственных задач 138

§ 9.5. Несимметричные двойственные задачи 141

Литература 144


Учебник
Солодовников Александр Самуилович

Бабайцев Владимир Алексеевич

Браилов Андрей Владимирович
МАТЕМАТИКА В ЭКОНОМИКЕ

В двух частях

Часть 1
Заведующая редакцией Л.А. Табакова

Редактор Е.В. Стадниченко

Художественный редактор Ю.И. Артюхов

Технический редактор И.В. Белюсенко

Корректор Т.М. Колпакова

Обложка художника Н.М. Биксентеева

Компьютерная верстка В.А. Львова
ИБ№3761

Лицензия ЛР № 010156 от 29.01.97
Подписано в печать 22.01.2001. Формат 60х88/16

Гарнитура «Таймс». Печать офсетная

Усл. печ. л. 13,72. Уч.-изд. л. 10,48.

Тираж 7000 экз. Заказ 447. «С»030
Издательство "Финансы и статистика"

101000, Москва, ул. Покровка, 7

Телефон (095) 925-35-02, факс (095) 925-09-57
E-mail: mail@finstat.ru http://www.finstat.ru
Великолукская городская типография

Комитета по средствам массовой информации и связям

с общественностью администрации Псковской области,

182100, г. Великие Луки, ул. Полиграфистов, 78/12

Тел./факс: (811-53) 3-62-95

E-mail: VTL@MART.RU




1   ...   24   25   26   27   28   29   30   31   32


§ 9.4. Доказательство основной теоремы двойственности. Метод одновременного решения пары двойственных задач
Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации