Компьютерное моделирование задач оптимизации. Мироновский Л.А - 26 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

Составители: 

Рубрика: 

26
Лабораторная работа № 3
РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Цель работы: ознакомиться с численными и компьютерными ме
тодами решения задач линейного программирования в пакетах
MATLAB и MAPLE.
1. ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ
1.1. Формы записи задач линейного программирования
Отдельный класс оптимизационных задач образуют задачи линей
ного программирования, в которых и оптимизируемый критерий, и
ограничения линейны. В них требуется найти экстремум целевой
функции
11 nn
fcx cx1 221
при наличии ограничений в виде неравенств
1
... , 1,2,..., .
iinni
aaxbi m11 2 3
Эти условия можно записать в матричной форме
cX extr, AX b.
T
1 2
(1)
Здесь b и c – векторыстолбцы, А – матрица размера m´n.
Существует другая форма записи, называемая канонической, когда
ограничения имеют вид равенств, а на переменные накладывается
требование положительности
cX min,AX b,X 0.
T
123
(2)
Формы записи (1) и (2) не являются независимыми. Существуют
преобразования, при помощи которых любую задачу линейного про
граммирования можно свести к одной из этих форм.
Чтобы перейти к канонической форме (2), необходимо условия типа
неравенство заменить на равенства и перейти к положительным пере
менным. Это делается путем введения дополнительных переменных;
например, вместо неравенства x
1
+3x
2
£ 0 можно записать равенство
123
30,xxx112

Страницы