Формирование задачи линейного программирования(ЛП)

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

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

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 предполагаются известными.

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

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

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

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

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

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

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

	А	Б	В
Тропосферная связь		--
РРС

Затраты на обслуживание одного канала РРС - 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 тыс. руб.

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