Решение задачи нахождения минимума целевой функции
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
Введение
Современный этап развития человечества отличается тем, что на смену века энергетики приходит век информатики. Происходит интенсивное внедрение новых технологий во все сферы человеческой деятельности. Встает реальная проблема перехода в информационное общество, для которого приоритетным должно стать развитие образования. Изменяется и структура знаний в обществе. Все большее значение для практической жизни приобретают фундаментальные знания, способствующие творческому развитию личности. Важна и конструктивность приобретаемых знаний, умение их структурировать в соответствии с поставленной целью. На базе знаний формируются новые информационные ресурсы общества. Формирование и получение новых знаний должно базироваться на строгой методологии системного подхода, в рамках которого отдельное место занимает модельный подход. Возможности модельного подхода крайне многообразны как по используемым формальным моделям, так и по способам реализации методов моделирования. Физическое моделирование позволяет получить достоверные результаты для достаточно простых систем.
В настоящее время нельзя назвать область человеческой деятельности, в которой в той или иной степени не использовались бы методы моделирования. Особенно это относится к сфере управления различными системами, где основными являются процессы принятия решений на основе получаемой информации.
1. Постановка задачи
минимум целевая функция
Решить задачу нахождения минимума целевой функции для системы ограничений, заданной многоугольником решений в соответствии с вариантом №16 задания. Многоугольник решений представлен на рисунке 1:
Рисунок 1 - Многоугольник решений задачи
Система ограничений и целевая функция задачи представлены ниже:
Необходимо решить задачу, используя следующие методы:
Графический метод решения задач ЛП;
Алгебраический метод решения задач ЛП;
Симплекс-метод решения задач ЛП;
Метод отыскания допустимого решения задач ЛП;
Решение двойственной задачи ЛП;
Метод ветвей и границ решения целочисленных задач ЛП;
Метод Гомори решения целочисленных задач ЛП;
Метод Балаша решения булевских задач ЛП.
Сравнить результаты решения разными методами сделать соответствующие выводы по работе.
2. Графическое решение задачи линейного программирования
Графический метод решения задач линейного программирования применяется в тех случаях, когда число неизвестных не превышает трех. Удобен для качественного исследования свойств решений и применяется совместно с другими методами (алгебраическим, ветвей и границ и т. д.). Идея метода основана на графическом решении системы линейных неравенств.
Рис. 2 Графическое решение задачи ЛП
- точка минимума
Уравнение прямой проходящей через две точки A1 и A2 :
АВ: (0;1); (3;3)
ВС: (3;3); (4;1) : (4;1); (3;0) А: (1;0); (0;1)
ЦФ: (0;1); (5;2)
при ограничениях:
Решение задачи линейного программирования алгебраическим симплекс-методом
Применение алгебраического метода решения задачи требует обобщения представления задачи ЛП. Исходную систему ограничений, заданную в виде неравенств преобразуют к стандартной форме записи, когда ограничения заданы в виде равенств. Преобразование системы ограничений к стандартному виду включает в себя следующие этапы:
Преобразовать неравенства таким образом, чтобы слева находились переменные и свободные члены, а справа - 0 т.е. чтобы левая часть была больше или равной нулю;
Ввести дополнительные переменные, число которых равно числу неравенств в системе ограничений;
Введя дополнительные ограничения на неотрицательность добавленных переменных, заменить знаки неравенств на знаки строгих равенств.
При решении задачи ЛП алгебраическим методом добавляется условие: целевая функция должна стремиться к минимуму. Если данное условие не выполняется, необходимо соответствующим образом преобразовать целевую функцию (умножить на -1) и решать задачу минимизации. После того, как решение найдено, подставить значения переменных в исходную функцию и посчитать ее значение.
Решение задачи при использовании алгебраического метода считается оптимальным, когда значения всех , базисных переменных - неотрицательно, и коэффициенты при свободных переменных в уравнении целевой функции также неотрицательны. Если эти условия не выполняются, необходимо преобразовать систему неравенств, выражая одни переменные через другие (меняя свободные и базисные переменные) добиться выполнения вышеприведенных ограничений. Значение всех свободных переменных считается равным нулю.
Алгебраический метод решения задач линейного программирования является одним из самых эффективных методов при решении задач небольшой размерности вручную т.к. не требует большого числа арифметических вычислений. Машинная реализация этого метода сложнее, чем, например, для симплекс-метода, т.к. алгоритм решения алгебраическим методом является в какой то степени эвристическим и эффективность решения во многом зависит от личного опыта.
- свободных переменных
Шаг 1.
св.пер. - доп. набор
Из (2)
Анализ
Шаг 2.
св. пер.
Анализ
Шаг 3.
св. пе