Симплекс-метод 2 (стр. 1 из 3)
МИНИСТЕРСТВО ОБРАЗОВАНИЯ
РОССИЙСКОЙ ФЕДЕРАЦИИ
«МАТИ» — РОССИЙСКИЙ ГОСУДАРСТВЕННЫЙ
ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ им. К.Э. ЦИОЛКОВСКОГО
Кафедра «Моделирование систем и информационные технологии»
«СИМПЛЕКС-МЕТОД»
Преподаватель: Смирнов Н. Я.
Студент: Асосков А.В.
Группа: 14АСУ-3ДС-025
Вариант: 3
2010 г.
Часть 1. Введение
В последние годы в прикладной математике большое внимание уделяется новому классу задач оптимизации, заключающихся в нахождении в заданной области точек наибольшего или наименьшего значения некоторой функции, зависящей от большого числа переменных. Это так называемые задачи математического программирования, возникающие в самых разнообразных областях человеческой деятельности и прежде всего в экономических исследованиях, в практике планирования и организации производства. Изучение этого круга задач и методов их решения привело к созданию новой научной дисциплины, получившей позднее название линейного программирования. В конце 40-х годов американским математиком Дж. Данцигом был разработан эффективный метод решения данного класса задач – симплекс-метод. К задачам, решаемых этим методом в рамках математического программирования относятся такие типичные экономические задачи как «Определение наилучшего состава смеси», «Задача об оптимальном плане выпуска продукции», «Оптимизация межотраслевых потоков», « Задача о выборе производственной программы», «Транспортная задача», «Задача размещения», «Модель Неймана расширяющейся экономики» и другие. Решение таких задач дает большие выгоды как народному хозяйству в целом, так и отдельным его отраслям.
Решение задач математического программирования при помощи симплекс-метода традиционными способами требует затрат большого количества времени. В связи с бурным развитием компьютерной техники в последние десятилетия естественно было ожидать, что вычислительная мощность современных ЭВМ будет применена для решения указанного круга задач.
Симплекс метод – является универсальным методам, которым можно решить любую задачу линейного программирования.
Часть 2. Основная
Математическое описание метода.
Допустим, имеется система уравнений ограничений:
Допустим, требуется вывести из числа свободных переменных какую – либо переменную, например, х2 и перевести ее в базисную, а в замен ее ввести в число свободных какую то базисную, например у3, т. е. х2 ↔у3. Если проводить этот процесс математическим способом то, необходимо было бы переразрешать каждое уравнение в системе ограничений относительно новой свободной переменной, т. е. новое получившееся уравнение, в котором была произведена замена необходимо подставить во все остальные уравнения, а так же целевую функцию. Данная процедура является громоздкой, поэтому проще задачу решить с помощью определенного алгоритма и записывать все промежуточные результаты в таблицу. Чтобы этот алгоритм был проще и лучше запоминался необходимо произвести следующие преобразования:
Избавляемся от отрицательных коэффициентов, для этого принимаем
Данная форма записи уравнений называется стандартной.
| СЧ | х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 |
При пересечении разрешающей строки у3 и разрешающего столбца х2 получаем разрешающий элемент а32.
Необходимо найти коэффициенты, которые получатся в разрешающей строке после обмена х2 ↔ у3.
| СЧ | х1 | у3 | х3 | х4 | |
| у1 |  |  |  |  |  |
| y2 |  |  |  |  |  |
| x2 |  |  |  |  |  |
| y4 |  |  |  |  |  |
| y5 |  |  |  |  |  |
Алгоритм преобразования коэффициентов стандартной таблицы.
- Разрешающий элемент заменяется на обратную ему величину.
- Все остальные элементы разрешающей строки делятся на разрешающий элемент.
- Все элементы разрешающего столбца, кроме самого разрешающего элемента делятся на разрешающий элемент и меняют знак.
- Каждый из остальных элементов подвергается следующему преобразованию: к нему прибавляется произведение элементов, стоявшего в прежней разрешающей строке на том же месте по порядку (т. е. в том же столбце), на элемент стоящий в новом разрешающем столбце на соответствующем месте (т. е. в той же строке, что и рассчитываемый элемент).
При всей легкости данных вычислений более удобно все промежуточные расчеты писать в той же таблице.
Алгоритм преобразования xj↔ yiстандартной таблицы сводится к следующим операциям:
1. Выделить в таблице разрешающий элемент. Вычислить ее обратную величину
и записать в нижней части этой же ячейки, например в правом нижнем углу.2. Все элементы разрешающей строки, кроме самого разрешающего элемента умножить на
, результат записать в нижней части той же ячейки.3. Все элементы разрешающего столбца, кроме всего разрешающего элемента умножить на – a, записать в нижней части той же ячейки.
4. Подчеркнуть в разрешающей строке все верхние числа (прежние элементы) за исключением самого разрешающего элемента. А в разрешающем столбце все новые элементы, кроме самого разрешающего элемента.
5. Для каждого из элементов не принадлежащих ни к разрешающей строке, ни к разрешающему столбцу в нижней часть ячейки записать произведение выделенных чисел, стоящих в той же строке и в том же столбце, что и данный элемент.
6. Переписать таблицу, заменив:
· xjнаyi;
· элемент разрешающей строки и столбца, числами, стоящими в нижней части тех же ячеек;
· каждый из остальных элементов суммой чисел стоящей в верхней и нижней части той же ячейки.
В любой задаче ОЗЛП существует так же линейная функция L, которая в общем случае выглядит следующим образом:
Для решения ее табличным способом ее так же можно привести к стандартному виду.
Таким образом, в стандартной таблице появляется еще одна строка L. С ней производятся только такие же вычисления как со всеми остальными ячейками таблицы, строка L никогда не может быть разрешающей строкой. С помощью табличного алгоритма обмена переменных в управлениях ОЗЛП можно решить любую задачу линейного программирования или убедиться, что она не имеет решения.