II. Использование методов линейного программирования в задачах связи

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

Под словом "программирование" здесь и в дальнейшем будем по­нимать не написание программы, а составление алгоритма, планиро­вание. Основные идеи линейного программирования возникли во время войны в связи с поиском оптимальных стратегий при ведении военных операций. С той поры они начали широко использоваться в различных сферах человеческой деятельности, в том числе и в связи. Этими методами можно решить многие (хотя и не все) задачи, связанные с эффективным использованием ограниченных ресурсов.

В общем виде задача линейного программирования состоит в мак­симизации (или минимизации) линейной функции

F=c₁x₁+c₂x₂+…+c_nx_n

при условии, что переменные x_i имеют линейные ограничения вида

a₁₁x₁+a₁₂x₂+…+a_1nx_n ≤ (=, ≥) b₁

a₂₁x₁+a₂₂x₂+…+a_2nx_n ≤ (=, ≥) b₂

………………………………….

a_m1x₁+a_m2x₂+…+a_mnx_n ≤ (=, ≥) b_m

и x_i ≥0.

Значения b_i, c_j, a_ij предполагаются известными.

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

Задача линейного программирования может решаться с помощью ряда методов, носящих явно выраженный алгоритмический характер, что позволяет решать ее с помощью ЭВМ. Задачи меньшего объема мож­но решать теми же методами вручную с применением калькуляторов.

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

подготовительным.

Существует несколько методов решения задач линейного про­граммирования. Одним из них является графический.

2.2. Графический метод

Графический метод решения задач линейного программирования является наиболее простым и наглядным. Проиллюстрируем этот метод

на примере.

Имеется 14 каналов радиорелейной связи и 10 каналов тропо­сферной. По ним необходимо передать информацию трех видов: А, Б и В. Причем информация А=300 условных единиц, Б=3000, В=5000 (под информацией можно понимать и число телефонных разговоров, передачу ' данных и пр.). Возможности каналов следующие:

	А	Б	В
Тропосферная связь	90	--	300
РРС	30	1000	1200

Затраты на обслуживание одного канала РРС - 1,5 тыс. рублей, а тропосферной связи - 2,5 тыс. рублей.

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

Решение.

Обозначим через x₁ количество каналов тропосферной связи, а через x₂ - количество каналов радиорелейной связи. Тогда функцию цели можно записать

F=2.5x₁+1.5x₂

Ограничения можно записать в следующем виде:

90x₁+30x₂≤300

x₁≥0, 1000x₂ ≤3000,

x₃≥0, 300x₁+1200x₂ ≤5000,

x₁≤10, x₂≤14

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

x₁=10, x₂=14

90x₁+30x₂=300

1000x₂ =3000,

300x₁+1200x₂ =5000,

Каждое из этих уравнений изобразим прямой линией на рис.2.1. Исходя из условий задачи любая точка, расположенная между этими прямыми линиями, представляет собой допустимое решение, так как удовлетворяет всем неравенствам, составляющим систему ограничений.

Построим теперь на этом же рисунке целевую функцию. Для это­го произвольно предположим, что расходы на эксплуатацию состави­ли 4,5 тыс. руб. (эта произвольная цифра нужна для того, чтобы по­строить по двум точкам прямую). Как видно из рис. 2.1, прямая эта не пересекла область допустимых значений. Это говорит о том, что в данной задаче невозможно добиться таких расходов. Теперь предполо­жим, что расходы составили 6 тыс. руб. Новая прямая прошла парал­лельно первой и несколько приблизилась к области допустимых значе­ний (ОДЗ), по-прежнему не пересекая ее. Значит, расходы будут еще выше. Перенесем параллельно двум построенным прямым прямую до касания с первой точкой ОДЗ. Эта точка и будет оптимальной. Т.е. для того чтобы передать с наименьшими затратами требующуюся инфор­мацию, необходимо взять 2 канала первого типа и 4 канала второго типа. Стоимость в этом случае будет равна

2,5*2 + 1,5*4 = 11 тыс. руб.

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

Использование графического способа удобно только при решении заданий линейного программирования с двумя переменными. При большем числе переменных необходимо применение алгебраического аппарата. В этой ситуации используется общий метод решения задач ЛП, назы­ваемый симплекс-методом.

Симплекс-метод носит итерационный характер. Это значит, что однотипные вычислительные процедуры в определенной последователь­ности повторяются до тех пор, пока не будет получено оптимальное решение.

При использовании симплекс-метода целевая функция и ограни­чения на

Рис. 2.1

переменные должны быть представлены в так называемой стан­дартной форме. При стандартной форме линейной модели:

1) все ограничения записываются в виде равенств с неотрицатель­ной правой

частью;

2) значения всех переменных модели должны быть неотрицательны;

3) целевая функция максимизируется или минимизируется.

Исходное ограничение, записанное в виде неравенства, можно представить в виде равенства, прибавляя некоторую переменную к левой части ограничения. Например, в левую часть исходного огра­ничения

2x₁+5x₂+3x₃≤6

вводится переменная x_u>0, в результате чего исходное неравен­ство обращается в равенство

2x₁+5x₂+3x₃ +x₄=6

Если правая часть равенства отрицательна, то, умножая обе части на -1, ее можно сделать неотрицательной.

Максимизацию функции F всегда можно заменить минимизацией функции -F и наоборот.

Например,

Max F=7x₁+x₂+5x₃

можно заменить

Min (-F) =-7x₁-x₂-5x₃

Если переменная, входящая в ограничения, неограниченна по зна­ку, то такую переменную можно представить как разность двух положи­тельных переменных:

x₁=x₁'-x₁'', x1’≥0, x₁'' ≥0

Пример: требуется минимизировать функцию

F=3x₁+4x₂

при условии

x₁+x₂=10

-2x₁+3x₂≤-5

7x₁-4x₂≤6

x₂≥0

x₁ не ограничена по знаку.

Для решения задачи неравенства превратим в равенства путем добав­ления новых переменных, а переменную x₁ представим как разность двух положительных переменных:

Min F=3 x₁'-3x₁''+4x₂

x₁'-x₁''+x₂=10,

2x₁'-2x₁''-3x₂-s₁=5,

7x₁'-7x₁''-4x₂+s₂=6,

x₁', x₁'', x₂, s₁, s₂ ≥0

Общую идею симплекс-метода можно проиллюстрировать на при­мере.

Пусть требуется максимизировать функцию

F=3x₁+2x₂

при ограничениях

x₁+2x₂≤6,

2x₁+x₂≤8,

-x₁+x₂≤1,

x₂≤2; x₁, x₂ ≥0.

Приведенная линейная модель может быть сведена к стандартной форме

Max F=3x₁+2x₂+0x₃+0x₄+0x₅+0x₆

при ограничениях

x₁+2x₂+x₃ =6,

4x₁+2x₂ +x₄ =8,

-x₁+ x₂ +x₅ =1,

x₂ +x₆=2

x₁, x₂, x₃, x₄, x₅, x₆ ≥0.

На рис.2.2 представлено пространство решений данной задачи. Каждую точку этого пространства можно определить c помощью пере­менных, входящих в модель стандартной формы. Например, при x₃=0 первое ограничение принимает вид равенства 2x₁+4x₂=12 , которое можно представить прямой 3-4.

Поскольку стандартная модель содержит четыре уравнения и шесть неизвестных, в каждой из экстремальных точек две переменные (=6-4) должны иметь нулевые значения. Например, в точке 1 – x₁ и x₂ равны нулю, в точке 2 – x₄ и x₂, в точке 3 – x₃ и x₄. Можно заметить, что экстремальные точки отличаются только одной переменной Переменные, имеющие

Рис 2.2

отличное от нуля значение, называются базисны­ми, остальные – небазисными переменными.

Каждую последующую экстремальную точку можно определить путем замены одной из текущих небазисных переменных текущей базисной пе­ременной.

Алгоритм симплекс-метода состоит из следующих шагов.

Шаг 1. Используя линейную модель стандартной формы, определяют

начальное допустимое базисное решение.

Шаг 2. Из числа текущих небазисных переменных выбирается одна, ко­торая включается в новый базис. Увеличение этой переменной должно обеспечить улучшение значения целевой функции. За­тем осуществляется переход к следующему шагу.

Шаг 3. Из числа базисных переменных выбирается одна, которая долж­на принять, нулевое значение (т.е. стать небазисной) при введении в состав базисных новой переменной.

Шаг 4. Находится новое базисное решение, соответствующее новым составам базисных и небазисных переменных.

В нашем примере точку I можно использовать как начальное до­пустимое решение. В этой точке x₁=x₂=0 и x₃=6, x₄=8, x₅=1, x₆=2, а функция F=0.

Преобразовав уравнение целевой функции так, чтобы его правая часть стала равна нулю

F-3x₁+2x₂=0

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

Полученные результаты удобно представить в виде табл.2.1.

Первый столбец этой таблицы содержит переменные пробного базиса x₃, x₄, x₅, x₆, значения которых приведены в последнем столбце.

Является ли полученное решение оптимальным? Нет. Об этом сви­детельствует наличие в строке целевой функции отрицательных чисел.

Таблица 2.1

Базисные переменные	F	x1	x2	x3	x4	x5	x6	Решение
x3	0	1	2	1	0	0	0	6
x4	0	2	1	0	1	0	0	8
x5	0	-1	1	0	0	1	0	1
x6	0	0	1	0	0	0	1	2
F	1	-3	-2	0	0	0	0	0

Это эквивалентно наличию положительных коэффициентов при этих пе­ременных в исходной целевой функции. Поскольку речь идет о макси­мизации, значение F может быть увеличено при увеличении как x₁, так и x₂. Если бы в отроке целевой функции не было отрицательных чисел, это означало бы, что функция цели уже не пересекает оси в области положительных решений.

А в качестве переменной, включаемой в базис, выберем x₁, так как коэффициент при ней больше и функция цели изменяется сильнее. Исключаемая переменная выбирается из совокупности базисных пере­менных x₃, x₄, x₅, x₆. Этой переменной является та, которая первой обращается в нуль при увеличении включаемой переменной вплоть до значения, соответствующего смежной экстремальной точке. В нашем случае переменная x₁ достигает максимально допустимого значения, равного 4, в точке 2, при этом исключаемой из базиса переменной становится x₄.

Отношение, фиксирующее искомую точку пересечения и идентифи­цирующее исключаемую переменную, можно определить прямо из симплекс-таблицы. Для этого в столбце, соответствующем вводимой переменной x, вычеркиваются отрицательные и нулевые элементы ограничений. Затем вычисляются отношения постоянных, фигурирующих в правых час­тях этих ограничений, к оставшимся элементам столбца, соответствую­щего вводимой переменной x₁. Исключаемой переменной будет та переменная базиса, для которой указанное выше отношение минималь­но.

Указанная процедура иллюстрируется табл.2.2.

Таблица 2.2

Базисные переменные	F	x1	x2	x3	x4	x5	x6	Решение
x3	0	1	2	1	0	0	0	6 (6/1=6)
x4	0	2	1	0	1	0	0	8 (8/2=4)
x5	0	-1	1	0	0	1	0	1
x6	0	0	1	0	0	0	1	2
F	1	-3	-2	0	0	0	0	0

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

Все элементы новой ведущей строки получаются путем деления элементов предыдущей ведущей отроки на ведущий элемент. Все ос­тальные уравнения получаются по правилу

(Новое уравнение) = (Предыдущее уравнение) -

-(Коэффициент ведущего столбца предыдущего уравнения)*

*(Новая ведущая строка).

В новом ведущем уравнении ведущий элемент становится равным 1, а все остальные коэффициенты, фигурировавшие в ведущем стол­бце, становятся равными 0.

Составим по этому правилу новую симплекс-таблицу. Новая ведущая строка:

	x1	x2	x3	x4	x5	x6	Решение
0	1	1/2	0	1/2	0	0	8/2=4

Для строки получим

(

)

1

-3

-2

0

0

0

0

0

-

(

)

0

3

3/2

0

3/2

0

0

12

(

)

------------------------------------------------------------------------------

1

0

-1/2

0

3/2

0

0

12

Для x₃ – уравнения

)

)

(

(

0	1	2	1	0	0	0	6
1	-1	-1/2	0	-1/2	0	0	-4

(

)

------------------------------------------------------------------------------

0

0

3/2

1

-1/2

0

0

2

Для x₅ – уравнения

0 ( (	1	2	1	0	0	0	6 ) )
1	-1	-1/2	0	-1/2	0	0	-4

(

)

------------------------------------------------------------------------------

0

0

3/2

1

-1/2

0

0

2

x₆ - уравнение останется таким же, постольку соответствующий ко­эффициент ведущего столбца равен нулю.

Таким образом, симплекс- таблица примет вид

Таблица 2.3

Базисные переменные	F	x1	x2	x3	x4	x5	x6	Решение
x3	0	0	3/2	1	-1/2	0	0	2 (4/3)
x1	0	1	1/2	0	1/2	0	0	4 (8)
x5	0	0	3/2	0	1/2	1	0	5 (10/3)
x6	0	0	1	0	0	0	1	2 (2)
F	1	0	-1/2	0	3/2	0	0	12

Из последней таблицы следует, что на очередной итерации в качестве вводимой переменной следует выбрать x₂, т.к. коэффи­циент при этой переменной в F -уравнении равен -1/2. Исключае­мой переменной будет x₃ , а включаемой – x₂ . Новая симплекс-таблица будет иметь вид табл.2.4.

Таблица 2.4

Базисные переменные	F	x1	x2	x3	x4	x5	x6	Решение
x3	0	0	1	2/3	-1/3	0	0	4/3
x1	0	1	0	-1/3	2/3	0	0	10/3
x5	0	0	0	-1	1	1	0	3
x6	0	0	0	-2/3	1/3	0	1	2/3
F	1	0	0	1/3	4/3	0	0	38/3

В новом базисном решении x₁=10/3 и x₂=4/3. Значение F увеличилось с 12 (предыдущая таблица) до 38/3. Этот прирост целевой функции обусловлен увеличением x₂ от 0 до 4/3, так как из F -строки предыдущей симплекс-таблицы следует, что возрастанию данной пе­ременной на единицу соответствует увеличение функции на 1/2.

Последняя симплекс-таблица соответствует оптимальному реше­нию задачи, так как в F -строке ни одна из небазисных перемен­ных не фигурирует c отрицательным коэффициентом. На этом и завершаются вычислительные процедуры симплекс-метода.

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

2.4. Частные случаи использования симплекс-метода.

Рассмотрим пример. Требуется минимизировать функцию

F=4x₁+x₂

при ограничениях

3x₁+x₂=3,

4x₁+3x₂≥6,

x₁+2x₂≤4,

x₁, x₂ ≥0

Запишем задачу в стандартной форме

3x₁+ x₂ =3,

4x₁+3x₂-x₃ =6,

x₁+2x₂ +x₄=4,

Таким образом, имеются три уравнения и четыре неизвестных. В отли­чие от случая, когда каждое уравнение содержит остаточную перемен­ную, в заданном случае уже нельзя быть уверенным в том, что при нулевом значении одной из переменных все базисные переменные будут неотрицательными. В этом случае используется метод искус­ственных переменных.

Искусственные переменные вводятся только для того, чтобы получить базисное решение.

В нашем примере в первом и втором уравнениях нет переменных, выполняющих роль остаточных. Поэтому введем в каждое из этих урав­нений по одной искусственной переменной (R₁ и R₂):

3x₁+x₂ + R₁ =3,

4x₁+3x₂-x₃ + R₂ =6,

x₁+2x₂ +x₄=4,

За использование этих переменных в составе целевой функции нужно ввести штраф, приписывая им большой коэффициент М.

Тогда функция цели примет вид:

Min F=4x₁+x₂+MR₁+MR₂.

Начальное допустимое решение при этом будет

R₁=3, R₂=6 и x4=4.

Т.к. мы имеем дело с описанием минимума, а переменные R₁ и R₂ вве­дены в функцию цели с большим коэффициентом М, то метод миними­зации должен привести к тому, что в оптимальном решении они обра­тятся в ноль.

Для построения симплекс-таблицы выразим искусственные пере­менные через небазисные:

R₁=3-3x₁-x₂

R₂=6-4x₁-3x₂+x₃

F=4x₁+x₂+M (3-3x₁-x₂) +M (6-4x₁-3x₂+x₃) = (4-7M) x1+ (1-4M) x₂+Mx₃+9M

Тогда первая симплекс-таблица будет иметь вид

Базисные переменные	x1	x2	x3			x4	Решение
F	-4+7M	-1+4M	-M	0	0	0	9M
R1	3	1	0	1	0	0	3
R2	4	3	-1	0	1	0	6
x4	1	2	0	0	0	1	4

Далее решение ведется обычным образом. Оптимальному решению соответствует точка x₁=2/5, x₂=9/5, где F=17/5.

Отметим, что при максимизации F штраф М необходимо брать c обратным знаком.

Рассмотрим другой пример.

Max F=3x₁+9x₂

при условии

x₁+4x₂≤8,

x₁+2x₂≤4,

x₁, x₂ ≥0

Введя остаточные переменные x₃ и x₄, построим симплекс-таблицу

	x1	x2	x3	x4
F	-3	-9	0	0	0
x3	1	4	1	0	8
x4	1	2	0	1	4

x₃- выводится, x₂ вводится

На следующем шаге

	x1	x2	x3	x4
F	-3/4	0	9/4	0	18
x1	1/4	1	1/4	0	2
x4	1/2	0	-1/2	1	0

x₄- выводится, x₁ - вводится

Получим

	x1	x2	x3	x4
F	0	0	3/2	3/2	18
x2	0	1	1/2	-1/2	2
x1	1	0	-1	2	0

Заметим, что после двух итераций значение функции цели не умень­шилось (18). Т.е. налицо зацикливание. Что же это означает? Рас­смотрим рис.2.3. Через точку оптимума проходят три прямые, а за­дача содержит только две переменные. Отсюда следует вывод, что одно из ограничений лишнее.

Max F=2x₁+4x₂

при условии

Рис. 2.3

Рис. 2.4

Рис. 2.5

x₁+2x₂≤5,

x₁ + x₂≤4,

x₁, x₂ ≥0

Рис. 2.4 иллюстрирует суть дела. Целевая функция параллельна одной из прямой ограничений. Это означает, что задача имеет бес­конечное множество решений.

Может быть, случай, когда решение отсутствует вообще.

Пример:

Max F=3x₁+2x₂

при условии

2x₁+ x₂≤2,

x₁+4x₂≥12,

x₁, x₂ ≥0.

Рис.2.5 хорошо иллюстрирует суть дела.