Методы оптимизации Лекции

1. Методы оптимизации Лекции

Нижегородский государственный технический университет им. Р.Е. Алексеева
Институт радиоэлектроники и информационных технологий
Кафедра «Электроника и сети ЭВМ»
К.т.н., доцент кафедры ЭСВМ
Калинина Н.А.
Kalinina_na@list.ru

2. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

2

3. Задача линейного программирования

Задача математического программирования относится к классу
задач линейного программирования, если целевая функция и все
ограничения задачи являются линейными функциями своих
аргументов.
Математическая постановка задачи линейного программирования в
общем виде записывается следующим образом:
n
C j x j min
j 1
n
aij x j bi , i 1, m
j 1
При этом ограничения задачи: a x b , i 1, m задают множество
допустимых решений (МДР) задачи линейного программирования,
а вектор x , x ,..., x МДР является оптимальным решением задачи
линейного программирования, если:
n
j 1
0
1
0
2
ij
j
i
0
n
n
n
C x min C x
0
j 1
3
j
j
x МДР
j 1
j
j

4. Пример задачи линейного программирования

Предприятие располагает m видами различных ресурсов, которые
обозначим R1, R2,…, Rm.
Запасы ресурсов на предприятии ограничены: ресурса R1 имеется
b1 единиц, ресурса R2 имеется b2 единиц, ..., ресурса Rm имеется bm
единиц.
Стоимость единицы ресурса Ri известна и равна di рублей (i=1…m).
Предприятие, используя эти ресурсы, может производить n видов
различных товаров T1, T2,…, Tn.
.
Для производства единицы товара Tj, необходимо затратить aij
единиц ресурса Ri.
Каждая единица товара Tj при её продаже приносит предприятию
доход Cj рублей.
Известно, что рынок не может поглотить больше, чем kj, товара Tj,
(j=1…n).
Требуется определить такой план производства товаров T1, T2,…, Tn,
который обеспечит предприятию максимальную прибыль.
4

5. Пример постановки задачи линейного программирования

Произведем математическую постановку задачи в соответствии с общим видом задач линейного
программирования.
Обозначим: xj – количество единиц товара Tj, которое планируется в производство (j=1…n).
Очевидно, что xj≥0, (j=1…n). Из условий спроса следует xj≤ kj, (j=1…n) .
Величина aijxj определяет количество ресурса Ri, которое потребуется для производства xj единиц
товара Tj.
Тогда общее количество ресурса Ri, необходимое для производства x1 ,x2,…, xn единиц товаров T1,
n
T2,…, Tn, составит ai1 x1 ai 2 x2 ... ain xn и оно ограничено величиной bi :
a x b , i 1, m
Целевая функция задачи, характеризующая прибыль:
j 1
ij
j
i
От продажи единицы товара Tj предприятие получит доход Сj.
Из этого дохода следует вычесть стоимость использованных в производстве ресурсов.
Известно, что стоимость единицы ресурса Ri равна di, а на производство единицы товара Tj затрачивается aij
единиц ресурса Ri , т.е. затраты на производство единицы товара Tj равны
diaij.
m
Следовательно, доход от производства единицы товара Tj составит C j d i aij, где учтено использование
ресурсов всех видов.
i 1
Тогда общий доход от производства всех товаров в количестве x1 ,x2,…, xn единиц соответственно составит
величину: n C m d a x
n
m
j 1
5
j
i 1
i ij
j
C j d i aij x j max
i 1
j 1
0 x j k j , j 1, n
n
aij x j bi , i 1, m
j 1
Объединив полученные условия, получим математическую
постановку задачи линейного программирования:
Задача линейного программирования может быть сформулирована как
на максимум, так и на минимум, т.е. решается задача максимизации
или минимизации.
При этом следует иметь в виду, что max f ( x1 ,..., xn ) min( f ( x1 ,..., xn )) .

6. Линейное программирование 1. Каноническая форма задачи линейного программирования

6

7. Каноническая форма задачи линейного программирования

Для решения задачи линейного программирования
часто требуется, чтобы задача была представлена в так
называемой канонической форме.
Каноническая форма - это особая форма записи
задачи, подчиняющаяся некоторым установленным
требованиям.
Задача линейного программирования, записанная в
следующем виде: n C x min
j j
j 1
n
aij x j bi , i 1, m
j 1
x j 0, j 1, n
называется задачей линейного программирования в
канонической форме.
7

8. Общий вид и каноническая форма задачи линейного программирования

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

9. Линейное программирование 1. Каноническая форма задачи линейного программирования Переход в ограничениях задачи от неравенств к

9

10. Переход в ограничениях задачи от неравенств к равенствам

Рассмотрим следующую задачу: f C j x j min
n
j 1
a11 x1 a12 x2 ... a1n xn b1
...........................................
aq1 x1 aq 2 x2 ... aqn xn bq
aq 1,1 x1 aq 1, 2 x2 ... aq 1, n xn bq 1
...........................................
a x a x ... a x b
rn n
r
r1 1 r 2 2
ar 1,1 x1 ar 1, 2 x2 ... ar 1, n xn br 1
...........................................
am1 x1 am 2 x2 ... amn xn bm
x j 0, j 1, n
10
Введем столько неотрицательных дополнительных переменных
xn 1 0,..., xn r 0 , сколько имеется ограничений-неравенств,
руководствуясь некоторыми правилами.

11. Введение остаточных переменных

Если ограничения имеют вид aij x j bi , i 1, q , то:
j 1
введем в каждое из них свою дополнительную переменную xn i , i 1, q
с коэффициентом 1;
остальные дополнительные переменные с коэффициентом 0.
В результате получим ограничения-равенства:
n
n
a x x
j 1
11
ij
j
n i
bi , i 1, q .
Переменная xn i , i 1, q называется остаточной, так как описывает
неиспользованный остаток какого-то ресурса.

12. Введение избыточных переменных

Если ограничения имеют вид a x b , i q 1, r , то: путём вычитания
из левой части переменной:
n
j 1
ij
j
i
.
xn i 0, i q 1, r
получим ограничения-равенства:
n
a x x
j 1
12
ij
j
n i
bi , i q 1, r
Переменная xn i , i 1, q называется избыточной переменной, так
как описывает превышение в ресурсах.

13. Расширенная задача линейного программирования

В целевую функцию добавочные переменные xn 1 ,..., xn r
входят с коэффициентом 0.
Таким образом, исходная задача принимает
канонический вид и называется расширенной:
n
C j x j 0 xn 1 ... 0 xn r min
j 1
n
aij x j xn i bi , i 1, q
j 1
n
aij x j xn i bi , i q 1, r
j 1
n
aij x j bi , i r 1, m
j 1
x j 0, j 1, n r
13

14. Линейное программирование 1. Каноническая форма задачи линейного программирования Переход к неотрицательным переменным

14

15. Переход к неотрицательным переменным

Пусть в исходной задаче на некоторые (или на все переменные) не
наложено условие неотрицательности:
n
C j x j min
j 1
n
aij x j bi , i 1, m
j 1
x1 0,..., xn 1 0
Здесь на переменную xn не наложено условие неотрицательности.
В этом случае сделаем замену переменных следующим образом:
xn y1 y2 , где y1 0, y2 0 .
Тогда задача принимает канонический вид:
n 1
C j x j Cn y1 Cn y2 min
j 1
n 1
aij x j ain ( y1 y2 ) bi , i 1, m
j 1
x1 0,..., xn 1 0, y1 0, y2 0
15

16. Линейное программирование 1. Каноническая форма задачи линейного программирования Задачи, где количество переменных и

16

17. Несовпадение числа переменных и ограничений

Рассмотрим задачу линейного программирования в канонической
форме, в которой число переменных больше числа ограничений (n≥m ).
Пусть линейно-зависимые ограничения исключены из системы.
a11x1 a12 x2 ... a1n xn b1
Система ограничений этой задачи:
a x a x ... a x b
21 1 22 2
2n n
2
Данная система может быть решена
...........................................
методом Гаусса, при этом возможны
am1 x1 am 2 x2 ... amn xn bm
следующие варианты решения:
rangA n m , тогда система имеет единственное решение. Это означает, что задача
линейного программирования имеет только одно допустимое решение, которое и
является оптимальным;
rangA m n , тогда система имеет множество допустимых решений, которое можно
представить, выразив m переменных через остальные n-m переменных:
17
x1 1 1,m 1 xm 1 ... 1, j x j 1n
...........................................
xi i i ,m 1 xm 1 ... i , j x j in
...........................................
xm m m,m 1 xm 1 ... m, j x j mn

18. Линейное программирование 2. Геометрическая интерпретация задачи линейного программирования

18

19. Геометрическая интерпретация задачи линейного программирования

Рассмотрим задачу линейного программирования в канонической
форме, в которой число переменных на два больше числа
ограничений (n = m + 2):
Пусть n = m + 2; rang A = m.
Выразим переменные (x3,..., xn ) и целевую функцию f через
переменные (x1, x2):
19

20. Построение множества допустимых решений

Построим МДР в осях x1, x2.
Поскольку существуют условия неотрицательности переменных, то
рассматриваем только первый квадрант.
Рассмотрим первое ограничение: x3 = α31 х1 + α 32 х2 +β3 ≥ 0
Положим х3 = 0 и получим уравнение прямой: α31 х1 + α 32 х2 +β3 = 0.
Эта прямая делит плоскость на две полуплоскости:
допустимую, где х3 > 0 (штрихуем эту область);
недопустимую, где х3 < 0.
Аналогично остальные ограничения х4 > 0,...,хn > 0 делят плоскость
на две полуплоскости – допустимую и недопустимую.
Пересечение всех допустимых
полуплоскостей образует
множество допустимых решений
(МДР).
20

21. Анализ множества допустимых решений

Найдем в МДР точку, в которой целевая функция
обращается в минимум.
Рассмотрим:
Положим f = α1 где α1- некоторая произвольная константа.
Получим уравнение прямой:
, отобразим ее в
осях x1,x2.
Положим f = α2 где α2 < α1. Прямые f=α1 и f = α2 параллельны,
причем f = α2 ближе к минимуму, чем f=α1. Сдвигая прямую f=α1 в
сторону прямой f = α2, и далее, в том же направлении, будем
уменьшать значение целевой функции.
Это движение возможно до тех пор, пока
хотя бы одна точка прямой находится в
МДР. Поэтому точка касания прямой
f = αmin и МДР есть оптимальное решение
рассматриваемой задачи. Очевидно, что
решение задачи всегда находится на
границе МДР.
21

22. Анализ МДР (возможные случаи)

При решении задачи линейного программирования графически могут
возникнуть следующие ситуации:
1.
Оптимальная прямая проходит через вершину многоугольника.
В этом случае задача имеет единственное решение.
2.
3.
4.
22
Оптимальная прямая и МДР пересекаются по стороне многоугольника.
В этом случае задача имеет бесчисленное множество решений,
заключенных на отрезке прямой, ограничивающей МДР и
совпадающей с fmin.
При перемещении прямой в сторону убывания целевой функции,
прямая f и МДР всегда имеют общие точки. В этом случае целевая
функция не ограничена на множества планов задачи, и
оптимального решения не существует. Можно ограничиться
любым допустимым решением из МДР.
На плоскости не существует ни одной точки, удовлетворяющей
ограничениям задачи, т.е. МДР - пустое множество
(нет допустимых решений). В этом случае задача
не имеет решения.

23. Замечания

1.
2.
3.
23
Если число переменных задачи линейного
программирования не превосходит трёх, а ограничения
имеют вид неравенств, то задачу можно решать, не
прибегая к канонической форме.
Если число переменных больше трёх, но n – m < 3, то
задачу можно решить геометрически, если она задана в
канонической форме.
Если число переменных больше трёх, но либо
n – m > 3, либо задача не представлена в канонической
форме, то она не имеет геометрического решения.

24. Закономерности для случая n – m = 2

1.
2.
3.
4.
24
МДР задачи линейного программирования - выпуклый
многоугольник.
Решение задачи линейного программирования всегда
лежит на границе МДР.
Решение всегда достигается в точке, где, по крайней мере,
две переменные из x1,..., xn обращаются в нуль, т.е. в точке
пересечения ограничивающих МДР прямых - в вершине
многоугольника.
Для нахождения решения достаточно перебрать все
вершины МДР и выбрать среди них ту, в которой целевая
функция достигнет оптимального значения (min или mах).

25. Другие случаи для n ≠ m 

В случае n – m = 3 геометрическая интерпретация задачи
линейного программирования строится в трехмерном
пространстве.
Для случая n – m = k > 3 геометрическая интерпретация теряет
наглядность, но общие закономерности и терминология
сохраняются. При этом МДР - это многомерный многоугольник,
границами которого являются многомерные плоскости
(гиперплоскости).
Такой многогранник называется симплексом.
Оптимальное решение, если оно существует, лежит на границе
МДР, в одной из вершин симплекса, где, по крайней мере,
k = n – m переменных из x1,..., xn равны нулю.
Для нахождения оптимального решения нужно перебрать
вершины многогранника и найти ту, в которой целевая функция
имеет оптимальное значение.
Решение задачи линейного программирования часто называют
оптимальным планом задачи.
25

26. Линейное программирование 2. Симплекс - метод решения задачи линейного программирования

26

27. Симплекс-метод  

27
Для решения задачи линейного программирования применяют специальные
методы.
Наиболее распространённый из них - симплекс-метод или метод
последовательного улучшения плана.
Пусть задача линейного программирования представлена в
канонической форме (если нет, прежде, чем приступить к
решению, следует привести ее к канонической форме):
Пусть ограничения задачи таковы, что линейно-зависимые уравнения из
системы уже удалены, т.е. ранг системы ограничений равен m : rang A=m.
Пусть m < n.
В этом случае система ограничений имеет множество решений.
Следовательно, систему ограничений методом Гаусса можно привести к виду,
в котором m переменных выражены через остальные
n - m переменных. Пусть переменные х1,...,xm, а также
целевая функция f выражены через переменные
xm+1,..,хn:

28. Симплекс-метод  

28
Необходимым условием решения такой задачи симплекс-методом является то,
что в преобразованной задаче свободные коэффициенты b1,...,bm должны быть
неотрицательны (bi ≥ 0, i = 1…m). Далее будем считать, что это условие
выполнено.
Переменная, которая стоит слева от знака равенства
в ограничениях задачи и которая выражается через
некоторые другие переменные, называется базисной.
Переменные, через которые выражены базисные,
называются свободными.
В приведенной постановке задачи х1,...,хm - базисные переменные, а хm+1,...,хn свободные переменные.
Система ограничений задачи имеет бесчисленное множество решений. Из них
выделяют особое решение, в котором все свободные переменные равны нулю, а
базисные принимают значения свободных коэффициентов:
х1 = b1,..., хm = bm; хm+1 = 0,..., хn = 0 .
Такое решение называется базисным решением.
Поскольку все bi ≥ 0, i = 1…m, то базисное решение является допустимым.
Поскольку в точке, определяемой базисным решением, n - m переменных равны
нулю, то базисное решение определяет граничную точку МДР,
более того - одну из вершин многоугольника МДР.

29. Линейное программирование 2. Симплекс - метод решения задачи линейного программирования Основные положения симплекс-метода

29

30. Основные положения симплекс-метода  

Пусть значение целевой функции в базисном решении равно γ0. Можно ли уменьшить
значение γ0, или это минимальное значение целевой функции, определяется следующим
образом:
Если среди коэффициентов целевой функции γm+1,…, γn нет положительных: γj ≤ 0,
j = m +1…n, то значение ни одной из свободных переменных хm+1,...,хn нельзя уменьшить,
так как они все равны нулю и в случае уменьшения станут отрицательными. С другой
стороны, увеличение любой из свободных переменных может привести только к
увеличению целевой функции. Следовательно, в этом случае базисное решение
оптимально.
Если среди коэффициентов γm+1,…, γn имеется хотя бы один положительный (например,
γj > 0, m +1≤ j ≤ n), тогда значение свободной переменной хj будем изменять от нуля в
сторону возрастания. При этом базисные переменные и целевая функция будут изменяться.
Поскольку γj > 0, то целевая функция будет убывать до тех пор, пока возрастает переменная
хj. Однако, увеличивая хj, мы изменяем значения базисных переменных, и в некоторый
момент они могут выйти из МДР. Здесь также возможны два случая:
Все коэффициенты а1j,а2j,...,аmj являются неположительными: аij ≤ 0, i = 1…m. Тогда при любом
значении хj базисное решение остается допустимым, а целевая функция убывает. В этом случае
оптимального решения задачи линейного программирования не существует.
Среди коэффициентов а1j,а2j,...,аmj есть хотя бы один положительный. Пусть аkj > 0, 1 ≤ k ≤ m. Тогда хj
можно увеличивать только до значения bk/akj. При дальнейшем увеличении переменной хj переменная
хk станет отрицательной. Выберем из базисных переменных ту, которая первой обратится в ноль при
увеличении хj. Очевидно, это будет переменная хi, для которой справедливо:
30

31. Разрешающий элемент 

Найденный таким образом элемент
аij называется разрешающим;
i-я строка называется разрешающей строкой;
j-й столбец – разрешающим столбцом.
Таким образом, переменную хj можно увеличивать только до значения
bi/aij и при этом значении базисная переменная хi принимает значение 0,
т.е. становится свободной.
Значение целевой функции при этом уменьшается до величины
а переменная хj из свободных перейдет в базисные.
Следовательно, теперь
свободными будут переменные
хm+1,..., хj-1,xi, хj+1, ...,хn,
базисными - переменные
х1,..., хi-1,xj, хi+1,...,хm,
это базисное решение будет лучше, чем предыдущее.
31
Далее требуется переписать задачу в новом базисе.

32. Построение задачи в новом базисе  

Выражение для новой базисной переменной xj получим из выражения для xi в
старой системе
,
что дает следующие правила вычисления коэффициентов для новых базисных
переменных:
коэффициенты i -й строки (которая была разрешающей):
коэффициенты j -го столбца (который был разрешающим):
остальные элементы (k=1…m, k≠i):
коэффициенты целевой функции:
32
На этом заканчивается один шаг симплекс-метода, который приблизил нас к
решению.
На следующем шаге анализу подвергается вновь полученная система
ограничений задачи.
Переход от одного базиса к другому продолжается до тех пор, пока не получена
система ограничений, удовлетворяющая условиям
случая 1 (т.е. получено оптимальное решение) или
случая 2.а (т.е. оптимального решения не существует).

33. Замечание  

33
Симплексом называется n -мерный многоугольник (число n – конечно),
определяющий МДР задачи линейного программирования.
Базисное решение системы ограничений определяет некоторую вершину
симплекса.
Переход от одного базиса к другому геометрически означает переход от одной
вершины симплекса к другой, более близкой к оптимуму.
Поскольку решение задачи линейного программирования всегда находится в
вершине симплекса, то если это решение существует, то через конечное число
шагов симплекс-метод приведет нас к решению.

34. Линейное программирование 2. Симплекс - метод решения задачи линейного программирования Алгоритм симплекс-метода

34

35. Построение симплекс-таблиц  

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

36. Алгоритм симплекс-метода (1)

1.
2.
3.
4.
Записываем значения bi, аij., γj задачи в верхние половинки клеток симплекстаблицы.
Если среди коэффициентов целевой функции нет положительных: γj ≤ 0, j = m
+1…n, то базисное решение xi= bi,i=1…m; xj = 0, j = m +1…n – оптимально, и
задача решена. Выход из алгоритма.
Пусть среди коэффициентов целевой функции есть положительные. Берём
любой из них, например γj. Просматриваем j -й столбец. Если Ɐi= 1…m, аij ≤ 0,
то задача не имеет оптимального решения. Выход из алгоритма.
Пусть в j-м столбце имеются положительные числа. Для каждого из них находим
отношение и выбираем среди этих отношение bk/akj и выбираем среди этих
отношений наименьшее. Пусть
.
Тогда аij. – разрешающий элемент, i -я строка
разрешающая, j -й столбец разрешающий.
36

37. Алгоритм симплекс-метода (2)

5.
6.
7.
8.
9.
37
В нижнюю половинку разрешающей клетки записываем λ=1/аij, выделяем оба
элемента разрешающей клетки.
Каждый элемент разрешающей строки, кроме аij, умножаем на λ и записываем
результат в нижнюю половинку каждой клетки.
Каждый элемент разрешающего столбца, кроме аij, умножаем на (-λ) и записываем
результат в нижнюю половинку соответствующей клетки.
Выделим в разрешающей строке все верхние, а в разрешающем столбце все нижние
элементы.
Для клетки, не принадлежащей ни к разрешающей строке, ни к разрешающему
столбцу, в нижнюю половинку клетки запишем произведение выделенных
элементов, стоящих с данной клеткой в одной строке и в одном столбце.
10. Перепишем таблицу, заменив xi ↔ xj.
11. В верхние части клеток бывшей разрешающей
строки и столбца новой таблицы запишем
нижние элементы соответствующих клеток
старой таблицы. Во все остальные клетки
новой таблицы в верхние части клеток
запишем суммы верхних и нижних элементов
соответствующих клеток старой таблицы.
12. Переходим на пункт 2 алгоритма

38. Алгоритм пересчета симплекс-таблицы

38

39. Линейное программирование 2. Симплекс - метод решения задачи линейного программирования Контроль правильности составления

39

40. Подход к контролю симплекс-таблиц

40
Для контроля правильности хода решения необходимо при формировании новой
симплекс-таблицы обязательно следить за тем, чтобы все свободные
коэффициенты в ней после пересчета остались неотрицательными: bi ≥ 0,
i = 1…m. Если это не так, то в ходе решения была неверно выбрана разрешающая
строка, и необходимо вернуться на пункт 4 алгоритма.
Для контроля правильности вычислений используется строка и столбец, где
записаны коэффициенты Ck, k = 1…n целевой функции исходной задачи до того,
как она записана через свободные переменные:
Контроль основан на том, что γ-коэффициенты
(коэффициенты последней строки таблицы)
можно находить двумя различными способами:
◦ вычислением последней строки по симплексметоду (производится в ходе алгоритма
пересчета симплекс-таблицы);
◦ вычислением γ -коэффициентов с помощью
коэффициентов целевой функции исходной
задачи.

41. Способ вычисления γ -коэффициентов

Вычисление γ -коэффициентов с помощью коэффициентов целевой функции
исходной задачи:
Пусть, что начальный базис задачи образуют переменные х1,...,хm:
Выразим функцию f через свободные переменные хm+1,...,хn:
Отсюда получаем:
41

42. Замечание

Если исходная задача сформулирована на поиск максимума, то можно поступить
двумя способами.
Во-первых, можно искать не mах(f), а min(–f) , а затем в полученном решении
поменять знак:
mах(f)= – min(–f).
Во-вторых, можно сразу решать задачу на максимум симплекс- методом. При
этом разница в алгоритмах определения минимума и определения максимума
имеет место только при анализе симплекс- таблицы и выборе разрешающего
столбца. Таким образом, если исходная задача сформулирована на максимум,
то пункты 1 и 4-12 алгоритма пересчета симплекс-таблиц остаются без
изменения, а пункты 2 и 3 изменяются следующим образом:
1. Если среди коэффициентов целевой функции нет отрицательных: γj ≥ 0,
j = m +1…n, то базисное решение xi= bi,i=1…m; xj = 0, j = m +1…n – оптимально,
и задача решена. Выход из алгоритма.
2. Пусть среди коэффициентов целевой функции есть отрицательные. Берём любой
из них, например γj. Просматриваем j -й столбец с целью выбора разрешающей
строки.
42

43. Линейное программирование 2. Симплекс - метод решения задачи линейного программирования Нахождение начального допустимого

43

44. Методы нахождения допустимого базиса

При рассмотрении симплекс-метода предполагалось, что система ограничений
задачи линейного программирования приведена к виду, когда базисные
переменные выражаются через свободные, и свободные коэффициенты bi. ≥ 0.
Другими словами, предполагалось, что нам известен начальный допустимый
базис.
Однако начальный допустимый базис не всегда бывает известен, а его
определение представляет собой самостоятельную задачу.
Рассмотрим два метода нахождения допустимого базиса:
V-задача;
М-задача.
44

45. Линейное программирование 2. Симплекс - метод решения задачи линейного программирования Нахождение начального допустимого

45

46. V-задача

Задача линейного программирования в канонической форме:
n
C j x j min
j 1
n
aij x j bi , i 1, m
j 1
x j 0, j 1, n
46
Будем считать, что bi. ≥ 0, i=1..m. Если это не так, то обе части соответствующего
уравнения умножим на (-1) так, чтобы bi. ≥ 0.
Рассмотрим вспомогательную задачу, которая называется V-зaдaчeй:
Эту задачу сразу можно решать симплекс-методом, так как её допустимый
начальный базис легко получить:

47. Решение V-задачи

47
Поскольку Ɐi=1..m Vi ≥ 0, то целевая функция задачи V ≥ 0. Предположим, что
вспомогательная задача решена и определено значение Vmin
Так как V ≥ 0, то возможны два случая:
Vmin = 0;
Vmin > 0;
Теорема:
Если Vmin = 0, то задача имеет хотя бы одно допустимое решение.
Если Vmin > 0, то система ограничений задачи несовместна.
Следовательно, решая задачу симплекс-методом, получим
либо Vmin > 0 (в этом случае задача не имеет ни одного допустимого решения),
либо Vmin = 0, и в этом случае оптимальное решение V-задачи можно
рассматривать как допустимое решение исходной задачи, так как это
допустимое решение получено по симплекс-методу, то оно является базисным.

48. Линейное программирование 2. Симплекс - метод решения задачи линейного программирования Нахождение начального допустимого

48

49. М-задача

Этот метод является альтернативой рассмотренному методу нахождения
начального допустимого решения с помощью V-задачи, но позволяет за конечное
число шагов получить не просто допустимое решение исходной задачи
линейного программирования, а решение, являющееся оптимальным.
Пусть дана задача линейного программирования в каноническом виде, что bi. ≥ 0,
i=1..m.. Если это не так, то обе части соответствующего уравнения умножим на
(-1) так, чтобы bi. ≥ 0.
Рассмотрим расширенную задачу, которая называется М-задачей:
где М- достаточно большое положительное число.
49

50. Решение М-задачи

Справедливы следующие утверждения:
1. Всегда можно указать такое М0 > 0, что для всех M > М0 из существования хотя
бы одного допустимого решения исходной задачи вытекает, что V~i 0, i 1, m
~
~
x1 ,..., ~
xn ) .
для оптимального плана М-задачи (V1 ,...,Vm , ~
~
~
~
~
~
2. Пусть (V1 ,...,Vm , ~
x1 ,..., ~
xn ) оптимальный план М-задачи, и Vi 0, i 1, m . Тогда ( x1 ,..., xn )
является оптимальным решением исходной задачи.
Таким образом, вместо исходной задачи можно решать М-задачу, которая сразу
решается симплекс-методом, если за начальный допустимый базис принять:
50
В процессе решения число М считают больше любого сравнимого с ним числа.
Если в результате решения М-задачи будет получено оптимальное решение, где
~
Vi 0, i 1, m, то это решение является оптимальным и для исходной задачи.
~
Если в оптимальном решении М- задачи среди Vi , i 1, m , существует хотя бы одно
значение V~i 0 , то исходная задача линейного программирования не имеет ни
одного допустимого решения, т.е. ограничения задачи несовместны.

51. Контрольные вопросы

52