Компьютерное моделирование задачи линейного программирования с разбросом коэффициентов в среде MathCAD

Для канонической задачи линейного программирования с неопределенными коэффициентами из заданных замкнутых интервалов реализуется метод невязок в среде Mathcad.

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

Рассмотрим каноническую задачу линейного программирования:

с’х ^ max, Ах = Ь , х > 0 (1) с неопределенными матрицей А размерности (ж х и), щ-вектором b и и-вектором с из заданных замкнутых интервалов:

| А - А0 <  АА, |Ь - &о < АЬ, |с - Со < Ас. (2) Здесь х — искомый вектор размерности и, «'» — знак транспонирования. Модули матриц и матричные неравенства (2) понимаются поэлементно.

Для решения изложенной задачи воспользуемся методом, предложенным Л. Т. Ащеп-ковым и И. Б. Косогоровой в работе [1]. Основная идея предлагаемого подхода состоит в том, чтобы определить одно решение для всего семейства задач так, чтобы оно было в том или ином смысле приемлемо для каждой задачи семейства. Для этого вводится s-невязка уравнений Ах = b (e's — минимальная норма невязки), а также еще одна задача линейного программирования для вычисления минимальной нормы невязки. Минимум целевой функции обозначим как еЩ+1. Любые векторы s и х, удовлетворяющие неравенствам (3) при sm+i = s^+i, будем называть минимальными невязками уравнения (1) и универсальными планами задачи (1), (2), соответственно.

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

Теорема [1]. Пусть задача линейного программирования б ^ min, с0х - b0у = 0, А0х = b0, А0у > с0, (4)

Ас'х + АЪ'г + е' ( ААх + АЬ ) + (5) + е' ( ДАг + Ас ) < s,

- 2 <  у <  2 , х >  0, 2 >  0 (6) разрешима. Если х , у , z , б —ее оптимальный план, то х , у — оптимальные универсальные планы задачи (1).

Для реализации этого метода используем возможности среды Mathcad [2]. Покажем решение задачи линейного программирования с разбросом коэффициентов, заданного в стандартной форме на конкретном примере. Пусть матрица А, векторы b и с имеют следующие значения:

"(60 - 68)" b = (70 - 74)

(19 - 21)

С =

<(3 - 5)1

Д5 - 7),

,

Г (1,7 - 2,3) (0,8 - 1,2) )

s _{m +} i ^ mln, - Ах - s < -Ь, Ах - s < Ь, e's - s _{m +} i < 0, х > 0, s > 0

А = (0,6 - 1,4) 0

(2 - 4)

(0,3 - 1,7) _у

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

Получим dx ^ шах, Ах <  Ь, х >  0, где

А =

'(1,7 - 2,3) (0,6 - 1,4)

(0,8 - 1,2) (2 - 4)

(0,3 -1,7)

10 0 >

0 1 0

0 0 1 _v

с- = ( ( 3 - 5 ) , ( 5 - 7 ) , 0, 0, 0 ) .

В рассматриваемом примере две переменные Др т2 и три ограничения. Приведем задачу к каноническому виду, увеличив количество переменных до семи, и запишем ее в этом виде в Mathсad. Для рассматриваемого примера система ограничений совместна, следовательно, можно приступать к решению задачи (4) — (6). Оптимальные планы данной задачи по построению будут оптимальными планами задачи (1) с коэффициентами, отвечающими серединам интервалов (2).

Запишем две матрицы коэффициентов А1, А2 и найдем новую расширенную матрицу с коэффициентами, отвечающими серединам интервалов (рис. 1).

Рис. 1. Исходные данные

Аналогично просчитываем вектора b и с. Введем обозначения:

• —    функция F(A, В, С, Q) находит решение задачи линейного программирования;

• —    описание переменных в скобках [ ] — размерность аргумента;

• —    А [n, т] — расширенная матрица условий задачи линейного программирования (записанная с учетом дополнительных и искусственных переменных);

• —    В [n] — вектор свободных членов (правых частей неравенств);

• —    С [т] — вектор коэффициентов целевой функции (вместо теоретически бесконечно большого числа М подставить большое 100000000000000);

• —    Q [n] — вектор индексов исходных базисных переменных.

Полученную задачу решаем симплексным методом. На рис. 2 приведена часть кода программы, описывающей симплексный метод.

Рис. 2. Код программы

Для заполнения промежуточных переменных используется внутренняя переменная N, а вместо возвращаемого вектора Z в конце программы можно написать одно из следующих значений:

• —    А — следующая матрица системы;

• —    В — следующий вектор свободных членов (значений базисных переменных);

• —    Q — индексы базисных переменных.

F(A, В, С, Q) [т, 2] — первый столбец результата — значения переменных соответствующих оптимальному значению, первый элемент второго вектора — значение целевой функции, второй элемент второго вектора — если равен 1, то целевая функция в области допустимых решений ограничена, если равен 0, то целевая функция в области допустимых решений не ограничена.

Рис. 3. Ответ

Решением задачи является вектор х = = (24; 16), максимальное значение функции 192 (рис. 3).