Линейное программирование

Политическая задача
В избирательном округе есть районы трех типов – городские, пригородные и сельские. В этих районах зарегистрировано, соответственно, 100000, 200000 и 50000 избирателей. Чтобы добиться успеха, желательно получить большин­ство голосов в каждом из трех регионов. Известно, что определенные пункты программы могут помочь завоевать голоса определенных групп избирателей. Основными пунктами программы являются строительство до­рог, контроль за использованием огнестрельного оружия, сельскохозяйственные субсидии и налог на бензин, направляемый на улучшение работы обществен­ного транспорта. Согласно исследованиям, можно оценить, сколько голосов будет приобретено или потеряно в каждой группе изби­рателей, если потратить 1000 долл. на пропаганду по каждому пункту програм­мы. Эта информация представлена в табл.1. Каждый элемент данной таблицы показывает, сколько тысяч избирателей удастся привлечь, потратив 1000долл. на агитацию в поддержку опре­деленного пункта предвыборной программы. Отрицательные элементы отражают потерю голосов. Задача состоит в минимизации суммы, которая позволит заво­евать 50000 голосов горожан, 100000 голосов избирателей из пригородных зон и 25 000 голосов сельских жителей.

на пропаганду строительства дорог, 0 долл. на агитацию в пользу

контроля за использованием оружия, 4 000 долл. на пропаганду сельскохозяйственных субсидий и 9 000 долл. на агитацию за введение налога на бензин.
При этом удастся привлечь 20 • (-2) + 0 • (8) + 4 • (0) + 9 • 10 = 50 тысяч голосов горожан, 20 • (5) + 0 • (2) + 4 • (0) + 9 • 0 = 100 тысяч голосов жителей пригородов и 20 • (3) + 0 • (-5) + 4 • 10 + 9 • (-2) = 82 тысячи голосов сельских жителей.

Таким образом, будет получено ровно необходимое количество голосов в городских и пригородных районах и большее количество голосов в сельской местности. (Получается, что в сельской местности привлечено голосов больше, чем наличное число избирателей!)

Чтобы получить эти голоса, придется потратить на пропаганду 20+0+4+9 = 33 тысячи долларов.

Вопрос: является ли данная стратегия наилучшей из возможных, т.е. можно ли достичь поставленных целей, потратив на пропаганду меньше денег?

переменные:
Х1– сумма (в тысячах долларов), потраченная на пропаганду программы строительства

дорог,
Х2 – сумма (в тысячах долларов), потраченная на агитацию в пользу кон­троля за использованием оружия,
Х3 – сумма (в тысячах долларов), потраченная на пропаганду программы сельскохозяйственных субсидий,
Х4 – сумма (в тысячах долларов), потраченная на агитацию за введение налога на бензин.

Требование получить не менее 50 ООО голосов избирателей-горожан можно записать в виде неравенства
-2x1 + 8 x2 + 0 x3 + 10 x4 ≥ 50 (1)

2 x2 + 0 x3 + 0 x4 ≥ 100

(2)
3 x1 -5 x2 + 10 x3 -2 x4 ≥ 25 (3)

Любые значения переменных x1, x2, x3, x4, удовлетворяющие неравенствам (1)–(3), позволят получить достаточное количество голосов избирателей в каждом регионе.

минимизировать сумму, затраченную на пропаганду, т.е. минимизировать выра­жение

x1 + x2 + x3 + x4 (4)

Хотя отрицательная агитация часто встречается в политической борьбе, отрица­тельных затрат на пропаганду не бывает. Поэтому следует записать условия
x1≥0, x2≥0, x3≥0, x4≥0 (5)

x1 + x2 + x3 + x4

(6)
при условиях:
-2x1 + 8 x2 + 0 x3 + 10 x4 ≥ 50 (7)
5 x1 + 2 x2 + 0 x3 + 0 x4 ≥ 100 (8)
3 x1 -5 x2 + 10 x3 -2 x4 ≥ 25 (9)
x1, x2, x3, x4≥0. (10)

при условиях
4x1 - x2 ≤ 8
2 x1 + x2 ≤10
5x1-2x2≥-2
x1,x2≥0

б) Пунктирные линии показывают точки, в которых целевое зна­чение равно

0, 4 и 8, соответственно

= (aij),
m-мерный вектор b =

(bj),
n-мерный вектор с = (cj)
n-мерный вектор x = (xj).
Тогда задачу линейного программирования можно запи­сать в следующем виде:
Максимизировать сТх
при условиях
Ах ≤ b,
х ≥ 0.
где сТх – это скалярное произведение двух векторов,
Ах – произведение матрицы и вектора,
х ≥ 0 означает, что все компоненты вектора х должны быть неотрицательными.

Таким образом, задачу линейного программирования в стандартной форме можно описать с по­мощью тройки (A, b, с).

в стандартную форму
1. Целевая функция минимизируется, а не максимизируется.
2. На

некоторые переменные не наложены условия неотрицательности.
3. Некоторые ограничения имеют форму равенств, т.е. имеют знак равенства вместо знака "меньше или равно".
4. Некоторые ограничения-неравенства вместо знака "меньше или равно" име­ют знак "больше или равно".
Преобразовывая задачу линейного программирования L в другую задачу ли­нейного программирования L', мы хотим, чтобы оптимальное решение задачи L' позволяло найти оптимальное решение задачи L.
Определение. Две зада­чи максимизации L и L' эквивалентны, если для каждого допустимого решения х задачи L с целевым значением z существует соответствующее допустимое ре­шение х' задачи L' с целевым значением z, а для каждого допустимого решения х' задачи L' с целевым значением z существует соответствующее допустимое решение х задачи L с целевым значением z. (Это определение не подразумева­ет взаимно однозначного соответствия между допустимыми решениями.)
Определение. Задачи минимизации L и задача максимизации L' эквивалентны, если для каждого допу­стимого решения х задачи L с целевым значением z существует соответствующее допустимое решение х' задачи L' с целевым значением z, а для каждого допусти­мого решения х' задачи L' с целевым значением z существует соответствующее допустимое решение х задачи L с целевым значением z.

Пример. Пусть исходная задача имеет вид:

Минимизировать -2x1+ 3x2
при условиях
x1 + x2 = 7
x1 - 2x2 ≤ 4
x1 ≥ 0
Если мы поменяем знаки коэффициентов целевой функции, то получим следую­щую задачу:
Максимизировать 2x1 - 3x2
при условиях
x1 + x2 = 7
x1 - 2x2 ≤ 4
x1 ≥ 0

в ко­торой на некоторые переменные не наложены ограничения неотрицательности, в

задачу, где все переменные подчиняются этому условию.
Предположим, что для некоторой переменной xj ограничение неотрицательности отсутствует. Заменим все вхождения переменной xj выражением x'j - x''j и добавим ограничения неот­рицательности x'j ≥ 0 и x''j≥0. Так, если целевая функция содержит слагаемое cjxj, то оно заменяется на cjx'j - cjx''j , а если ограничение i содержит слагаемое aijxj, оно заменяется на aijx'j - aijx''j.
Пример (продолжение нашего примера).
Для переменной х1 такое ограничение есть, а для переменной х2 – нет. Заменив переменную х2 двумя переменными х'2 и х''2 и выполнив соответствующие преобразования, получим следующую задачу:
Максимизировать 2х1 - З х'2 + З х''2
при условиях
х1+ х'2 - х''2 = 7
х1 – 2 х'2 + 2 х''2 ≤ 4
x1, х'2 , х''2 ≥ 0

Предположим, что задача линейного программирования содержит

ограничение-равен­ство f(x1, x2, . . . , xn)= b. Поскольку x = у тогда и только тогда, когда справедли­вы оба неравенства х ≥ у и x ≤ у, можно заменить данное ограничение-равенство парой ограничений-неравенств f(x1, x2, . . . , xn)≤ b и f(x1, x2, . . . , xn)≥ b. Вы­полнив такое преобразование для всех ограничений-равенств, получим задачу ли­нейного программирования, в которой все ограничения являются неравенствами.
Пример (продолжение нашего примера).
Максимизировать 2х1 - З х'2 + З х''2
при условиях
х1+ х'2 - х''2 ≤ 7
х1+ х'2 - х''2 ≥ 7
х1 – 2 х'2 + 2 х''2 ≤ 4
x1, х'2 , х''2 ≥ 0

вспомогатель­ные переменные x4,x5,x6, получим:
Максимизировать 2х1- 3x2 +

Зх3
при условиях
x4 = 7 – x1 - x2 + x3
x5 = –7 + x1 + x2 – x3
x6 = 4 – x1 + 2x2 – 2x3
x1 , x2 , x3 , x4 , x5 , x6 ≥ 0

Переменные, находящиеся в левой части равенств, называются базисными переменными, а переменные, находящиеся в правой части, − небазисными переменными.

а также "ограничения неотрицательности", и используя для обозначения значения целевой

функции переменную z, получим форму записи, которая называется ка­нонической формой. Каноническая форма задачи линейного програм­мирования выглядит следующим образом:

z = 2х1- 3x2 + Зx3
x4 = 7 – x1 - x2 + x3
x5 = –7 + x1 + x2 – x3
x6 = 4 – x1 + 2x2 – 2x3
 

z = 28 – x3/6 –x5/6 –2x6/3
x1 = 8 + x3/6 +x5/6 – x6 /3
x2 = 4 – 8x3/3 – 2x5/3 + x6 /3
x4 = 18 – x3/2 +x5/2
элементы шестерки имеют вид В = {1,2,4}, N = {3,5,6}, v = 28,

-1/6 -1/6 1/3
A = = 8/3 2/3 -1/3
1/2 -1/2 0


b =

, а индексы у A, b и с не обязатель­но

являются множествами последовательных целых чисел; они зависят от того, какие индексы входят во множества В и N.

(19}-(21), чему будут равны п, m, A, b и с?
2.

Укажите три допустимых решения задачи линейного программирования (24)-(28). Чему равно целевое значение для каждого решения?
4. Приведите следующую задачу линейного программирования к стандарт­ной форме:
Минимизировать 2х1 + 7x2
при условиях
х1 = 7
3х1 + х2 ≥ 24
х1 ≥ 0
х2 ≤ 0
5. Преобразуйте следующую задачу линейного программирования в кано­ническую форму:
Максимизировать 2х1 - 6x3
при условиях
х1 + x2 - x3 ≤ 7
3x1 - x2 ≥ 8
-x1 + 2 х2 + 2х3 ≥ 0
x1 , х2 , х3 ≥ 0
Какие переменные являются базисными, а какие небазисными?
6. Покажите, что следующая задача линейного программирования является неразрешимой:
Максимизировать 3x1 - 2x2
при условиях
х1 + x2 ≤ 2
- 2x1 - 2х2 ≤ -10
x1 , х2 ≥ 0
8. Пусть имеется задача линейного программирования общего вида с n переменными и m ограничениями. Предположим, что мы преобразовали ее в стандартную форму. Укажите верхнюю границу числа переменных и ограничений в полученной задаче.
9. Приведите пример задачи линейного программирования, для которой до­пустимая область является неограниченной, но оптимальное целевое зна­чение конечно.

Пример симплекс-алгоритма

Рассмотрим следующую задачу линейного программирования в стандартной форме:
Максимизировать 3х1+ х2 + 2х3
при условиях
х1+ х2 + 3х3 ≤30
2х1+ 2х2 + 5х3≤24
4х1+ х2 + 2х3 ≤36
х1 , х2 , х3 ≥ 0.

z = 3х1+ х2 + 2х3
х4 = 30-х1- х2 - 3х3
х5 = 24 - 2х1- 2х2 - 5х3
х6 = 36 - 4х1- х2 - 2х3

Система ограничений содержит 3 уравнения и 6 переменных.
Рассмотрим базисное решение: установим все (небазисные) переменные правой части равными 0 и вычислим значения (базисных) переменных левой части.
Базисным ре­шением является (х1, х2, х3, х4, х5, х6 ) = (0,0,0,30,24,36) и ему соответствует целевое значение z = (3 • 0) + (1 • 0) + (2 • 0) = 0. В этом базисном реше­нии xi =bi для всех i ∊ В.

x1 = 9

- x2/4 - x3/2- x6/4
Для других уравнений поступаем аналогичным образом. В результате получаем задачу линейного программирования в виде:
z = 27 + x2/4 + x3/2- 3x6/4
x1 = 9 - x2/4 - x3/2- x6/4
x4 = 21 - 3x2/4 -5x3/2+ x6/4
x5 = 6 - 3x2/2 - 4x3+ x6/2

Эта операция называется замещением. Как было показано выше, в процессе заме­щения выбираются небазисная переменная хе, называемая вводимой переменной, и базисная переменная хk называемая выводимой переменной, которые затем меняются ролями.

базисное решение (0,0,0,30,24,36) удовлетворяет новым уравнениям и имеет целевое значение

27 + (1/4) • 0 + (1/2) • 0 - (3/4) • 36 = 0.
В базисном решении, связанном с новой задачей, новые небазисные переменные равны 0. Таким образом, оно имеет вид (9,0,0,21,6,0), а соответствующее це­левое значение z = 27.
Простые арифметические действия позволяют убедиться, что данное решение удовлетворяет уравнениям исходной задачи и при подстановке в целевую функцию имеет целевое значение (3 • 9) + (1 • 0) + (2 • 0) = 27.

превышающее 18, ограничение для x4 – не превышающее 42/5, а

ограничение для x5 − не превышающее 3/2. Третье ограничение − самое строгое, следовательно, мы пере­писываем его так, чтобы x3 было в левой части, а x5 − в правой части. Затем подставляем это новое выражение в другие уравнения и получаем новую эквивалентную задачу:
 
z = 111/4 + x2/16 - x5/8- 11x6/16
x1 = 33/4 - x2/16 + x5/8 - 5x6/16
x3 = 3/2 - 3x2/8 -x5/4+ x6/8
x4 = 69/4 + 3x2/16 +5x5/8 - x6/16
 
С этой системой связано базисное решение (33/4,0,3/2,69/4,0,0) с целевым зна­чением 111/4.
Единственная возможность увеличить целевое значение − увеличить x2. Имеющиеся ограничения задают верхние границы увеличения 132, 4 и  , соответственно (верхняя граница в ограничении равна оо, посколь­ку при увеличении x2 значение базисной переменной x4 также увеличивается. Следовательно, данное уравнение не налагает никаких ограничений на величину возможного увеличения x2). Увеличиваем x2 до 4 и делаем ее базисной.

выражения в другие уравнения и получаем новую задачу:

z = 28 - x3/6 - x5/6- 2x6/3
x1 = 8 + x3/6 + x5/6 - x6/3
x2 = 4 - 9x3/3 -2x5/3+ x6/3
x4 = 18 - x3/2 +x5/2
Таким образом, для данной задачи решение (8,4,0,18,0,0) с целе­вым значением 28 является оптимальным.
Ис­ходная задача содержит только переменные х1, х2, х3, поэтому оптимальное решение имеет вид х1= 8, x2 = 4, х3= 0, с целевым значением (3 • 8) + (1 • 4) + + (2 • 0) = 28.

Замещение
Формализуем процедуру замещения. Процедура Pivot получает на входе ка­ноническую форму задачи линейного программирования, заданную кортежем (N, В, А, b, с, v), индекс k выводимой переменной хk и индекс е вводимой пе­ременной хе. Она возвращает кортеж (N', В', А', b', с', v'), описывающий новую ка­ноническую форму. (напомним, что элементы матриц А и А' являются числами, обратными коэффициентам канонической формы.)

//Вычисление коэффициентов

уравнения
//для новой базисной переменной хе
be' ⟵ bk/ake
for (для) всех j ∊ N − {е}
do aej' ⟵ akj/ake
aek ⟵ 1/ ake
> Вычисление коэффициентов остальных ограничений
for (для) всех i ∊ В − {k}
do bi' ⟵ bi − aie bе'
for (для) всех j ∊ N − {е}
do aij' ⟵ aij − aie aej'
aik' ⟵ −aieaek'’
> Вычисление целевой функции
v' ⟵ v+ cebe'
for (для) всех j ∊ N - {e}
do cj'⟵ cj − ceaej'
ci' ⟵ −ceaek'
> Вычисление новых множеств базисных и небазисных переменных
N'⟵N-{e}U{k}
B'⟵B-{k}U{e}
return (N', В', А', b', с', v')

Формальный симплекс-алгоритм

Теперь мы готовы формализовать симплекс-алгоритм, который уже продемонстрировали на примере. Этот пример был очень удачным, однако нам еще необходимо ответить на следующие вопросы.
- Как определить, что задача линейного программирования является разре­шимой?
- Что делать, если задача линейного программирования является разрешимой, однако начальное базисное решение не является допустимым?
- Как определить, что задача линейного программирования является неогра­ниченной?
- Как выбирать вводимую и выводимую переменные?
Предположим, что у нас есть процедура Initialize_Simplex(A,b,с), которая получает на входе задачу линейного программирования в стандартной форме, т.е. матрицу А = (аij) раз­мером m ⤫ n т-мерный вектор b = (bi) и n-мерный вектор с = (ci). Если задача неразрешима, процедура возвращает соответствующее сообщение и завершается. В противном случае она возвращает каноническую форму, начальное базисное решение которой является допустимым.
Процедура Simplex получает на входе задачу линейного программирования в стандартной форме, описанной выше. Она возвращает n-мерный вектор х = (xj), который является оптимальным решением задачи линейного программи­рования, заданной формулами.

⟵Initialize_Simplex(A, b, с)
while (пока) cj > 0 для некоторого

индекса j ∊ N
do выбрать индекс е ∊ N, для которого се > 0
for (для) каждого индекса i ∊ В
do if aie > 0
then Di ⟵ b/aie
else Di ⟵оо
Выбираем индекс k ∊ В, который минимизирует Di
if Di = оо
then return "Задача неограниченна“
else (N,B, A,b,c,v) ⟵ Pivot(N, В, А, b, с, v,k,e)
for i ⟵ to n
do if i∊ В
then xi '⟵ bi
else xi '⟵ 0
return (х1' , x2', . . . , xn’)

18x1 +12.5x2
при условиях
x1 +x2 ≤ 20
x1

≤ 12
x2 ≤ 16
x1 ,x2 ≥ 0
2. Решите следующую задачу линейного программирования, используя про­цедуру Simplex:
Максимизировать −5x1 − 3x2
при условиях
x1 −x2 ≤ 1
2x1 +x2 ≤ 2
x1 ,x2 ≥ 0
3. Решите следующую задачу линейного программирования, используя про­цедуру Simplex:
Минимизировать x1 + x2 + x3
при условиях
2x1 + 7.5x2 + 3x3 ≥ 10000
20x1 + 5x2 + 10x3 ≥ 30000
x1 ,x2 ,x3 ≥ 0

Двойственность
При определенных предположениях процедура Simplex за­вершается. Однако еще не доказано, что она действительно находит оптимальное решение задачи линейного программирования. Чтобы сделать это, введем новое мощное понятие − двойственность (дуальность) задач линейного программи­рования (linear-programming duality).
Двойственность − очень важное свойство. В задачах оптимизации определе­ние двойственной задачи практически всегда сопровождается открытием алго­ритма с полиномиальным временем выполнения. Двойственность также является очень мощным средством при доказательстве того, что решение действительно является оптимальным.
Для задачи максимизации определяется связанная с ней задача минимизации, причем такая, что эти две задачи имеют одно и то же оптимальное значение.
Опишем, как для заданной задачи линейного программирования, в которой требуется максимизировать целевую функцию, сформулировать двойственную (dual) задачу линейного программирования, в которой целевую функцию требу­ется минимизировать и оптимальное значение которой идентично оптимальному значению исходной задачи. При работе с двойственными задачами исходная зада­ча называется прямой (primal).

форме определим двойственную задачу следующим образом:
Чтобы

получить двойственную задачу для задачи максимизации, нужно изменить максимизацию на ми­нимизацию, поменять роли коэффициентов правых частей и целевой функции и заменить неравенства "меньше или равно" на "больше или равно". С каждым из m ограничений прямой задачи в двойственной задаче связана переменная уi, а с каждым из n ограничений двойственной задачи связана переменная прямой задачи xj. Например, для рассмотренного ранее примера симплекс-алгоритма двойственная задача выглядит следующим образом:
Минимизировать З0у1 + 24у2 + 36 у3 (прямая: Максимизировать 3х1+ х2 + 2х3
при условиях при условиях
у1 + 2у2 + 4у3 ≥3 х1+ х2 + 3х3 ≤30
у1 + 2у2 + у3 ≥1 2х1+ 2х2 + 5х3≤24
3у1 + 5у2 + 2у3≥2 4х1+ х2 + 2х3 ≤36
у1, у2, у3 ≥0 х1, х2, х3 ≥ 0 )
Отметим, что оптимальное значение двойственной зада­чи линейного программирования всегда равно оптимальному значению прямой задачи. Более того, симплекс-алгоритм неявно решает одновременно обе задачи, прямую и двойственную, тем самым обеспечивая доказательство оптимальности

Предположим, у нас есть задача линейного программирования, не при­веденная к

стандартной форме. Можно получать двойственную задачу в два этапа: сначала привести исходную задачу к стандартной форме, а затем формулировать двойственную. Однако было бы удобно иметь возможность сразу формулировать двойственную задачу. Объясните, ка­ким образом, имея произвольную задачу линейного программирования, можно получить двойственную задачу непосредственно.
3. Покажите, что задача, двойственная к двойственной задаче линейного программирования, является прямой задачей.

допустимое решение
Cначала покажем, как проверить,

является ли задача ли­нейного программирования разрешимой, и как в случае положительного ответа получить каноническую форму, базисное решение которой является допустимым. В заключение мы докажем основную теорему линейного программирования, в ко­торой утверждается, что процедура Simplex всегда дает правильный результат.
Поиск начального решения
В алгоритме Simplex предполагалось, что у нас есть некая процедура Initialize^ Simplex, которая определяет, имеет ли задача линейного программирования до­пустимые решения, и в случае положительного ответа возвращает каноническую форму, имеющую допустимое базисное решение. Опишем данную процедуру.
Даже если задача линейного программирования является разрешимой, началь­ное базисное решение может оказаться недопустимым. Рассмотрим, например,
следующую задачу:
Максимизировать 2x1− 3x2
при условиях
2x1 −x2 ≤ 2
x1 −5x2 ≤ −4
x1 ,x2 ≥ 0

каноническую форму, базисным решением будет х1 = 0, x2 =

0. Это решение нарушает второе ограничение и, следователь­но, не является допустимым. Таким образом, процедура Initialize_Simplex не может сразу возвратить эту очевидную каноническую форму. На первый взгляд, вообще неясно, имеет ли данная задача допустимые решения.
Чтобы определить, существуют ли они, можно сформулировать вспомогательную задачу линейного программирования (auxiliary linear program). Для этой вспомогательной задачи мы сможем (причем достаточно легко) найти каноническую форму, базисное ре­шение которой является допустимым.
Более того, решение этой вспомогательной задачи линейного программирования позволит определить, является ли исходная задача разрешимой, и если да, то обеспечит допустимое решение, которым можно инициализировать процедуру Simplex.

допустимого решения задачи линейного программирования L, заданной в стандартной форме:
Initialize_Simplex(A,

b, с)
Пусть k — индекс минимального коэффициента bi
if bk ≥0 > Допустимо ли начальное базисное решение?
then return ({1,2,..., n}, {п + 1, n + 2,..., п + m}, А, b, с, 0)
Образуем Laux путем добавления –х0 к левой части каждого уравнения и задаем целевую функцию равной –х0