Министерство образования Российской Федерации
Тольяттинский ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
Кафедра «Автоматизация машиностроения»
Методы оптимизации.
Линейное программирование (ЛП).
Симплекс – метод решения задач ЛП.
Учебное пособие по дисциплине
«Основы САПР»
Тольятти 2003
УДК 002
Методы оптимизации. Линейное программирование (ЛП). Симплекс метод решения задач ЛП: Учебное пособие по дисциплине «Основы САПР»/ сост. Пиастро Г.П., Атлягузова Е.И., Коротыч В.И. - Тольятти: ТГУ, 2003.
Рассматривается математическая модель задачи линейного программирования, в том числе различные формы ее представления. Приводится графическая интерпретация задачи линейного программирования на плоскости и графический способ решения. Выполнен интуитивно - понятный анализ процедуры аналитического решения задачи линейного программирования. Излагается прямой алгоритм симплекс-метода и его графическая иллюстрация, а также прямой алгоритм с искусственными переменными.
Составители: Пиастро Г.П., Атлягузова Е.И., Коротыч В.И.
Научный редактор: Ройтбург Ю.С.
(с) Тольяттинский Государственный Университет, 2003
ОГЛАВЛЕНИЕ.
ВВЕДЕНИЕ. 4
1. Геометрическая интерпретация задачи. Анализ вариантов решений. 6
9
2. КАНОНИЧЕСКАЯ ФОРМА ПРЕДСТАВЛЕНИЯ ОГРАНИЧЕНИЙ. ДОПУСТИМЫЕ БАЗИСНЫЕ РЕШЕНИЯ. 10
3.СИМПЛЕКС-МЕТОД. АНАЛИЗ ПРОЦЕДУРЫ РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ (С ПРИМЕРОМ). 12
4. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ. 15
5. Прямой алгоритм симплексного метода 21
6. Прямой алгоритм с искусственными переменными 28
ВВЕДЕНИЕ.
Задача повышения эффективности технологических и организационных систем (например: металлорежущего станка, автоматической линии, производства в целом) путём принятия обоснованных решений актуальна во всех областях деятельности человека. Количественная оценка эффективности может быть получена при заданной цели функционирования системы, с учётом ограничений на ресурсы, привлекаемые для достижения цели. При этом задача принятия решения ставится как задача выбора параметров системы, обеспечивающих максимизацию или минимизацию целевой функции. Последняя количественно определяет степень достижения цели – величину критерия оптимизации. В качестве критерия можно принять, например, себестоимость изделия (цель-минимизация), быстродействие машины или прибора (цель-максимизация) и другие показатели.
Обоснованное применение количественных методов для принятия решений - оптимизацию поведения структур систем называют исследованием операций (ИСО). Здесь операция – комплекс целенаправленных действий.
Задача, рассмотренная выше, решается с применением математической модели системы, объединяющей упомянутые ограничения на ресурсы и целевую функцию. Нахождение величин упомянутых параметров системы (они входят в математическую модель как неизвестные) путём решения математической задачи называют математическим программированием. Математическое программирование – важнейшая область математики, ориентированная на широкое применение компьютеров. Одним из разделов этой области является линейное программирование.
В моделях линейного программирования так называемая «основная задача» состоит в нахождении неотрицательного решения системы линейных уравнений или неравенств (ограничений), которая минимизирует или максимизирует линейную форму (целевую функцию). Математическая задача линейного программирования записывается в сокращённом виде следующим образом:
найти
при ограничениях типа:
(0.1)
которые минимизируют (или максимизируют) линейную форму – целевую функцию:
(0.2)