Реферат на тему Симплекс-метод решения задач линейного программирования

Содержание:

Введение 3
1. Методы проведения исследований 3
2. Методы анализа исходных данных 5
3. Основные теоретические модели принятия экономических решений 8
4. Методы анализа построенных формализованных моделей 12
5. Основные алгоритмические и программные средства реализации процедур решения возникающих математических задач 14
Заключение 17
Список литературы 17

Введение:

Во многих областях производственно-экономической деятельности возникает необходимость в решении задач для определения максимального эффекта при заданных ограничениях на различные виды ресурсов [1]. Ввиду сложности современных объектов исследования для их модельного описания используются различные подходы, например – линейное программирование, частью которого являются транспортные задачи.
В классическом варианте они ассоциируются с перемещением груза от поставщиков к потребителям. Решение данной задачи позволяет разработать наиболее рациональные пути и способы транспортирования товаров, устранить чрезмерно дальние, встречные, повторные перевозки. Всё это уменьшает стоимость доставки товаров, связанные с осуществлением процессов снабжения материалами, сырьём, оборудованием, топливом и т.д.
Тем не менее алгоритмы и методы решения транспортной задачи могут быть использованы при рассмотрении других типов задач, не относящихся к классу объектов транспортировки груза, например, сетевое, календарное планирование, составление расписания, оптимальное обеспечение материальными ресурсами предприятия, распределение торговых агентов и т.д.
Известно, что при использовании методов линейного программирования необходимо выполнять многочисленные последовательные арифметические операции, причем ошибка на любом этапе решения приводит к неверному конечному результату, а повторные вычисления зачастую занимают много времени.
Цель работы – рассмотреть симплекс-метод решения задач линейного программирования.  

Заключение:

Математическое программирование помогло найти оптимальный план производства, который полностью использует ресурсы и выпускает продукцию с максимальным эффектом.
Доказано, что если оптимальное решение существует, то оно обязательно будет найдено через конечное число итераций (шагов), кроме случаев «зацикливания».
Модели принятия решений характеризуются методами, которые можно отнести к одному из трех типов:
1. Классическая модель,
2. Административная модель,
3. Политическая модель.
Модели принятия решений выбираются в соответствии с личными предпочтениями менеджеров. Также выбор зависит от того, запрограммированными или незапрограммированными являются принимаемые решения.
Модели принятия решения также основаны на степени риска, недостоверности или неопределенности.
Симплекс-метод основан на переходе от одного опорного плана к другому, при котором значение целевой функции возрастает.
Симплекс-метод – это алгоритм, используемый при решении оптимизационной задачи линейного программирования.

Фрагмент текста работы:

1. Методы проведения исследований
Математическое программирование помогает определить лучшее решение из предложенных. Решение задач математического программирования сводятся к решению задачи линейного программирования. Задачи математического программирования математические загадки, ответом на которые является оптимальное использование ресурсов для получения максимальной прибыли.
Существует три способа решения задач линейного программирования: простой и направленный переборы, симплекс метод. Каноническая форма задачи линейного программирования представлена на рисунке 1.

Рисунок 1 — Каноническая форма задачи линейного программирования
Таким образом, математическое программирование помогло найти оптимальный план производства, который полностью использует ресурсы и выпускает продукцию с максимальным эффектом.
 
2. Методы анализа исходных данных
Симплекс-метод основан на переходе от одного опорного плана к другому, при котором значение целевой функции возрастает.
Алгоритм симплекс-метода следующий:
Исходную задачу переводим в канонический вид путем введения дополнительных переменных. Для неравенства вида ≤ дополнительные переменные вводят со знаком (+), если же вида ≥ то со знаком (—). В целевую функцию дополнительные переменные вводят с соответствующими знаками с коэффициентом, равным 0, т.к. целевая функция не должна при этом менять свой экономический смысл.
Выписываются вектора Pi из коэффициентов при переменных и столбца свободных членов. Этим действием определяется количество единичных векторов. Правило – единичных векторов должно быть столько, сколько неравенств в системе ограничений.