Применение методов линейного программирования в военном деле. Симплекс-метод (стр. 3 из 5)

где k_j (j=1,2,…,m) – коэффициенты, определяющие важность целей. Если цели имеют одинаковую важность, то k₁=k₂=…=k_m=1. При этих значениях выражение (6) является математическим ожиданием числа уничтоженных целей. Требование, чтобы каждое средство было закреплено за какой либо целью, определяется выражениями

(i=1,2,…,m) (7)

Условия, что за каждой целью закрепляется не более одного средства поражения, определяются выражением

(j=1,2,…,n) (8)

В случае знака равенства во всех выражениях (8) имеет место m=n, в противном случае m<n. Первая задача целераспределения может быть сформулирована следующим образом.

Найти такие целые значения x_ij³0 (найти такой план), удовлетворяющие условиям (7) и (8), которые обращают критерий эффективности (6) в максимум.

Как видно, эта задача линейного программирования, причем транспортного типа. В отличие от задачи на перевозку здесь ищутся значения x_ij, принимающие только два возможных значения: 0 и 1.

При малых m и n задачи целераспределения могут решаться путем элементарных расчетов и рассуждений.

Задача. Разведкой обнаружены три равноценные цели противника. Для их уничтожения выделяется командованием три средства поражения. Известны вероятности поражения каждой цели любым средством (таблица 3).

Таблица 3.

Средства поражения	цели			Количество средств поражения
	1	2	3
1	x11=1 0,8*	x12=0 0,4	x13=0 0,8*	1
2	x21=0 0,5	x22=0 0,1	x23=1 0,7	1
3	x31=0 0,2	x32=1 0,5*	x33=0 0,5	1
Количество целей	1	1	1

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

Решение. Критерий эффективности в этой задаче согласно формуле (6) определяем выражением:

(9)

Здесь положено k₁=k₂=k₃=1, т.к. все цели равноценны. Выражения (7) и (8) для условия задачи будут иметь вид:

(10)

(11)

Найти такие целые положительные корни x_ij уравнений (10) и (11), при которых критерий эффективности (9) примет максимальное значение.

Для определения оптимального плана найдем в столбцах таблицы 3 максимальные значения вероятностей и отметим их звездочками. Очевидно, что за второй целью нужно закрепить 3-е средство (x₃₂=1). Первое средство одинаково целесообразно закрепить за 1-ой или 3-ей целью. Но так как ближайшее значение к максимальной вероятности для 3-ей цели больше, чем для 1-ой, то целесообразно 1-ое средство закрепить за 1-ой целью (x₁₁=1), a 2-oe средство за 3-ей целью (x₂₃=1).

Максимальное значение математического ожидания числа пораженных целей будет равно:

При оптимальном плане будет поражено в среднем две цели. Для сравнения рассмотрим следующий план: x₁₃=1, x₂₂=1 и x₃₁=1. При этом плане средние потери будут равны

Таким образом, только за счет оптимального целераспределения эффективность средств поражения может быть значительно повышена (в данном примере почти в два раза). Этот факт имеет не только экономическое значение, но и повышает оперативность выполнения задачи на поражение цели.

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

Симплекс-метод решения задачи линейного программирования. Пусть дана система n линейных уравнений с m переменными (n<m).

(3.22)

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

Тогда систему (3.22) можно разрешить относительно переменных x₁, x₂, …,x_n которые, как и раньше, будем называть базисными переменными. В результате решения системы (3.22) базисные переменные будут выражены через остальные переменные x_n+1, x_n+2, …, x_m, называемые свободными. Число свободных переменных k=m-n. Мы имеем решение системы (3.22) в виде:

(3.23)

Свободные переменные остаются произвольными. Давая им различные значения, получим все решения системы (3.22). Одно из решений найдем, если все свободные переменные приравняем к нулю. Тогда получим:

x₁=b₁, x₂=b₂, …, x_n=b_n; x_n+1=x_n+2=…=x_m=0

Если все числа b₁, b₁, …,b_n неотрицательны, то мы будем иметь неотрицательное решение системы (3.22), соответствующее угловой точке (вершине) многогранника неотрицательных решений, это так называемое опорное решение.

Решить систему относительно базисных переменных x₁, x₂, …,x_n, используя свойства определителей n-го порядка, очень удобно. Мы будем решать эту систему путем последовательного исключения неизвестных.

Запишем в виде таблицы коэффициенты уравнений (3.24) и элемент a₁₁ заключим в рамку

(3.27)

коэффициенты от неизвестных свободных членов отделим чертой, а элемент a₁₁, заключенный в рамочку, будем называть разрешающим элементом.

Выпишем соответствующую таблицу для коэффициентов уравнений (3.26)

(3.28)

Коэффициент a’₂₁ равен нулю

Из уравнения (3.25) следует, что

(3.29)

На таблице (3.27) соединим элемент a_2j c разрешающим элементом прямой линией. Рассмотрим прямоугольник, диагональю которого является проведенная линия. Эту диагональ будем называть первой диагональю. Второй диагональю является прямая, соединяющая элементы a₂₁ и a_1j, обведенные кружком. Как следует из формулы (3.29), чтобы получить элемент a_2j, нужно из произведения элементов первой диагонали вычесть произведение второй диагонали. Остальные элементы второй строки вычисляются по этому же правилу. Это правило напоминает правило вычисления детерминантов второго порядка, поэтому будем коротко называть его D-правилом.

Переход от таблицы коэффициентов (3.27) к таблице (3.28), совершаемый с помощью D-правила, будем называть симплекс преобразованием или S-преобразованием одной таблицы в другую.

Очевидно, для выполнения S-преобразования с помощью первого уравнения необходимо, чтобы коэффициент a₁₁¹0 в противном случае переменная x₁ в первом уравнении будет отсутствовать.

Если теперь возьмем первое уравнение системы (3.22) и третье и проделаем такие же вычисления, то исключим x₁ из третьего уравнения. Продолжая такие же вычисления, исключим x₁ из всех уравнений, кроме первого. Вычисления будем производить в следующем порядке. Сначала запишем таблицу коэффициентов системы (3.22)

(3.30)

Если a₁₁¹0, и мы хотим исключить x₁ с помощью первого уравнения, то принимаем элемент a₁₁ за разрешающий и в таблице (3.30) обводим его рамкой. Строка и столбец, в которых находится разрешающий элемент, называются соответственно разрешающей строкой и разрешающим столбцом. В таблице (3.30) это первая строка и первый столбец.

Применяя симплекс преобразование, перейдем к новой таблице. В новой таблице элементы разрешающей строки переписываются без изменений. Все элементы разрешающего столбца, кроме самого разрешающего элемента заменяются нулями.

Остальные элементы новой таблицы вычисляются по D-правилу. Например, для вычисления элемента a’_ij соединяем элемент a_ij на таблице (3.30) с элементом a₁₁ прямой. В результате имеем первую диагональ. Вторая диагональ получается от соединения элементов a_i1 и a_1j, обведенных на таблице кружками. По D-правилу имеем