Решение и корректировка решений близких задач линейно-квадратичного программирования
Использование конечного двойственного метода для корректировки решений близких задач линейно-квадратичного программирования. Разработка программы на языке С для решения и корректировки решений. Двойственная задача. Основные понятия и утверждения.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | курсовая работа |
| Язык | русский |
| Дата добавления | 01.06.2014 |
| Размер файла | 165,9 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ
Учреждение образования
"Гомельский государственный университет имени Франциска Скорины"
Математический факультет
Кафедра вычислительной математики и программирования
РЕШЕНИЕ И КОРРЕКТИРОВКА РЕШЕНИЙ БЛИЗКИХ ЗАДАЧ ЛИНЕЙНО-КВАДРАТИЧНОГО ПРОГРАММИРОВАНИЯ
КУРСОВАЯ РАБОТА
Исполнитель:
студент группы ПМ-32 Долгалева Анна Александровна
Научный руководитель:
к. ф. - м. н., доцент Лубочкин Александр Васильевич
Гомель 2014
Реферат
Курсовая работа 21 страница, 1 приложение, 7 источников.
Ключевые слова: план, оптимальный план, условие оптимальности, критерий управляемости основного ограничения, критерий оптимальности, двойственная задача, конечный двойственный метод.
Объект исследования: близкие задачи линейно-квадратичного программирования.
Методы исследования: использование программы двойственного метода квадратичного программирования для решения и корректировки решений близких задач линейно-квадратичного программирования.
Цель курсовой работы: Разработать программу для решения и корректировки решений близких задач линейно-квадратичного программирования.
Выводы: для задачи корректировки решений близких задач линейно-квадратичного программирования использован конечный двойственный метод, написана программа на языке С.
Содержание
- Реферат
- Содержание
- Введение
- 1. Постановка задачи
- 1.1 Прямая задача квадратичного программирования. Основные понятия
- 1.2 Основные утверждения
- 1.3 Проблема построения решений близких задач квадратичного программирования
- 2. Двойственная задача. основные понятия и утверждения
- 3. Классификация методов решения линейно-квадратичных задач
- 4. Два подхода к проблеме решения близких линейно-квадратичных задач
- 5. Использование программы DMQP
- Заключение
- Список использованных источников
- Приложения
Введение
В теории управления до сих пор являются актуальными многие задачи. Например, задачи регулирования, демпфирования и стабилизации динамических систем с ограниченными управлениями.
Эти задачи в теории управления решались разными методами. Они не позволяли учитывать ограничения на управления, которые характерны для современных постановок задач.
В середине прошлого века от общей теории управлений отделилась теория оптимального управления, которая с тех пор прошла огромный путь развития. Было построено много различных способов решения задач оптимального управления: и линейных, и линейно-негладких, и линейно-квадратичных, и других. Поэтому уместно применять методы оптимального управления к классическим задачам управления. При этом будут автоматически учитываться ограничения на управление и траекторию, т.к. они являются составными элементами задач оптимального управления. При этом переходным процессам будут приданы дополнительные полезные свойства: минимизация энергии, расхода топлива, интенсивности управления и другие. Но в применении к классическим задачам управления задачи оптимального управления являются не основными, а вспомогательными. При этом приходится строить решения целой серии близких задач оптимального управления выбранного вида, т.е. актуальной является проблема корректировки решений близких задач оптимального управления. Эти задачи можно решать в различных классах допустимого управления. Тогда соответственно задачи оптимального управления будут эквивалентны конечномерным задачам математического программирования.
В данной работе в качестве таких задач рассматривается линейно-квадратичная задача.
линейное квадратичное программирование язык
1. Постановка задачи
1.1 Прямая задача квадратичного программирования. Основные понятия
Рассмотрим задачу
, (1.1)
, (1.2)
, (1.3)
где ,
,
; ;
,
; , .
Задачу (1.1) - (1.3) можно трактовать как поиск такого решения уравнения (1.2) на ограниченном множестве (1.3), которое минимально в среднеквадратичном уклоняется от нулевого вектора.
Любой n-вектор x, удовлетворяющий основному (1.2) и прямым (1.3) ограничениям называется планом задачи (1.1) - (1.3).
План , доставляющий минимум целевой функции (1.1), называется оптимальным планом.
Субоптимальный (е-оптимальный) план (при заданном числе е > 0) определяется неравенством
(1.4)
1.2 Основные утверждения
Достаточное условие оптимальности плана
Теорема 1.1 (достаточное условие оптимальности) Если для плана выполняются соотношения
при ;
при ; (1.5)
при , ,
то оптимальный план задачи (1.1) - (1.3).
Управляемость основного ограничения. Опора ограничений. Опорный план
Задача (1.1) - (1.3) можно решать прямыми методами, на итерациях которых, преобразуются планы задачи. Следовательно, возникает проблема соблюдения на итерациях методов всех ограничений задачи. При этом главной является проблема выполнения основного ограничения (1.2), поскольку соблюдение на n-векторе прямых ограничений (1.3) не составляет никакого труда. Таким образом, первой при разработке прямых методов решения задачи (1.1) - (1.3) возникает задача управления основным ее ограничением.
Основное ограничение (1.2) задачи (1.1) - (1.3) называется управляемым, если для любых m-вектора b и n-вектора х найдется такой n-вектор , что на векторе будет выполняться основное ограничение:
Из последнего равенства имеем , откуда
(1.6)
Таким образом, задача управляемости основным ограничением свелась к проблеме разрешимости относительно системы (1.6), состоящей из т линейных алгебраических уравнений с n неизвестными .
Из курса линейной алгебры известно, что система (1.6) разрешима (при любых правых частях) тогда и только тогда, когда матрица А полного ранга, т.е.
(1.7)
Таким образам, доказана
Теорема 1.2 (критерий управляемости основного ограничения) Для управляемости основного ограничения (1.2) задачи (1.1) - (1.3) необходимо и достаточно выполнения условия (1.7).
Из теоремы 1.2 следует, что в случае управляемости основного ограничения в матрице А можно выделить систему из т линейно независимых столбцов. Пусть такая система выбрана. Множество индексов этих столбцов обозначается , а соответствующая вырезка из матрицы А - .
Тогда имеем
(1.8)
Множество индексов , называется опорой ограничений, если для опорной матрицы выполняется условие (1.8).
Теорема 1.3 (вторая форма критерия управляемости основного ограничения) Для управляемости основного ограничения (1.2) задачu (1.1) - (1.3) необходимо и достаточно существования хотя бы одной опоры ограничений.
Из сделанных предположений следует, что в задаче (1.1) - (1.3) существует хотя бы одна опора.
Поскольку на каждой итерации прямых методов осуществляется переход от плана х задачи к некоторому другому плану , то при разработке прямых методов возникает частный случай управления основным ограничением, а именно, поскольку х - план задачи, то , и из (1.6) получаем
(1.9)
Используя опору ограничений, равенство (1.9) запишем в виде
,
где ,
,
,
откуда следует, что
, (1.10)
где .
Таким образом, каким бы ни взять (n - m) - вектор , подсчитав по формуле (1.10) m-вектор получим n-вектор , добавление которого к любому плану х дает n-вектор , являющийся псевдопланом, т.е. вектором, на котором выполняется основное ограничение.
Пару из плана и опоры ограничений называется опорным планом.
Будем считать его невырожденным, если
(1.11)
Формула приращения целевой функции
Пусть - некоторый (начальный) опорный план задачи (1.1) - (1.3), - некоторый ее псевдоплан. Получим формулу приращения целевой функции (1.1) при переходе от к при неизменной опоре ограничений
(1.12)
Обозначив и воспользовавшись соотношением (1.10), из (1.12) получим
(1.13)
Обозначим через и (1.14)
Введём m - вектор потенциалов :
(1.15)
и вектор оценок со следующими компонентами
(1.16)
Используя (1.15), (1.16), из (1.13) получим
. (1.17)
Очевидно .
Выясним физический смысл оценок .
Положим , где k - некоторый индекс из . Компоненту найдём из (1.10): .
Согласно (1.17) имеем
, (1.18)
где через обозначена величина более высокого порядка, чем , т.е. . Из (1.18) видно, что - взята с противоположным знаком начальная скорость изменения целевой функции (1.1) в точке при увеличении k-ой неопорной компоненты плана , если при этом остальные неопорные компоненты плана не изменяются, а опорные изменяются так, чтобы выполнялось основное ограничение (1.12).
Критерий оптимальности
Из формулы приращения (1.17) следует следующая теорема:
Теорема 1.4 (критерий оптимальности) Для оптимальности плана . в задаче (1.1) - (1.9) достаточно существования такой опоры ; что для опорного плана выполняются соотношения
при ;
при ; (1.19)
при ,
В случае невырожденности опорного плана соотношения (1.19), являются необходимыми для оптимальности плана х.
Доказательство. Достаточность. Пусть на опорном плане соотношения (1.19) выполняются. Рассмотрим произвольный другой план . Тогда для неопорных компонент вектора имеем:
если , то ;
если , то , . (1.20)
Сравнивая (1.19) и (1.20), получим , . Подставив эти значения в (1.17) и учитывая при этом, что , получим
Таким образом, для любого плана , что и означает оптимальность плана х.
Необходимость (доказательство от противного). Пусть х - оптимальный план, а - невырожденный опорный план задачи (1.1) - (1.3).
Предположим, что, вопреки утверждению, соотношения (1.19) не выполняются. Для определённости предположим, что для некоторого соотношения (1.19) нарушаются следующим образом: при .
Построим вектор с компонентами
; , ; . (1.21)
Тогда, очевидно, вектор при всех удовлетворяет основному ограничению, т.е. является псевдопланом задачи. Покажем, что при достаточно малых он является и ее планом. Для этого проверим на нем прямые ограничения.
Поскольку , то при всех достаточно малых будут выполняться неравенства .
Так как , то при любом будут справедливы неравенства
(т.к. х - план задачи).
Рассмотрим . В силу невырожденности (1.11) опорного плана на векторе выполнены строгие неравенства . В силу (1.21) вектор линейно зависит от , и поэтому его норма будет сколь угодно мала при достаточно малом . Следовательно, при достаточно малом будут выполнены неравенства .
Итак показано, что , такое, что при всех , , вектор является планом задачи (1.1) - (1.3). Учитывая квадратичную зависимость от значения , заключаем, что, и поэтому знак при достаточно малом не влияет на знак (1.17).
Оценим на векторе (1.21) приращение целевой функции
при достаточно малом . Отсюда имеем при достаточно малом , что противоречит оптимальности плана х.
Другие случаи нарушения соотношений (1.19) исследуются аналогично.
Пару , на которой выполняются соотношения (1.19), называют оптимальным опорным планом.
Достаточное условие субоптимальности
Пусть - опорный план задачи (1.1) - (1.3). Рассмотрим для него линейную часть формулы при ращения (1.17)
. (1.22)
Найдём максимум функции (т.е. величину максимального уменьшения линейной части формулы приращения) на таких псевдопланах , для неопорных компонент которых выполняются ограничения (1.3), т.е. в случае соблюдения ограничений ,
Указанное максимальное значение достигается на векторе :
при
при , ,
и равно числу
(1.23)
Число (1.23) называют оценкой субоптимальности опорного плана , что оправдано тем, что с учетом (1.22) из формулы приращения (1.17) при следует неравенство
(1.24)
которое оценивает сверху отклонение по значению целевой функции плана х от оптимального плана .
Теорема 1.5 (достаточное условие субоптимальности) При любом для е - оптимальности плана х достаточно существования такой опоры , при которой для оценки субоптuмальности опорного плана выполняется неравенство
Доказательство следует из формулы (1.24): и определения е - оптимальности плана (1.4).
Очевидно, что в отличие от задачи ЛП, оценка (1.23) всегда будет оценкой сверху для плана х, за исключением случая оптимального опорного плана , когда . Это объясняется тем, что в отличие от линейной в линейно-квадратичной задаче оценки , зависят не только от опоры, но и от плана х. А это объясняется тем, что целевая функция (1.1) квадратичная. При нахождении формулы приращения (1.17) была выделена линейная часть приращения, а нелинейность содержится в слагаемом . При вычислении же оценки (1.23) оптимизировалась только линейная часть формулы приращения.
1.3 Проблема построения решений близких задач квадратичного программирования
Основной вопрос при решении задачи (1.1) - (1.3) состоит в построении оптимального плана . Тут же возникает вопрос: как изменится оптимальный план и оптимальное значение функции при изменении параметров задачи? (проблема чувствительности). Для ответа на поставленный вопрос, надо найти коэффициент чувствительности.
Коэффициентом чувствительности значения задачи по отношению к некоторому параметру задачи называется начальная скорость изменения значения целевой функции при изменении этого параметра.
Например, если коэффициент чувствительности к некоторому параметру равен нулю, то оптимальный план задачи будет при достаточно малом изменении параметра задачи оптимальным и для близкой задачи.
2. Двойственная задача. основные понятия и утверждения
Согласно правилу составления двойственных задач, двойственная задача для задачи (1.1) - (1.3) имеет вид:
(2.1)
Задача (1.1) - (1.3) называется прямой, а (2.1) - двойственная к ней.
Совокупность , удовлетворяющая ограничениям двойственной задачи (2.1), называется двойственным планом задачи. Причём - сопровождающий опору псевдоплан.
Решение задачи (2.1) называется оптимальным двойственным планом. Решения задач (1.1) - (1.3) и (2.1) удовлетворяют следующим соотношениям двойственности, выражающим тесную связь между прямой и двойственной задачей:
1) для существования решения прямой задачи необходимо существования решения двойственной задачи;
2) оптимальные значения прямой и двойственной целевых функций равны:
3) для любого прямого и двойственного планов выполняется неравенство:
4) если на некоторой паре {} из прямого и двойственного планов выполняется равенство , то - решение задач (1.1) - (1.3), (1.2).
Копланом задачи называется вектор
(2.2)
Для согласования двойственного плана должны выполнятся условия:
(2.3)
Пара из коплана и опоры задачи называется опорным копланом.
Теорема (критерий оптимальности в двойственной задаче) Для оптимальности согласованного двойственного плана достаточно существования такой опоры задачи , что для согласованных опорного коплана и псевдоплана выполняются соотношения
(2.4)
3. Классификация методов решения линейно-квадратичных задач
Исходя из соотношений (1.19) критерия оптимальности, а также с учетом формул (1.14) - (1.16), которые определяют векторы потенциалов и оценок, следует структура оптимального плана задачи (1.1) - (1.3):
1) опорные компоненты , "отвечают" только за соблюдение основного ограничения (1.2) и могут принимать любые значения из отрезков: , (предпочтительнее, конечно, вариант, когда все последние неравенства строгие, т.е. случай невырожденности опорного плана , что делает справедливой необходимую часть критерия оптимальности);
2) неопорные компоненты , , делятся на две группы: одни из них принимают критические значения ( или ) в сочетании с определенным знаком оценок (см. (1.19)); вторая часть принимает некритические значения () с одновременным равенством нулю их оценок. При этом очевидно, что поскольку оценки зависят от плана, то любой малый сдвиг от точки сразу нарушит равенство нулю оценок компонент второй группы (некритических компонент), т.е. сразу будет нарушена третья группа соотношений из (1.19). Если при этом у компонент, принимающих критические значения, оценки ненулевые, то малый сдвиг от точки не изменит знаки этих оценок, т.е. при малом сдвиге две первые группы соотношений из (1.19) будут выполняться.
Таким образом, можно выделить, две группы оптимальных признаков плана задачи (1.1) - (1.3):
1) устойчивые признаки:
(3.1)
2) неустойчивые признаки:
(3.2)
На вышеизложенном анализе структуры оптимального плана задачи (1.1) - (1.3), на разделении оптимальных признаков на две группы (3.1) и (3.2) и базируются прямые методы решения этой задачи.
Направление улучшения плана в случае невыполнения соотношений оптимальности (1.19), т.е. в случае невыполнения оптимальных признаков (3.1), (3.2) подсказывает доказательство необходимой части критерия оптимальности.
Как и в случае полностью линейной задачи направлений улучшения плана (подходящих направлений) при решении задачи (1.1) - (1.3) можно предложить целое множество. Прежде всего, можно изменять только одну неопорную компоненту плана (элементарное направление) или одновременно изменять все неопорные его компоненты (неэлементарное направление). Поскольку при любом изменении плана изменяются оценки всех неопорных его компонент, то использование неэлементарных направлений будет более предпочтительным в линейно-квадратичной задаче.
Если для начального опорного плана оценки всех неопорных компонент не равны нулю, то, как и в линейной задаче, все неопорные компоненты плана можно направить к соответствующим границам ( или ) прямых ограничений (в соответствии со знаком ) в надежде, что знаки оценок не изменятся, и при шаге вдоль выбранного направления, равном единице, будут выполнены условия (1.19) критерия оптимальности с критическими значениями для " (устойчивые (3.1) и неустойчивые (3.2) признаки для критических значений ).
При этом нужно следить за знаками неопорных оценок, за уменьшением значения целевой функции.
Метод первого порядка и метод второго порядка различаются множествами накапливаемых оптимальных признаков и, в соответствии с этим - способами накопления этих признаков.
Метод первого порядка на своих итерациях накапливает только устойчивые признаки и индексы тех компонент, для которых потом нужно обеспечить выполнение неустойчивых признаков с помощью специальной завершающей процедуры доводки. Итерации этого метода делятся на два типа: на итерациях первого типа главной целью является уменьшение значения целевой функции и накопление устойчивых признаков; итерации второго типа уточняют структуру решения и улучшают данные для процедуры доводки.
Метод второго порядка постепенно накапливает все оптимальные признаки. Для удержания неустойчивых признаков (3.2) привлекается специальная конструкция - опора целевой функции. Таким образом, метод второго порядка (в отличие от метода первого порядка) кроме опоры ограничений использует также опору целевой функции.
Существует также двойственный метод. Этот метод удобно использовать для решения серии задач типа (1.1) - (1.3), каждая последующая из которых получается из предыдущей добавлением к системе основных ограничений одного или нескольких ограничений.
4. Два подхода к проблеме решения близких линейно-квадратичных задач
На практике часто встречаются линейно - квадратичные задачи близкие по своим параметрам. Такие задачи можно решать каждый раз с самого начала, используя прямой метод, но поскольку у нас стоит задача корректировки близких линейно - квадратичных задач, то можно откорректировать параметры близкой ей, уже решенной задачи, и решить задачу конечным двойственным методом. Известно, что самым быстрым и экономичным для этих целей является именно двойственный метод.
И так, для решения исходной задачи и корректировки близкой ей задачи будем строить программу конечного двойственного метода.
5. Использование программы DMQP
Программа DMQP - программа конечного двойственного метода линейно-квадратичного программирования.
Как и прежде рассматриваем задачу линейно - квадратичного программирования:
,
, ,
где
- двумерный массив основных ограничений размерности
, - вектор-столбец размерности
, и - нижнее и верхнее ограничениям на переменные,
- вектор-столбец размерности , соответствующий начальному плану задачи,
- количество основных ограничений задачи,
- количество переменных.
Программа корректировки решений близких задач линейно-квадратичного программирования написана на языке С.
Для решения задачи используем двойственный метод.
Программа конечного двойственного метода линейно-квадратичного программирования написана на языке фортран и скомпилирована в файл dmqp. exe.
Запуск этого файла осуществляется с помощью оператора System.
При этом формируются входной и выходной файлы.
Входной файл имеет следующую структуру:
В файле: - транспонированный двумерный массив , и соответственно равны и , - размер опоры ограничений начального согласованного опорного плана, - обратная матрица к опорной матрице, - размер опоры целевой функции начального согласованного опорного плана, - вектор-столбец, содержащий элементы верхнего треугольника матрицы, обратной к опорной матрице целевой функции, записанные по строчкам; - вектор-столбец размерности , который содержит следующую информацию: индексы опорных компонент начального плана, вошедшие в опору ограничений (их количество ); индексы опорных компонент начального плана, вошедшие в опору целевой функции (их количество ); индексы неопорных компонент начального плана (их количество ).
Выходной файл содержит следующую результирующую информацию:
значение параметра kod4. Если он равен нулю, то построен оптимальный план задачи;
размерность опоры ограничений;
опору ограничений;
размерность опоры целевой функции;
опору целевой функции;
неопорные индексы;
оптимальный план задачи;
Заключение
В данной курсовой работе была сформулирована линейно - квадратичная задача. Были сформулированы понятия плана, оптимального плана, субоптимального плана. Были сформулированы теорема о достаточном условии оптимальности, критерий управляемости основного ограничения, была выведена формула приращения целевой функции. На основании полученных сведений были доказаны критерий оптимальности и достаточное условие субоптимальности. Была сформулирована двойственная задача, произведена классификация методов решения линейно - квадратичных задач. Так же в курсовой работе было описано два подхода к проблеме решения близких линейно - квадратичных задач. Для решения линейно - квадратичной задачи был выбран двойственный метод, написана программа на языке С, которая его использует. В итоге была решена поставленная задача.
Список использованных источников
1. Габасов Р., Кириллова Ф.М. Методы линейного программирования. Ч.1 - 3. - Мн.: Изд-во БГУ, 1977, 1978, 1980.
2. Габасов Р., Кириллова Ф.М., Тятюшкин А.И. Конструктивные методы оптимизации. Ч.1. Линейные задачи. - Мн.: Изд-во БГУ, 1983.
3. Габасов Р., Кириллова Ф.М., Костюкова О.И., Ракецкий В.М. Конструктивные методы оптимизации. Часть 4. Выпуклые задачи. - Мн.: Изд-во Университетское, 1987.
4. Ракецкий В.М. Решение общей задачи выпуклого квадратичного программирования прямым методом. - Програм. Обеспечение ЭВМ / Ин-т математики АН БССР. Мн., 1985. Вып.55. - С.113 - 123.
5. Ракецкий В.М. Решение общей задачи выпуклого квадратичного программирования двойственным методом. - Програм. Обеспечение ЭВМ / Ин-т математики АН БССР. Мн., 1985. Вып.55. - С.124 - 129.
6. Лубочкин А.В. Методы решения выпуклых задач оптимального управления. - Дисс. … канд. физ. - мат. наук. - Мн.: БГУ, 1987.
7. Численные методы оптимизации. Ч.2. Линейные задачи оптимального управления. Практикум. - Гомель: ГГУ, 2001.
Приложения
Приложение А
Текст программы корректировки решений близких задач линейно-квадратичного программирования
# include <stdio. h>
# include <math. h>
# include <string. h>
# include <process. h>
# include <alloc. h>
# include <conio. h>
# include <bios. h>
#define N_M N-M
#define M 2
#define N 10
#define O 1.0
double A [M] [N],
B [M],
dn [N], dw [N],
eps1 = 0.00001, eps2=0.00001,P [M] [M], **Pr, Q [M] [M],
D [N_M] [N_M],
v [N_M], Ma [N_M] [N_M],
x [N],
y [M],
Del [N];
int i, j, k,
Jop [M],
Jn [N_M], kn,
Joc [N_M], koc,
Jnn [N_M], knn,
kod4;
double xr,
H [N_M] [N_M];
int kod,
nn,
UslSogl, UslOpt;
void main ();
void prosm (void);
void korect (void);
void obrabotka (void);
void callocPr (int);
void freePr (int);
void formParam (int);
void formElem (void);
void procsogl (int);
int gs (int, double**,
double*, int*);
int menu (int, char *nazv []);
char *nazv [] =
{"Обработка",
"Выход"
};
int menu (int kp, char *nazv [])
{ int i,k;
clrscr ();
for (i=0; i<kp; i++)
printf ("\n %d. %s", i+1,nazv [i]);
printf ("\n \n выберите пункт-->");
scanf ("%d",&k);
return k;
}
FILE *d;
FILE *r;
void prosm (void)
{
clrscr ();
printf ("\n матрица A: \n");
for (i=0; i<M; i++)
{printf ("\n");
for (j=0; j<N; j++)
printf (" %6.3f",A [i] [j]); }
printf ("\n вектор B: \n");
for (i=0; i<M; i++)
printf (" %7.3f",B [i]);
printf ("\n вектор dn: \n");
for (i=0; i<N; i++)
printf (" %5.2f",dn [i]);
printf ("\n вектор dw: \n");
for (i=0; i<N; i++)
printf (" %5.2f",dw [i]);
bioskey (0);
}
void korect (void)
{char *nazv [] ={ "Просмотр",
"Изменение B",
"Изменение dn",
"Изменение dw",
"Обработка"};
int nom,kp=5,s;
while (1)
{ clrscr ();
s=menu (kp,nazv);
switch (s)
{ case 1: prosm (); break;
case 2: {printf ("Введите эл-ты вектора\n");
for (i=0; i<M; i++)
{ printf (" B [%d] =", i);
scanf (" %lf",&B [i]); }}; break;
case 3: {printf ("Введите эл-ты вектора\n");
for (i=0; i<N; i++)
{ printf (" dn [%d] =", i);
scanf (" %lf",&dn [i]); }}; break;
case 4: {printf ("Введите эл-ты вектора\n");
for (i=0; i<N; i++)
{ printf (" dw [%d] =", i);
scanf (" %lf",&dw [i]); }}; break;
case 5: return;
default: {puts ("Не тот номер");
getchar ();; }
}
}
}
void callocPr (int n)
{
int i;
Pr = (double**) calloc (n, sizeof (double));
for (i=0; i<n; i++)
Pr [i] = (double*) calloc (n, sizeof (double));
}
void freePr (int n)
{
int i;
for (i=0; i<n; i++)
free (Pr [i]);
free (Pr);
}
void formElem (void)
{
int i, j, k,
kod,
PrOp,
jr;
Jop [0] =0;
Jop [1] =N-1;
kn = N - M;
k = 0;
for (j=0; j<N; j++)
{
PrOp = 0;
for (i=0; i<M; i++)
if (j==Jop [i])
{
PrOp = 1;
break;
}
if (! PrOp)
{
Jn [k] = j;
k++;
}
}
koc = 0;
knn = kn;
for (j=0; j<knn; j++)
Jnn [j] = Jn [j];
for (i=0; i<M; i++)
for (j=0; j<M; j++)
P [i] [j] = A [i] [Jop [j]];
callocPr (M);
for (j=0; j<M; j++)
{
for (i=0; i<M; i++)
{
for (k=0; k<M; k++)
Pr [i] [k] = P [i] [k];
v [i] = 0.0;
}
v [j] = 1.0;
gs (M, Pr, v, &kod);
if (kod)
{
printf ("\nОпорная матрица (ограничений) вырождена!!! \n");
getchar ();
}
for (i=0; i<M; i++)
Q [i] [j] = v [i];
}
freePr (M);
for (j=0; j<knn; j++)
x [Jnn [j]] = dn [Jnn [j]];
if (koc>0)
for (i=0; i<koc; i++)
x [Joc [i]] = v [i];
callocPr (M);
for (i=0; i<M; i++)
{
for (j=0; j<M; j++)
Pr [i] [j] = P [i] [j];
v [i] = B [i];
for (j=0; j<kn; j++)
v [i] - = A [i] [Jn [j]] * x [Jn [j]];
}
gs (M, Pr, v, &kod);
freePr (M);
if (kod)
{
printf ("\nОпорная матрица (ограничений) вырождена!!! \n");
getchar ();
}
for (i=0; i<M; i++)
x [Jop [i]] = v [i];
callocPr (M);
for (i=0; i<M; i++)
{
for (k=0; k<M; k++)
Pr [i] [k] = P [k] [i];
v [i] = x [Jop [i]];
}
gs (M, Pr, v, &kod);
freePr (M);
if (kod)
{
printf ("\nОпорная матрица (ограничений) вырождена!!! \n");
getchar ();
}
for (j=0; j<N; j++)
{
Del [j] = x [j];
for (i=0; i<M; i++)
Del [j] - = v [i] * A [i] [j];
}
} // formElem
void procsogl (int nz)
{
double l [N],
Qb [M],
Th, Thj;
int i, j, k,
kod,
iterS,
prTh,
j0;
iterS = 0;
while (1)
{
for (j=0; j<knn; j++)
if (Del [Jnn [j]] > eps1)
l [Jnn [j]] = dn [Jnn [j]] - x [Jnn [j]];
else
if (Del [Jnn [j]] < - eps1)
l [Jnn [j]] = dw [Jnn [j]] - x [Jnn [j]];
else
l [Jnn [j]] = 0.0;
if (koc>0)
{
callocPr (M);
for (j=0; j<koc; j++)
{
for (i=0; i<M; i++)
{
for (k=0; k<M; k++)
Pr [i] [k] = P [i] [k];
v [i] = A [i] [Joc [j]];
}
gs (M, Pr, v, &kod);
if (kod)
{
printf ("\nОпорная матрица (ограничений) вырождена!!! \n");
getchar ();
}
for (i=0; i<M; i++)
Ma [i] [j] = v [i];
}
freePr (M);
for (i=0; i<koc; i++)
for (j=0; j<koc; j++)
{
D [i] [j] = 0.0;
for (k=0; k<M; k++)
D [i] [j] += Ma [k] [i] * Ma [k] [j];
}
for (i=0; i<koc; i++)
D [i] [i] += 1.0;
callocPr (M);
for (i=0; i<M; i++)
{
for (k=0; k<M; k++)
Pr [i] [k] = P [i] [k];
Qb [i] = 0.0;
for (j=0; j<knn; j++)
Qb [i] += A [i] [Jnn [j]] * l [Jnn [j]];
}
gs (M, Pr, Qb, &kod);
freePr (M);
if (kod)
{
printf ("\nОпорная матрица (ограничений) вырождена!!! \n");
getchar ();
}
for (i=0; i<koc; i++)
{
v [i] = 0.0;
for (j=0; j<M; j++)
v [i] - = Ma [j] [i] * Qb [j];
}
callocPr (koc);
for (i=0; i<koc; i++)
for (k=0; k<koc; k++)
Pr [i] [k] = D [i] [k];
gs (koc, Pr, v, &kod);
freePr (koc);
if (kod)
{
printf ("\nОпорная матрица (цел. ф-ии) вырождена!!! \n");
getchar ();
}
}
for (j=0; j<koc; j++)
l [Joc [j]] = v [j];
callocPr (M);
for (i=0; i<M; i++)
{
for (j=0; j<M; j++)
Pr [i] [j] = P [i] [j];
v [i] = 0.0;
for (j=0; j<kn; j++)
v [i] - = A [i] [Jn [j]] * l [Jn [j]];
}
gs (M, Pr, v, &kod);
freePr (M);
if (kod)
{
printf ("\nОпорная матрица (ограничений) вырождена!!! \n");
getchar ();
}
for (j=0; j<M; j++)
l [Jop [j]] = v [j];
callocPr (M);
for (i=0; i<M; i++)
{
for (k=0; k<M; k++)
Pr [i] [k] = P [k] [i];
Qb [i] = l [Jop [i]];
}
gs (M, Pr, Qb, &kod);
freePr (M);
if (kod)
{
printf ("\nОпорная матрица (ограничений) вырождена!!! \n");
getchar ();
}
for (j=0; j<knn; j++)
{
v [j] = l [Jnn [j]];
for (i=0; i<M; i++)
v [j] - = Qb [i] * A [i] [Jnn [j]];
}
Th = 1;
prTh = - 1;
for (j=0; j<koc; j++)
if (l [Joc [j]] < - eps2)
{
Thj = (dn [Joc [j]] - x [Joc [j]]) / l [Joc [j]];
if (Thj < Th)
{
Th = Thj;
j0 = j;
prTh = 0;
}
}
else
if (l [Joc [j]] > eps2)
{
Thj = (dw [Joc [j]] - x [Joc [j]]) / l [Joc [j]];
if (Thj < Th)
{
Th = Thj;
j0 = j;
prTh = 0;
}
}
for (j=0; j<knn; j++)
if (Del [Jnn [j]] * v [j] < - eps1)
{
Thj = - Del [Jnn [j]] / v [j];
if (Thj < Th)
{
Th = Thj;
j0 = j;
prTh = 1;
}
}
for (j=0; j<nz; j++)
x [j] += Th*l [j];
if (Th == 1)
{
break;
}
else
if (prTh)
{
Joc [koc] = Jnn [j0];
koc++;
knn--;
for (i=j0; i<knn; i++)
Jnn [i] = Jnn [i+1];
}
else
{
Jnn [knn] = Joc [j0];
knn++;
koc--;
for (i=j0; i<koc; i++)
Joc [i] = Joc [i+1];
}
callocPr (M);
for (i=0; i<M; i++)
{
for (k=0; k<M; k++)
Pr [i] [k] = P [k] [i];
v [i] = x [Jop [i]];
}
gs (M, Pr, v, &kod);
freePr (M);
if (kod)
{
printf ("\nОпорная матрица (ограничений) вырождена!!! \n");
getchar ();
}
for (j=0; j<nz; j++)
{
Del [j] = x [j];
for (i=0; i<M; i++)
Del [j] - = v [i] * A [i] [j];
}
iterS++;
} // while (1)
}
int gs (int m, double **pX,
double copX [], int *kod)
{
double tol = 1E-5,bigpX, pXpX,
sav;
int i, j, k, ky, imax,
ix, jx, i0, ib;
for (j=0; j<m; j++)
{
bigpX = 0.;
for (i=j; i<m; i++)
{
pXpX = fabs (pX [i] [j]);
if (fabs (bigpX) < pXpX)
{
bigpX = pX [i] [j];
imax = i;
}
}
if (fabs (bigpX) <= tol)
{
*kod = 1;
return 1;
}
for (k=j; k<m; k++)
{
sav = pX [imax] [k];
pX [imax] [k] = pX [j] [k];
pX [j] [k] = sav / bigpX;
}
sav = copX [imax];
copX [imax] = copX [j];
copX [j] = sav / bigpX;
if (j==m-1)
break;
for (ix=j+1; ix < m; ix++)
{
for (jx=j+1; jx < m; jx++)
pX [ix] [jx] - = pX [ix] [j] * pX [j] [jx];
copX [ix] - = copX [j] * pX [ix] [j];
}
}
for (ky=0; ky < m-1; ky++)
{
ib = m-2-ky;
i0 = m-1;
for (k=0; k <= ky; k++)
{
copX [ib] - = pX [ib] [i0] * copX [i0];
i0--;
}
}
*kod=0;
return 0;
}
void formParam (int nz)
{
int i, j;
A [1] [0] =1.8;
A [0] [0] =30.78;
for (j=1; j<nz; j++)
{
A [1] [j] =1.8;
A [0] [j] =A [0] [j-1] - 3.24;
}
B [0] =70;
B [1] =0;
for (i=0; i<nz; i++)
{
dn [i] =-O;
dw [i] = O;
}
prosm ();
printf ("\n");
int t;
printf (" Если хотите изменить, то нажмите 1=");
scanf ("%d",&t);
if (t==1)
korect ();
} // formParam
void obrabotka (void)
{
clrscr ();
int nz=N;
formParam (nz);
formElem ();
UslSogl = 1;
for (j=0; j<knn; j++)
if ( ( (Del [Jnn [j]] < - eps1) &&
(fabs (x [Jnn [j]] - dn [Jnn [j]]) < eps2)) ||
( (Del [Jnn [j]] > eps1) &&
(fabs (x [Jnn [j]] - dw [Jnn [j]]) < eps2)))
{
UslSogl = 0;
break;
}
if (! UslSogl)
procsogl (nz);
UslOpt = 1;
for (j=0; j<M; j++)
if ( (x [Jop [j]] < dn [Jop [j]] - eps2) ||
(x [Jop [j]] > dw [Jop [j]] + eps2))
{
UslOpt = 0;
break;
}
if (UslOpt! = 0)
{clrscr ();
printf ("Псевдоплан оптимален!!!!");
bioskey (0); }
if (! UslOpt)
{
if ( (d = fopen ("dat", "wt")) == NULL)
{
perror ("dat");
exit (-1);
}
callocPr (koc);
for (j=0; j<koc; j++)
{
for (i=0; i<koc; i++)
{
for (k=0; k<koc; k++)
Pr [i] [k] = D [i] [k];
v [i] = 0.0;
}
v [j] = 1.0;
gs (koc, Pr, v, &kod);
if (kod)
{
printf ("\nОпорная матрица (цел. ф-ии) вырождена!!! \n");
getchar ();
}
for (i=0; i<koc; i++)
H [i] [j] = v [i];
}
freePr (koc);
fprintf (d, "%d %d\n", M, nz);
for (j=0; j<nz; j++)
{
for (i=0; i<M; i++)
fprintf (d, "%lf", A [i] [j]);
fprintf (d, "\n");
}
for (i=0; i<M; i++)
fprintf (d, "%lf", B [i]);
fprintf (d, "\n");
for (i=0; i<nz; i++)
fprintf (d, "%lf %lf\n", dn [i], dw [i]);
fprintf (d, "%d\n", M);
for (i=0; i<M; i++)
{
for (j=0; j<M; j++)
fprintf (d, "%lf", Q [i] [j]);
fprintf (d, "\n");
}
fprintf (d, "%d\n", koc);
for (j=0; j<koc; j++)
for (i=0; i<=j; i++)
fprintf (d, "%lf\n", H [i] [j]);
for (i=0; i<M; i++)
fprintf (d, "%d\n", Jop [i] + 1);
for (i=0; i<koc; i++)
fprintf (d, "%d\n", Joc [i] + 1);
for (i=0; i<knn; i++)
fprintf (d, "%d\n", Jnn [i] + 1);
for (j=0; j<nz; j++)
fprintf (d, "%lf\n", x [j]);
fclose (d);
system ("errfile. exe");
system ("dmqp. exe");
getchar ();
printf ("Результат: \n");
if ( (r = fopen ("res", "r")) == NULL)
{
perror ("res");
exit (-1);
}
fscanf (r, "%d", &kod4);
if (kod4==0)
{
printf ("Jop = (");
fscanf (r, "%d", &i);
nn = i;
for (j=0; j<i; j++)
{
fscanf (r, "%d", &k);
Jop [j] = k - 1;
printf ("%d", Jop [j]);
}
printf (") \n");
printf ("Joc = (");
fscanf (r, "%d", &i);
nn += i;
for (j=0; j<i; j++)
{
fscanf (r, "%d", &k);
Joc [j] = k - 1;
printf ("%d", Joc [j]);
}
printf (") \n");
printf ("Jnn = (");
for (j=0; j<nz-nn; j++)
{
fscanf (r, "%d", &k);
Jnn [j] = k - 1;
printf ("%d", Jnn [j]);
}
printf (") \n");
printf ("x = (");
for (k=0; k<nz; k++)
{
fscanf (r, "%lf", &xr);
x [k] = xr;
printf ("%7.3lf", x [k]);
}
printf (") \n");
getchar ();
}
fclose (r);
}
} // if (! UslOpt)
// }
void main (void)
{
int nom,kp=2,s;
textcolor (3);
while (1)
{ clrscr ();
s=menu (kp,nazv);
switch (s)
{
case 1: obrabotka (); break;
case 2: return;
default: { puts ("Смотри что вводишь");
getchar ();
}
}
}
}
Размещено на Allbest.ru
Подобные документы
Решение задачи минимизации среднеквадратичной интенсивности управления. Использование формулы Коши и приращения критерия качества. Применение программы конечного двойственного метода линейно квадратичного программирования. Выбор метода корректировки.
курсовая работа [262,0 K], добавлен 23.02.2016Изучение экстремальных задач и поиск их решений. Выбор метода решения и приведения задачи к каноническому виду и к задаче линейного программирования. Метод искусственного базиса. Модифицированный симплекс-метод. Написание программы на языке С++Builder 6.
курсовая работа [343,0 K], добавлен 28.11.2010Общее понятие и характеристика задачи линейного программирования. Решение транспортной задачи с помощью программы MS Excel. Рекомендации по решению задач оптимизации с помощью надстройки "Поиск решения". Двойственная задача линейного программирования.
дипломная работа [2,4 M], добавлен 20.11.2010Предмет, постановка и особенности задач дискретного программирования. Задачи с неделимостями и с разрывными целевыми функциями. Экстремальные комбинаторные задачи. Примеры решений задач дискретного программирования методом ветвей и границ, методом Гомори.
курсовая работа [211,3 K], добавлен 22.05.2013Характеристика параметрических методов решения задач линейного программирования: методы внутренней и внешней точки, комбинированные методы. Алгоритм метода барьерных поверхностей и штрафных функций, применяемых для решения задач большой размерности.
контрольная работа [59,8 K], добавлен 30.10.2014Практические навыки моделирования задач линейного программирования и их решения графическим и симплекс-методом с использованием прикладной программы SIMC. Моделирование транспортных задач и их решение методом потенциалов с помощью программы TRAN2.
контрольная работа [199,8 K], добавлен 15.06.2009Постановка задачи линейного программирования и формы ее записи. Понятие и методика нахождения оптимального решения. Порядок приведения задач к каноническому виду. Механизмы решения задач линейного программирования аналитическим и графическим способами.
методичка [366,8 K], добавлен 16.01.2010Изучение и укрепление на практике всех моментов графического метода решения задач линейного программирования о производстве журналов "Автомеханик" и "Инструмент". Построение математической модели. Решение задачи с помощью электронной таблицы Excel.
курсовая работа [663,9 K], добавлен 10.06.2014Анализ метода линейного программирования для решения оптимизационных управленческих задач. Графический метод решения задачи линейного программирования. Проверка оптимального решения в среде MS Excel с использованием программной надстройки "Поиск решения".
курсовая работа [2,2 M], добавлен 29.05.2015Оптимизационные исследования задач линейного и нелинейного программирования при заданных математических моделях. Решение задач линейного программирования и использование геометрической интерпретации и табличного симплекс-метода, транспортная задача.
курсовая работа [408,7 K], добавлен 13.06.2019
