Лекція 12 Тема: Взаємно двоїсті задачі лінійного програмування

План:

1. Основна теорема оптимізації (лінійного програмування).

2. Теорема про зв’язок оптимального розв’язку з базисним.

3. Теорема двоїстості.

Короткий зміст лекції:

Теорема 1. Якщо лінійна функція обмежена зверху (знизу) на многограннику розв’язків М системи , рангу r>0, то серед значень функції f на многограннику М існує найбільше maxf (найменше minf) значення функції f, і воно співпадає з її значенням хоча б на одній з мінімальних граней многогранника.

Теорема 2. Якщо канонічна задача лінійного програмування має оптимальний розв’язок, то вона має оптимальний розв’язок, який є базисним розв’язком системи обмежень задачі.

З цих теорем випливає, що кожну канонічну задачу можна розв’язати, використавши лише скінчену кількість обчислень:

1. Знайти всі невід’ємні базисні розв’язки системи обмежень-рівнянь, їх скінчена кількість.

2. Обчислити значення цільової функції для кожного з одержаних невід’ємних розв’язків та вибрати серед них найбільше (найменше).

3. Невід’ємний базисний розв’язок, при якому значення цільової функції f найбільше (найменше) і буде оптимальним розв’язком канонічної задачі максимізації (мінімалізації).

Нехай задана канонічна задача максимізації функції на множині невід’ємних розв’язків системи

.

(1)

Нехай система (1) має невід’ємні розв’язки. Тоді існують також невід’ємні базисні розв’язки системи (1). Можна вважати, що відповідний базис системи стовпців матриці А складається з перших r стовпців. Тоді систему (1) можна представити в такому вигляді, де невідомі системи (1) виражені через невідомі :

(2)

. Надаючи довільних числових значень, одержуємо усі можливі розв’язки системи (1).

При існує невід’ємний базисний розв’язок системи (1):

; .

Підставляючи значення які виражені через вільні невідомі, в запис функції f, одержуємо для неї новий вираз:

.

(3)

Тоді справедлива теорема:

Якщо в (3) то невід’ємний розв’язок системи (1) , , є оптимальним розв’язком даної канонічної задачі, а її оптимальне значення maxf = l.

Якщо знайдеться таке, що , то множина значень функції на множині невід’ємних розв’язків системи не обмежена зверху і, отже, канонічна задача нерозв’язна.

Нехай задана система лінійних нерівностей , та лінійна форма . Треба знайти розв’язок системи нерівностей, який максимізує лінійну форму f. Цю стандартну задачу максимізації будемо вважати задачею І. Поряд з задачею І розглянемо наступну стандартну задачу максимізації: задано систему нерівностей:

(*)

та лінійну форму . Треба знайти розв’язок системи нерівностей (*), який мінімізує лінійну форму . Цю задачу будемо називати двоїстою відносно І або задачею .

Порівнюючи І та , маємо, що двоїсту систему одержуємо із задачі І за наступними правилами:

1. Вільні члени обмежень задачі І є коефіцієнтами цільової функції двоїстої задачі, а коефіцієнти цільової функції f задачі І є вільними членами обмежень двоїстої задачі.

Отже, кількість невідомих у двоїстій задачі дорівнює кількості обмежень задачі І, тобто m, а кількість обмежень двоїстої задачі дорівнює кількості невідомих задачі І, тобто n.

2. Матриця коефіцієнтів обмежень двоїстої задачі одержується з матриці коефіцієнтів обмежень задачі І транспонуванням.

3. Система обмежень задачі складається з нерівностей типу , а система обмежень двоїстої задачі – з нерівностей протилежного типу .

4. Максимізація цільової функції f задачі І замінюється мінімізацією цільової функції двоїстої задачі.

Отже, справедлива теорема двоїстості:

Якщо система обмежень однієї із задач не має невід’ємних розв’язків, то обидві задачі І і нерозв’язні. Якщо системи обмежень задачі І і мають невід’ємні розв’язки, то обидві задачі мають оптимальні розв’язки, і оптимальні значення їх співвідношень: , де М – множина невід’ємних розв’язків системи обмежень функції f; N – множина невід’ємних розв’язків системи обмежень функції φ.

Теорема двоїстості може мати і інший вид.

Розглянемо стандартну задачу лінійного програмування: знайти maxf, на множині М розв’язків систем

.

(1)

Виходячи з цієї задачі, сформулюємо канонічну задачу мінімізації функції на множині невід’ємних розв’язків N системи рівнянь:

.

(2)

Тоді справедлива теорема двоїстості:

Якщо будь-яка із задач (1) або (2) має оптимальний розв’язок, то інша задача також має оптимальний розв’язок, та їх оптимальні значення співпадають: .

В канонічній задачі лінійного програмування системою обмежень є система лінійних рівнянь. Тому правомірним буде говорити про базисні розв’язки системи обмежень канонічній задачі, отже, і про базисні розв’язки канонічної задачі.

Контрольні запитання для самоперевірки:

1. Сформулюйте основну теорему оптимізації (лінійного програмування).

2. Який оптимальний розв’язок канонічній задачі називається базисним?

3. Як пов’язані між собою оптимальний розв’язок канонічній задачі і оптимальний базисний розв’язок?

4. Наведіть схему розв’язування канонічній задачі.

5. Сформулюйте двоїсті задачі лінійного програмування?

6. Який зв’язок існує між двоїстими задачами?

Література:

1. С.Т.Завало, В.М.Костарчук, Б.І.Хацет. Алгебра і теорія чисел, Ч.2. – К.: Вища школа, 1980. – Гл.І, §3.5;4.

2. Колесник С.Г., Цыбуленко В.В.. Алгебра и теория чисел, Ч.І – Х.: ХГПУ, 1998. – Гл. 5, § 2.2