Lektsii_po_teorii_lineynogo_programmirovania

Российскаяакадемиянаук Уфимскийнаучныйцентр Институтматематики свычислительнымцентром

М.Д. РАМАЗАНОВ

ЛЕКЦИИПО ТЕОРИИ ЛИНЕИНОГО ПРОГРАММИРОВАНИЯ

Уфа 2005

Издается при поддержке Федеральной целевой программы «Государственная поддержка интеграции высшего образования инауки», договор№401-2-04 игрантаРФФИ№02-01-01167.

УДК517.97 (07)

Научныйредактор: профессор Мухачева Э.А. Рецензент: профессор НовокшеновВ.Ю., отдел математической физики ИМВЦ УНЦ РАН

Рамазанов М.Д.

Лекции по теории линейного программирования – Уфа: ИМВЦ УНЦ РАН.

Излагаются основные положения линейного программирования как части учебного курса «Методы оптимизации», предназначенного студентам старших курсов специальностей «Математика» и «Прикладная математика». Материал книги может служить базой усовершенствования курсов методов оптимизации. Прилагается нобелевская лекция одного из основоположников линейного программированияакадемикаЛ.В. Канторовича.

©Рамазанов М.Д., 2005

©ИМВЦ УНЦ РАН, 2005

2

2.Эквивалентность различных форм постановки основной задачи..................................……. 7

3.Преобразование Лежандра......................…... 9

4.Определение двойственной задачи с помощью преобразования Лежандра......................…... 19

5.Теорема двойственности и теорема

существования решения.........………………… 24

6.Критерии крайней точки невырожденной канонической задачи.....………………………… 26

7.Алгоритм симплекс-метода решения задачи линейного программирования....................... 31

8.Обоснование алгоритма симплекс-метода...….. 36

9.Нахождение крайней точки........................... 43

3

Предисловиередактора

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

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

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

Безусловным украшением книги является текст нобелевской лекции академика Л.В. Канторовича.

Профессор Э.А. Мухачева

4

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

Задача линейного программирования – это нахождение минимума линейной функции f : Rn → R1, заданной на некотором замкнутом выпуклом множестве, выделенном линейными неравенствами.

называется общей задачей линейного программирования

– будем обозначать ее Зо.

Определение 1. Функцией цели общей задачи назовем функцию

Задачу линейного программирования записывают и в других формах – канонической и нормальной.

Канонической задачей – обозначение Зк, назовем

такую

n

Зк: arg max ∑сj xj = ? ,

xΩ j=1

x Ω = {x | Ax = b, xj ≥0, j = 1, n }.

Нормальной задачей Зн, назовем такую

n

Зн: arg max ∑сj xj = ? ,

xΩ j=1

x Ω = {x | Ax ≤ b, xj ≥0, j = 1, n }.

(Ее называют и канонической в симметричной форме).

5

Множеством допустимых значений задачи З назовем область определения функции

f : x →< c, x >= ∑ cj xj - обозначаем DЗ.

1≤ j≤n

6

2. Эквивалентность различных форм постановки основной задачи

Теорема 1. Постановки задач Зо, Зк, Зн эквивалентны. «Эквивалентность» означает, что Зо, Зк, Зн – это

различные постановки одной задачи. Если задачу в одной форме мы можем преобразовать к какой-то задаче в другой форме, то скажем, что мы можем свести первую задачу ко второй, З1 → З2. Задачи эквивалентны, если их можно преобразовать друг в друга.

Доказательство проведем по схеме Зн → Зк → Зо → Зн. 1) Зн → Зк. Итак, пусть мы умеем решать задачи в

канонической форме, а задана задача в нормальной форме

Зн: arg max < c, x > = ?, Ax ≤ b, x ≥0.

Введем дополнительные координаты x = (xn+1,…, xn+m)T условиями

c'=(c1,…,cn, 0…0)T Rn+m, A'=(A, Im).

Поставим каноническую задачу З'к: arg max < c', x'>=?,

решает первоначальную задачу Зн. Это очевидно.

2) Зк → Зо. Задачу Зк : arg max <c, x>=?, Ax=b, x ≥0,

запишем в виде

arg min < -c, x >=?, Ax ≤b, -Ax ≤-b, -x ≤0.

Теперь введем замену переменных с'=-c и получим

7

8

3. Преобразование Лежандра

Мы рассмотрим функции, заданные на Rn с вещественными значениями, допуская и значения равные ±∞

f : R n → R ≡ R {-∞,+∞}.

Функцию назовем собственной, если:

1)для всех x, f (x) > – ∞

2)f (x) + ∞.

Очевидно, по заданной функции надгрaфик однозначно определяется. Верно и обратное: надграфик однозначно определяет функцию. Замыканием функции f назовем функцию cl f (от английского слова close - замкнуто), имеющую своим надграфиком замыкание надграфика самой функции. Функция, совпадающая со своим замыканием, называется замкнутой.

Пример 1. (Примеры замкнутой и незамкнутой функций).

Непрерывная функция с замкнутой областью определения-– замкнута.

Функция

замкнута и является замыканием функции f.

Теорема 2. Собственную замкнутую выпуклую функцию f можно задать как поточечный "supremum" всех таких афинных функций h, что h(x) ≤ f(x).

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

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

замкнутом выпуклом множестве С , то она принадлежит

и любому содержащему С замкнутому полупространству. Значит, P лежит и в пeресечении этих

полупространств. Если же точка Q не лежит в С , то ρ(Q,C ) > 0. Тогда существует опорная плоскость

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

содержащих С .

Обратимся к заданной в теореме замкнутой выпуклой функции f. Надграфик ее – выпуклое замкнутое множество, является пересечением содержащих его полупространств. Эти полупространства могут быть трех видов:

нижние {(x,µ) | µ ≤ h(x) ≡ x,b − β},

10