85849 (612592), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

Двойственная задача имеет:

1. m переменных, соответствующих числу ограничений прямой задачи;

2. n ограничений, соответствующих числу переменных прямой задачи.

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

• Каждому ограничению b_i ПЗ соответствует переменная y_i ДЗ;

• Каждой переменной x_j ПЗ соответствует ограничение C_j ДЗ;

• Коэффициенты при x_j в ограничениях ПЗ становятся коэффициентами левой части соответствующего ограничения ДЗ;

• Коэффициенты C_j при x_j в целевой функции ПЗ становятся постоянными правой части ограничения ДЗ;

• Постоянные ограничений b_i ПЗ становятся коэффициентами целевой функции ДЗ.

Рассмотрим следующие две задачи:

F = С₁х₁+С₂х₂+... +С_nx_n→max

a

(5)

₁₁x₁ + a₂₂x₂ + ... + a_1mx_n ≤ b₁

a₂₁x₁ + a₂₂x₂ + ... + a_2mx_n ≤b₂

. . . . . . . . . . . . . . . . . . . . . . .

a_m1x₁ + a_m2x₂ + ... + a_mnx_n ≤b_m

x_j≥0 j=1,…,n

Z = b₁х₁+b₂х₂+... +b_nx_n→min

a

(6)

₁₁y₁ + a₂₁y₂ + ... + a_m1y₁ ≤ C₁

a₁₂y₁ + a₂₂y₂ + ... + a_m2y₂ ≤C₂

. . . . . . . . . . . . . . . . . . . . . . .

a_1ny_n + a_2my_n + ... + a_nmy_n ≤C_n

y_i≥0 i=1,…,m

Теорема 1 (первая теорема двойственности)

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

Fmax=Zmin

Теорема 2(вторая теорема двойственности)

Если (5) и (6) пара симметричных двойственных задач, то (x⁰₁, x⁰₂, ... , x⁰_n) и (y⁰₁, y⁰₂, ... , y⁰_n) являются их оптимальными решениями, то компоненты оптимальных решений удовлетворяются системе.

x₁⁰(a₁₁y₁⁰+a₂₁y₂⁰+…+a_m1y_n⁰-c₁)=0

x ₂⁰(a₁₂y₁⁰+a₂₂y₂⁰+…+a_m2y_n⁰-c₂)=0

. . . . . . . . . . . . . . . . . . . . . . . . . . .

x_n⁰(a_1ny₁⁰+a_2my₂⁰+…+a_m1y_n⁰-c₁)=0

y₁⁰(a₁₁x⁰₁+a₂₂x⁰₂+...+a_1mx⁰_n -b₁)=0

y₂⁰(a₂₁x⁰₁+a₂₂x⁰₂+... +a_2mx⁰_n-b₂)=0

. . . . . . . . . . . . . . . . . . . . . . . . . . .

y_n⁰(a_m1x⁰₁+a_m2x⁰₂+...+a_mnx⁰_n-b_m)=0

Заключение

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

1. Основы математических методов и их применение;

2. Решение задач с помощью симплекс – метода.

Характеристики

Список файлов курсовой работы