Симплекс-метод 2

МИНИСТЕРСТВО ОБРАЗОВАНИЯ

РОССИЙСКОЙ ФЕДЕРАЦИИ

«МАТИ» — РОССИЙСКИЙ ГОСУДАРСТВЕННЫЙ

ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ им. К.Э. ЦИОЛКОВСКОГО

Кафедра «Моделирование систем и информационные технологии»

«СИМПЛЕКС-МЕТОД»

Преподаватель: Смирнов Н. Я.

Студент: Асосков А.В.

Группа: 14АСУ-3ДС-025

Вариант: 3

2010 г.

Часть 1. Введение

В последние годы в прикладной математике большое внимание уделяется новому классу задач оптимизации, заключающихся в нахождении в заданной области точек наибольшего или наименьшего значения некоторой функции, зависящей от большого числа переменных. Это так называемые задачи математического программирования, возникающие в самых разнообразных областях человеческой деятельности и прежде всего в экономических исследованиях, в практике планирования и организации производства. Изучение этого круга задач и методов их решения привело к созданию новой научной дисциплины, получившей позднее название линейного программирования. В конце 40-х годов американским математиком Дж. Данцигом был разработан эффективный метод решения данного класса задач – симплекс-метод. К задачам, решаемых этим методом в рамках математического программирования относятся такие типичные экономические задачи как «Определение наилучшего состава смеси», «Задача об оптимальном плане выпуска продукции», «Оптимизация межотраслевых потоков», « Задача о выборе производственной программы», «Транспортная задача», «Задача размещения», «Модель Неймана расширяющейся экономики» и другие. Решение таких задач дает большие выгоды как народному хозяйству в целом, так и отдельным его отраслям.

Решение задач математического программирования при помощи симплекс-метода традиционными способами требует затрат большого количества времени. В связи с бурным развитием компьютерной техники в последние десятилетия естественно было ожидать, что вычислительная мощность современных ЭВМ будет применена для решения указанного круга задач.

Симплекс метод – является универсальным методам, которым можно решить любую задачу линейного программирования.

Часть 2. Основная

Математическое описание метода.

Допустим, имеется система уравнений ограничений:

Допустим, требуется вывести из числа свободных переменных какую – либо переменную, например, х₂ и перевести ее в базисную, а в замен ее ввести в число свободных какую то базисную, например у₃ , т. е. х₂ ↔у₃ . Если проводить этот процесс математическим способом то, необходимо было бы переразрешать каждое уравнение в системе ограничений относительно новой свободной переменной, т. е. новое получившееся уравнение, в котором была произведена замена необходимо подставить во все остальные уравнения, а так же целевую функцию. Данная процедура является громоздкой, поэтому проще задачу решить с помощью определенного алгоритма и записывать все промежуточные результаты в таблицу. Чтобы этот алгоритм был проще и лучше запоминался необходимо произвести следующие преобразования:

Избавляемся от отрицательных коэффициентов, для этого принимаем

Данная форма записи уравнений называется стандартной.

СЧ	х1	х2	х3	х4
у1	b1	a11	a12	a13	a14
у2	b2	a21	a22	a23	a24
у3	b3	a31	a32	a33	a34
у4	b4	a41	a42	a43	a44
у5	b5	a51	a52	a53	a45

При пересечении разрешающей строки у₃ и разрешающего столбца х₂ получаем разрешающий элемент а_32.

Необходимо найти коэффициенты, которые получатся в разрешающей строке после обмена х₂ ↔ у_{3 .}

СЧ	х1	у3	х3	х4
у1
y2
x2
y4
y5

Алгоритм преобразования коэффициентов стандартной таблицы.

1. Разрешающий элемент заменяется на обратную ему величину.
2. Все остальные элементы разрешающей строки делятся на разрешающий элемент.
3. Все элементы разрешающего столбца, кроме самого разрешающего элемента делятся на разрешающий элемент и меняют знак.
4. Каждый из остальных элементов подвергается следующему преобразованию: к нему прибавляется произведение элементов, стоявшего в прежней разрешающе

   Внимание, отключите Adblock

   Вы посетили наш сайт со включенным блокировщиком рекламы!
   Ссылка для скачивания станет доступной сразу после отключения Adblock!

   Скачать