Учебная работа № 341479. Тема: Методы искусственного базиса в симплекс — алгаритме
[Тип работы: Курсовая практическая
Предмет: Математика
Страниц: 20
стр.
ВВЕДЕНИЕ 3
§1. Симплекс-метод решения задачи линейного программирования 4
§2. Нахождение начального решения 5
§3. Модификации симплекс-метода 7
§4. Метод искусственного базиса 10
ЗАКЛЮЧЕНИЕ 19
СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ 20
Учебная работа № 341479. Тема: Методы искусственного базиса в симплекс — алгаритме
Выдержка из похожей работы
Основы симплес метода
…….ограммирование
Линейное
программирование — математическая
дисциплина, посвящённая теории и методам
решения экстремальных задач на множествах
n-мерного векторного пространства,
задаваемых системами линейных уравнений
и неравенств.
Линейное
программирование является частным
случаем выпуклого программирования,
которое в свою очередь является частным
случаем математического программирования.
Одновременно оно — основа нескольких
методов решения задач целочисленного
и нелинейного программирования. Одним
из обобщений линейного программирования
является дробно-линейное программирование.
Многие
свойства задач линейного программирования
можно интерпретировать также как
свойства многогранников и таким образом
геометрически формулировать и доказывать
их.
Термин
«программирование» нужно понимать в
смысле «планирования». Он был предложен
в середине 1940-х годов Джорджем Данцигом,
одним из основателей линейного
программирования, ещё до того, как
компьютеры были использованы для решения
линейных задач оптимизации.
В самом общем
виде задачу линейного программирования
можно записать так:
Основы
симплекс-метода
Симплекс-метод
был разработан и впервые применен для
решения задач в 1947 г. американским
математиком Дж. Данцигом.
Симплексный
метод в отличие от геометрического
универсален. С его помощью можно решить
любую задачу линейного программирования.
В основу
симплексного метода положена идея
последовательного улучшения получаемого
решения.
Геометрический
смысл симплексного метода состоит в
последовательном переходе от одной
вершины многогранника ограничений к
соседней, в которой целевая функция
принимает лучшее (или, по крайней мере,
не худшее) значение до тех пор, пока не
будет найдено оптимальное решение —
вершина, где достигается оптимальное
значение функции цели (если задача имеет
конечный оптимум).
Таким образом,
имея систему ограничений, приведенную
к канонической форме (все функциональные
ограничения имеют вид равенств), находят
любое базисное решение этой системы,
заботясь только о том, чтобы найти его
как можно проще. Если первое же найденное
базисное решение оказалось допустимым,
то проверяют его на оптимальность. Если
оно не оптимально, то осуществляется
переход к другому, обязательно допустимому
базисному решению. Симплексный метод
гарантирует, что при этом новом решении
целевая функция, если и не достигнет
оптимума, то приблизится
…