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

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

(9)

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

(10)

(11)

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

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

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

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

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

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

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

(3.22)

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

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

(3.23)

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

x1=b1, x2=b2, …, xn=bn; xn+1=xn+2=…=xm=0

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

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

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

(3.27)

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

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

(3.28)

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

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

(3.29)

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

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

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

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

(3.30)

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

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

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

При выполнении симплекс преобразования диагонали, изображенные на таблице (3.30), на самом деле проводить не нужно: они легко выделяются в уме.

Выполнив S-преобразование над таблицей (3.30), мы получим новую таблицу

(3.31)

Этой таблице соответствует система уравнений:

(3.32)

Система (3.32) эквивалентна первоначальной системе (3.22), но в системе (3.32) переменная x1 исключена из всех уравнений, кроме первого. Если в таблице (3.31) элемент a’22¹0, то, приняв его за разрешающий элемент и проделав над таблицей (3.31) S-преобразование, получим новую таблицу. И в системе уравнений, соответствующей этой таблице, переменная x2 будет исключена из всех уравнений, кроме второго.

Если в таблице (3.31) a’22=0, то во втором столбце найдем элемент, не равный нулю, и примем его за разрешающий. Пусть это будет a’12. Тогда выполняя симплекс преобразование над таблицей (3.31), мы исключим x2 из всех уравнений, кроме i-того. Продолжая так дальше, мы после n преобразований придем к таблице, имеющей, например, следующий вид.

(3.33)

Таблице (3.33) соответствует система уравнений, эквивалентная первоначальной системе. Эта система уравнений имеет вид:

(3.34)

Можно считать, что система (3.34) решена относительно базисных переменных x1, x2, …, xn. Переносить члены, соответствующие свободным переменным, в правую часть для фактического решения системы (3.34) относительно базисных переменных не будем, так как в дальнейшем нас будет интересовать решение, где все свободные переменные равны 0.

Полагая xn+1=xn+2=…=xm=0, получим:

Если окажется, что x1³0, x2³0, …, xm³0, то совокупность чисел (x1, x2, …, xn, 0, 0, …, 0) дает неотрицательное решение системы.

Рассмотрим пример. Дана система уравнений

Нужно данную систему разрешить относительно переменных x1, x2, x3. Следовательно свободными переменными будут x4, x5, x6. Напишем таблицу, соответствующую данной системе уравнений.

Решим систему относительно x1 с помощью первого уравнения. За разрешающий элемент принимаем первый элемент первой строки, и подвергнем таблицу S-преобразованию. Получим новую таблицу, где первая строка переписывается, в первом столбце записываются нули, а остальные элементы вычисляются по D-правилу.

Этой таблице соответствует система уравнений, разрешенная относительно x1 (x1 входит только в первое уравнение). Исключить x2 удобнее с помощью третьего уравнения, так как коэффициент при x2 в третьем уравнении равен единице. Принимаем его за разрешающий элемент. Пишем новую таблицу

Система уравнений, соответствующая этой таблице, разрешена относительно x1 и x2 (x1 входит только в первое уравнение, а x2 только в третье).

Для разрешения системы относительно x3 за разрешающий элемент берем коэффициент при x3 во втором уравнении. Новая таблица имеет вид

Последняя таблица соответствует системе, решенной относительно базисных переменных x1, x2, x3. Полагая свободные переменные x4, x5, x6 равными нулю, получим уравнения:

-3x1=-18, откуда x1=6

-3x2=-6, откуда x2=2

-3x3=3, откуда x3=-1

Совокупность чисел x1=6, x2=2, x3=-1, x4=0, x5=0, x6=0 есть одно из решений данной системы. Оно не принадлежит к области допустимых решений, так как одна из координат x3 отрицательна.

Для решения задачи линейного программирования важно уметь находить неотрицательные (опорные) решения данной системы уравнений.

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

Пусть дана система уравнений

(3.36)

В системе (3.36) свободные члены можно считать неотрицательными, так как в обеих частях уравнения всегда можно поменять знаки.

Если при выполнении симплекс преобразований при переходе от одной системы к другой будем следить за тем, чтобы разрешающие элементы были положительными, то на последнем этапе разрешения системы относительно базисных переменных получим систему вида (3.34) и по формулам (3.35) найдем неотрицательные значения базисных переменных. Составляем отношения свободных членов bk к положительным элементам akj разрешающего столбца и среди чисел выбираем наименьшее значение. Если наименьшее значение достигается при k=i, то i-номер разрешающей строки, а разрешающим элементом будет aij.

Рассмотрим пример отыскания неотрицательных решений системы уравнений.

Пример. Найти неотрицательное решение системы уравнений

Пишем таблицу, соответствующую данной системе

Пробуем разрешить эту систему относительно x1, т.е. переменную x1 будем считать базисной переменной. Первый столбец будет базисным столбцом. Составляем отношения свободных членов к положительным элементам первого столбца 10/2=5; 4/7. Наименьшее из этих чисел 4/7. Числа 4 и 7 находятся во второй строке. Следовательно разрешающей строкой будет вторая строка и разрешающим элементом число 7. Выполняя симплекс преобразование, получим новую таблицу

Этой таблице соответствует система уравнений, разрешенная относительно базисной переменной x1. Так как обе части любого уравнения системы можно умножать и делить на любое постоянное число (система при этом будет эквивалентна прежней), то если строки таблицы имеют общий множитель, на него можно сократить. Последняя строка предыдущей таблицы имеет общий множитель 7; сокращая на него, получим таблицу

Введем в базис переменную x3, т.е. примем за разрешающий столбец третий столбец.

Из двух отношений 62/13 и 10/3 меньшим является второе. Следовательно, разрешающим элементом будет 3. Выполняя симплекс преобразование получим таблицу

Первую строку сокращаем на 28, вторую на 21

Введем в базис переменную x2. Разрешающим элементом будет 5. Снова выполняя симплекс преобразования, получим таблицу

Последнюю строку сокращаем на 3

Эта таблица соответствует системе уравнений, разрешенной относительно базисных переменных x1, x2, x3. Свободными переменными здесь являются x4 и x5. Полагая свободные переменные равными нулю, получим:

5x1=12, x1=12/5; 5x2=2, x2=2/5; 5x3=18, x3=18/5;

Совокупность чисел x1=12/5; x2=2/5; x3=18/5; x4=0; x5=0

Дает неотрицательный ответ данной системы уравнений. Эти числа можно рассматривать как координаты угловой точки (вершины) множества (многогранника) допустимых решений.

ЛИТЕРАТУРА

Малявко К.Ф. «Применение математических методов в военном

деле».

Журко М.Д. «Математические методы и основы их применения

в управлении войсками».

Журнал Квант №6 за 1989г.

Квант №7 за 1979г.

Страницы: 1, 2