ЗАДАЧИ И МЕТОДЫ ЛИНЕЙНОГО ПРГРАММИРОВАНИЯ

1.11. ЗАДАЧИ И МЕТОДЫ ЛИНЕЙНОГО ПРГРАММИРОВАНИЯ.

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

a₁₁x₁+...+a_1nx_n=в₁

(1) ............................

a_m1x₁+...+a_1mx_n=в_n ___

где не уменьшая общности можно считать в_i≥0, i=1,m.

Характерной особенностью данной задачи является, то, что число уравнений меньше числа неизвестных, т.е. m<n. Требуется найти неотрицательные значения переменных, которые удовлетворяют уравнениям (1) и обращают в минимум целевую функцию:

(2) q=c₁x+...+a_nx

Более компактно задачи ЛП могут быть записаны в матричной форме:

q(x)=cx=min

(3) Ax=B (B≥0), x≥0

где А - матрица размером m*n, В m - мерный вектор, х и c n - мерные вектора. Матрицу А называют матрицей условий задачи векторов В - вектор ограничений задачи (3).

ГЕОМЕТРИЧЕСКА ИНТЕРПРИТАЦИЯ ОСНОВНОЙ ЗАДАЧИ ПРОГРОММИРОВАНИЯ.

В пространстве Е_n множество R₁ можно рассматривать как пересечение полупространств (при n=2 - полуплоскостей). ___

(Ax)_i≥b_i, ( i=1,m)

x≥0 (j=1,n)

СИМПЛЕКС МЕТОД.

1) Идея метода.

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

Рассмотрим задачи (каноническую) ЛП:

(4) min<c, x> R₀ ={x; Ax=b, x≥0}

x∈R₀

Задача (4)-невырожденная, т.е. невырожденна каждая угловая точка ∈R₀. Итерационный шаг состоит в переходе от одной угловой точки х круговой точке х', при котором значение целевой функции убывает; <C, x'> < <C, x> x -угловая точка. Базис В образует, первые m столбцов матрицы А. Будем записывать матрицу А=[В,D], где В=[a₁, a₂,..., a_m].

D=[a_n+1, a_n+2,..., a_n]

x^T=(x_в^Т, x_д^Т), C^Т=(C_в^Т, C_д^Т)

х_В - базис компоненты, х_д - в небазисные компоненты.

2) Выбор столбца для ввода в базис.

Известна угловая точка х: х_в>0, х_д=0, det(В)≠0, Вх_в=в

Рассмотрим векторы: х_к=х_к(ℷ)= x_в-ℷb_ak^-1 ______

ℷ k=(m+1,n)

0

где ℷ является к - й компонентой вектора х.

Если х_в>0, то при малых ℷ>0; х_k≥0, т.к. Ах_k=в, то х_k∈R_○ при малых ℷ>0. Кроме того:

<C₁ x_k>=<C₁ x>-ℷ[<C_в, B^-1_ak>-C_k]=<C, x>-ℷ∆k

∆к - определитель для любого к=1,n, причем при к=1,m;

∆к=<C_в, B^-1_ak>-C_k=<C_в, C_к>C_к=C_к-C_к=0

Окончательно; <C₁ x_к>=<C₁x>-ℷ∆x (k=1,n)

3)Выбор столбца для ввода из базиса.

В зависимости от значков величины ∆к и (В^-1_ak); возникает 3 случая. ___

a)Если для любого к=1,n будет ∆к=0, то точка х - оптимальная. _____

б) Если найдется номер к≥m+1 такой, что ∆к>0 и В^-1_ak≤0, то множество R₀ неограниченно и функция <С₁х> неограниченна снизу на R₀.

в) Пусть найдутся такие к≥m+1 и i≤m, что ∆к>0  и (В^-1_akа )>0.

4)Конечность метода.

х_k - новая угловая точка, причем <C₁k>=<C₁x>-ℷ₀ ∆k < <C₁ x>. Из этого следует, что итерационный шаг симплексного метода состоит в таком переходе от базиса а₁, а₂,..., а_s, а_s+1, a_m к базису a₁, a₂,..., a_s-1, a_s+1,..., a_m, a_k при котором целевая функция убывает, а значит, симплексный метод приводит к угловой точке х*, в которой достигает минимума за конечное число итераций.

Стр: 19
 [ВЮЮ1]

Стр: 19
 [ВЮЮ2]

Стр: 29
 [ВЮЮ3]

Стр: 1
 [ВЮЮ4]

Похожие работы

Математичекие основы теории систем: анализ сигнального графа и синтез комбинационных схем

Скачать

30399

31

10

... D=1- W3W4(W1W5W6+ W7+ W1W8+ W2W6 W7+ W2W7+2W2W8+ 1)+ W5W6(W3W4(W7+ W1W5W6+ W2W7+ W2W8+1)-1)   Для x1 Для x4 Для y Для х13 Задание 2. Синтез комбинационных схем. 2.1 Определение поставленной задачи Устройство, работа которого может быть представлена на языке алгебры высказываний, принято называть логическим. Пусть такое устройство имеет n ...

Основы теории систем и системный анализ

Скачать

71710

1

1

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

Дифференциальные уравнения и описание непрерывных систем

Скачать

38497

0

12

... в момент t, образует пространство выхода системы. Множество всех значений, которые может принять вектор состояния x в момент t, образует пространство состояний системы. 3.3. Описание непрерывных систем с помощью системы дифференциальных уравнений В любой момент времени t состояние системы является функцией начального состояния x(t0) и вектора входа m(t0, t), то есть x(t)=F[x(t0); m(t0; t)], ...

Математические основы информатики

Скачать

41359

0

6

... Рассела и во многом базируется на работе Бертрана Рассела и Альфреда Уайтхэда «Principia Mathematica» (этот фундаметальный трёхтомник математической логики до сих пор не издан на русском языке)[8]. Заключение Прародителем информатики является кибернетика, основанная американским математиком Норбертом Винером, опубликовавшим в 1948 году одноименную книгу. Основоположником ...