close

Вход

Забыли?

вход по аккаунту

?

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

код для вставкиСкачать
УДК 004.414.23
КОМПЬЮТЕРНОЕ МОДЕЛИРОВАНИЕ ЗАДАЧИ
ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
С РАЗБРОСОМ КОЭФФИЦИЕНТОВ
В СРЕДЕ MATHCAD
Е. А. Лизина, О. В. Хохлова, Е. В. Щенникова
Для канонической задачи линейного программирования с неопределенными коэффициентами из заданных замкнутых интервалов реализуется метод невязок в среде
Mathсad.
У значительного числа практических задач, математическими моделями которых являются задачи линейного программирования,
исходная информация носит приближенный
характер. Такая ситуация характерна, например, для моделей перспективного планирования, в которых используются не известные на данный момент будущие экономические показатели: стоимости продукции, запасы ресурсов, технологические нормативы
и т. п. Эти показатели определяются интервально с помощью экспертных оценок, прогнозов или проектных расчетов за счет неизбежных процедурных и вычислительных ошибок.
Рассмотрим каноническую задачу линейного программирования:
сўх ® max, Ax = b, x і 0
(1)
с неопределенными матрицей А размерности
(m ґ n), m-вектором b и n-вектором c из заданных замкнутых интервалов:
A - A0 Ј DA, b - b0 Ј Db, c - c0 Ј Dc. (2)
Здесь x — искомый вектор размерности n,
«ў» — знак транспонирования. Модули матриц и матричные неравенства (2) понимаются поэлементно.
Для решения изложенной задачи воспользуемся методом, предложенным Л. Т. Ащепковым и И. Б. Косогоровой в работе [1].
Основная идея предлагаемого подхода состоит в том, чтобы определить одно решение
для всего семейства задач так, чтобы оно
было в том или ином смысле приемлемо для
каждой задачи семейства. Для этого вводится e-невязка уравнений Ах = b (еўe — минимальная норма невязки), а также еще одна
задача линейного программирования
em +1 ® min, - Ax - e Ј -b, Ax - e Ј b,
(3)
eўe - em +1 Ј 0, x і 0, e і 0
для вычисления минимальной нормы невязки. Минимум целевой функции обозначим
как e*m +1. Любые векторы e и x, удовлетворяющие неравенствам (3) при em+1 = e*m +1,
будем называть минимальными невязками
уравнения (1) и универсальными планами
задачи (1), (2), соответственно.
При переходе от обычных планов к универсальным обеспечивается регуляризация
исходной задачи, при этом норма невязки играет роль стабилизирующего функционала.
Справедлива теорема.
Теорема [1]. Пусть задача линейного
программирования
e ® min, c0' x - b0' y = 0, A0 x = b0, А0' y і c0, (4)
Dcўx + Dbўz + eў DAx + Db +
(5)
+ eў DAўz + Dc Ј e,
(6)
разрешима. Если x , y , z , e — ее оптимальный план, то x*, y* — оптимальные
универсальные планы задачи (1).
Для реализации этого метода используем возможности среды Mathсad [2]. Покажем решение задачи линейного программирования с разбросом коэффициентов, заданного в стандартной форме на конкретном
примере. Пусть матрица A, векторы b и c
имеют следующие значения:
- z Ј y Ј z, x і 0, z і 0
*
*
*
*
ж (60 - 68) ц
ж (3 - 5) ц
з
ч
b = з (70 - 74) ч , c = з
ч,
и (5 - 7) ш
з (19 - 21) ч
и
ш
ж (1,7 - 2, 3) (0,8 - 1,2) ц
з
ч
А = з (0,6 - 1,4)
(2 - 4) ч .
з
0
(0,3 - 1,7) чш
и
© Лизина Е. А., Хохлова О. В., Щенникова Е. В., 2012
198
ВЕСТНИК Мордовского университета | 2012 | № 2
Приведем задачу к канонической форме,
т. е. перейдем от ограничений-неравенств к
ограничениям-равенствам. Для этого введем
3 дополнительные переменные, по одной в
каждое ограничение. Соответственно добавим эти переменные в целевую функцию, коэффициенты перед ними будут нулевыми.
Получим сўх ® max, Ax Ј b, x і 0, где
ж (1,7 - 2,3) (0,8 - 1,2) 1 0 0 ц
з
ч
А = з (0,6 - 1,4) (2 - 4)
0 1 0 ч,
з
0
(0,3 - 1,7) 0 0 1чш
и
— С [m] — вектор коэффициентов целевой функции (вместо теоретически бесконечно большого числа М подставить большое 100000000000000);
— Q [n] — вектор индексов исходных
базисных переменных.
Полученную задачу решаем симплексным методом. На рис. 2 приведена часть
кода программы, описывающей симплексный
метод.
cў = 3 - 5 , 5 - 7 , 0, 0, 0 .
В рассматриваемом примере две переменные х1, х2 и три ограничения. Приведем
задачу к каноническому виду, увеличив количество переменных до семи, и запишем ее
в этом виде в Mathсad. Для рассматриваемого примера система ограничений совместна, следовательно, можно приступать к решению задачи (4)—(6). Оптимальные планы
данной задачи по построению будут оптимальными планами задачи (1) с коэффициентами, отвечающими серединам интервалов (2).
Запишем две матрицы коэффициентов
A1, A2 и найдем новую расширенную матрицу с коэффициентами, отвечающими серединам интервалов (рис. 1).
Р и с. 2. Код программы
Для заполнения промежуточных переменных используется внутренняя переменная N, а вместо возвращаемого вектора Z в
конце программы можно написать одно из
следующих значений:
— A — следующая матрица системы;
— В — следующий вектор свободных
членов (значений базисных переменных);
— Q — индексы базисных переменных.
F(A, B, C, Q) [m, 2] — первый столбец
результата — значения переменных соответствующих оптимальному значению, первый
элемент второго вектора — значение целевой функции, второй элемент второго вектора — если равен 1, то целевая функция в области допустимых решений ограничена, если
равен 0, то целевая функция в области допустимых решений не ограничена.
Р и с. 1. Исходные данные
Аналогично просчитываем вектора b и c.
Введем обозначения:
— функция F(A, B, C, Q) находит решение задачи линейного программирования;
— описание переменных в скобках [ ] —
размерность аргумента;
— А [n, m] — расширенная матрица условий задачи линейного программирования
(записанная с учетом дополнительных и искусственных переменных);
— B [n] — вектор свободных членов
(правых частей неравенств);
Серия «Физико-математические науки»
Р и с. 3. Ответ
Решением задачи является вектор х =
= (24; 16), максимальное значение функции
192 (рис. 3).
199
БИБЛИОГРАФИЧЕСКИЙ СПИСОК
1. Ащепков Л. Т. Интервальная задача линейного программирования / Л. Т. Ащепков, И. Б. Косогорова // Экономика и математические методы. — 2006. — Т. 42, № 3. — С. 99—104.
2. Кирьянов Д. В. Mathcad 13 / Д. В. Кирьянов. — СПб. : БХВ-Петербург, 2006. — 608 с.
Поступила 18.03.2012.
200
ВЕСТНИК Мордовского университета | 2012 | № 2
Документ
Категория
Без категории
Просмотров
10
Размер файла
626 Кб
Теги
среды, mathcad, моделирование, разбросом, компьютерные, коэффициента, линейного, задачи, программирование
1/--страниц
Пожаловаться на содержимое документа