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

Содержание


Введение 3
1. Истоки симплексного метода и его суть 4
2. Алгоритм симплекс-метода 6
3. Двухфазный симплекс-метод 7
Заключение 12
Список используемой литературы 13

Введение

Методы линейного программирования являются весьма эффективными для решения некоторых задач из области исследования операций. Линейное программирование – это наука о методах исследования и отыскания наибольших и наименьших значений линейной функции, на неизвестные которой наложены линейные ограничения.
С тех пор они нашли широкое применение в промышленности, торговле и управлении – как в местных, так и в государственных масштабах. Этими методами можно решить многие задачи, связанные с эффективным использованием ограниченных ресурсов.
Доказано, что оптимальное решение задачи линейного программирования связано с угловыми точками многоугольника решений, то есть с опорными планами. Они определяются системой m – линейно независимых векторов, содержащихся в системе из n – векторов. Количество опорных планов меньше, где n – число неизвестных, а m – число ограничений. При больших n и m найти все их перебором очень трудно, поэтому необходимо упорядоченный перебор, такой схемой является симплексный метод, который позволяет исходя из известного опорного плана задачи, за конечное число шагов получить её оптимальный план. Каждый из шагов (итераций) состоит в нахождении нового плана, которому соответствует меньшее для задачи на минимум (большее для задачи на максимум) значение линейной формы, чем её значение в предыдущем плане. Процесс продолжается до получения оптимального плана задачи (План, при котором целевая функция канонической задачи принимает свое максимальное (минимальное) значение, называется оптимальным). Если задача не обладает планами или её линейная форма неограниченна на многограннике решений, то симплексный метод позволяет установить это в процессе решения.
Цель работы – изучить симплекс-метод в линейном программировании.
1. Истоки симплексного метода и его суть

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