Симплексный метод решения задач ЗЛП

Оглавление

Приложение B……………………………………………………………………23

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

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

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

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

Цель курсового проекта: решение задачи нахождения кратчайшего маршрута методами динамического программирования.

Задачи:

• Изучить основы линейного программирования;
• Изучить модифицированный симплекс-метод решения задач линейного программирования;
• Решить поставленную задачу модифицированным симплекс методом
• Реализовать решение поставленной задачи на ЭВМ.

1 Теоретическая  часть

1.1 Постановка задачи линейного  программирования

Линейное программирование — математическая дисциплина, посвящённая теории и методам решения экстремальных задач на множествах n-мерного векторного пространства, задаваемых системами линейных уравнений и неравенств. Называется программированием условно, не имея ничего общего с написанием машинного кода.

Линейное программирование является частным случаем выпуклого программирования, которое в свою очередь является частным случаем математического программирования. Одновременно оно — основа нескольких методов решения задач целочисленного и нелинейного программирования. Одним из обобщений линейного программирования является дробно-линейное программирование.

Многие свойства задач линейного программирования можно интерпретировать также как свойства многогранников и таким образом геометрически формулировать и доказывать их.

Термин «программирование» нужно понимать в смысле «планирования». Он был предложен в середине 1940-х годов Джорджем Данцигом, одним из основателей линейного программирования, ещё до того, как компьютеры были использованы для решения линейных задач оптимизации.

К числу задач линейного программирования можно отнести задачи:

• рационального использования сырья и материалов;
• задачи оптимального раскроя;
• оптимизации производственной программы предприятий;
• оптимального размещения и концентрации производства;
• составления оптимального плана перевозок, работы транспорта (транспортные задачи);
• управления производственными запасами;
• и многие другие, принадлежащие сфере оптимального планирования.

Линейное программирование является одной из основных частей того раздела современной математики, который получил название математического программирования. В общей постановке, задачи этого раздела выглядят следующим образом.

Требуется найти такие неотрицательные , которые обеспечивают максимум или минимум целевой функции (формула 1.1), которые удовлетворяют системе ограничений (формула 1.2) и не противоречат условиям неотрицательности:                       .

    (1.1)

               

                         (1.2)

                                 … … … … … … … … … …

                               

В зависимости от вида функции F(X) различают разделы математического программирования: квадратичное программирование, выпуклое программирование, целочисленное программирование и т.д. Линейное программирование характеризуется тем, что функция F(X) является линейной функцией переменных X1, X2, …, Xn. [1]

Формы задач линейного программирования:

1. стандартная;

1.1 первая  стандартная форма (формула 1.3);

                               (1.3)

… … … … … … … … … …

.

1.2 вторая  стандартная форма (формула 1.4);

                                (1.4)

… … … … … … … … … …

.

2. каноническая (формула 1.5).

                                (1.5)

… … … … … … … … …

.

Задачу на минимум (формула 1.6) можно решать как задачу на максимум. Достаточно знаки целевой функции поменять на противоположные (формула 1.7). В результате необходимо знак целевой функции поменять на противоположный.

                              (1.6)

                       (1.7)

Аналогично можно сменить знак неравенства меньше или равно (формула 1.8) на больше или равно (формула 1.9).

                           (1.8)

                     (1.9)

Целевая функция задачи линейного программирования достигает своего экстремума (минимума или максимума) в вершине допустимой области. Если целевая функция достигает экстремального значения более чем на одной вершине, то она достигает того же значения в любой точке, являющейся выпуклой комбинацией этих вершин (альтернативный оптимум). [6]

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

Любой набор чисел                       , удовлетворяющий ограничениям задачи, называют планом, а множество всех планов допустимой областью. Тот план, который доставляет экстремум (минимум или максимум) целевой функции, называют оптимальным планом или просто решением задачи линейного программирования. [13]

1.2 Модифицированный симплекс-метод решения задач линейного программирования

Для решения задач линейного программирования существует множество методов. Рассмотрим один из них улучшенный (модифицированный) симплекс-метод

Для начала расскажем, что такое симплекс-метод. Слово SIMPLEX в обычном смысле означает простой, несоставной, в противоположность слову COMPLEX.

Данный метод получил несколько различных форм (модификаций) и был разработан в 1947 году Г. Данцигом.

Сущность симплекс-метода заключается в том, что если число неизвестных больше числа уравнений, то данная система неопределенная с бесчисленным множеством решений. Для решения системы все неизвестные произвольно подразделяют на базисные и свободные. Число базисных переменных определяется числом линейно-независимых уравнений. Остальные неизвестные свободные. Им придают произвольные значения и подставляют в систему. Любому набору свободных неизвестных можно придать бесчисленное множество произвольных значений, которые дадут бесчисленное множество решений. Если все свободные неизвестные приравнять к нулю, то решение будет состоять из значений базисных неизвестных. Такое решение называется базисным. [7]

В теории линейного программирования существует теорема, которая утверждает, что среди базисных решений системы можно найти оптимальное, а в некоторых случаях и несколько оптимальных решений, но все они обеспечат экстремум целевой функции. Таким образом, если найти какой-либо базисный план, а затем улучшить его, то получится оптимальное решение. На этом принципе и построен симплекс-метод. [17]

Одним из модификаций симплекс-метода является улучшенный симплекс-метод. В литературе этот метод встречается также под названием метода обратной матрицы или модифицированного симплекс-метода.

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

В улучшенном симплекс-методе реализуется та же основная идея, что и в обычном симплекс-методе, но здесь на каждой итерации пересчитывается не вся матрица A-1, обратная матрице ограничений A, а лишь та часть, которая относится к текущему базису Ax. [15]

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

1. В начале первого цикла нам известны обратная матрица A-1;x (единичная матрица), базисное решение xb = A-1;x b.

2. Образуем для каждой небазисной переменной характеристическую разность Dj, используя уравнение:

Dj = cj — pi=1;n; i * Aij = cj — pPj ,                                (2)

где p - двойственные переменные, которые можно найти следующим образом:

p = cx * A-1;x ,                                              (2.1)

где cx - вектор коэффициентов целевой функции при базисных переменных.

3. Предполагая, что используется стандартное правило выбора вводимого столбца, находим:

DDminj   j = s .                                             (2.2)

4. Если Ds ³ 0 - процедура останавливается. Текущее базисное решение является оптимальным.

5. Если Ds £ 0, вычисляем преобразованный столбец:

P;—s = A-1;x Ps .                                            (2.3)

6.Пусть

P;—s = (a;-1s , a;-2s , ..., a;-ms ) .                                  (2.4)

Если все a;-is £ 0 - процедура останавливается: оптимум неограничен.

7. В противном случае находим выводимую из базиса переменную:

³xb r; a;-r s = mina;-rs  0 = q .                                       (2.5)

8. Строим увеличенную матрицу:

[ A-1;x :;:;: P;—s ,                                         (2.6)

и трансформируем ее с ведущим элементом a;-r s . Первые m столбцов дают матрицу, обратную новому базису.

9. Преобразуем базисное решение:

xb i Ü xb i — q * a;-is , i ¹ r,                             (2.7)

xb r Ü q ,                                         (2.8)

и переходим к этапу 2.

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

Для этого нужно:

1. Сохранять исходную запись задачи на протяжении всей работы метода, это та цена, которую приходится платить за больше быстродействие;
2. Использовать так называемые симплекс – множители π – коэффициенты для непосредственного перехода от исходной записи задачи к ее текущей канонической форме базиса;
3. Использовать обращенный базис В־¹ - матрицу размера m x m, позволяющую вычислять на каждом шаге ведущий столбец a΄s и обновлять симплекс – множители π.

Улучшенный симплекс-метод, обладает значительными преимуществами по сравнению со стандартной формой. Это относится к точности, скорости и требованиям к памяти. Большая часть этих преимуществ определяется тем фактором, что, как правило, матрицы больших линейных задач (то есть с n>m>100) являются слабо заполненными, содержат малый процент ненулевых элементов.

Обычной является плотность 5% или менее. Улучшенная форма симплекс-метода в большей степени способна использовать преимущества, вытекающие из этого факта. В этой форме характеристические разности и ведущий вектор вычисляются непосредственно по исходным данным. Поскольку исходная матрица слабо заполнена, а перемножение следует производить только тогда, когда оба сомножителя отличны от нуля, то время вычислений значительно сокращается. [9]

В дополнение к этому использование только исходных данных приводит к тому, что уменьшается возможность накопления ошибок округления. Наоборот, стандартные симплексные таблицы, даже если они первоначально являются слабо заполненными, в ходе итеративного процесса быстро заполняются ненулевыми элементами. Таким образом, время вычислений увеличивается, и, поскольку каждая таблица вычисляется из предшествующей, накопление ошибок может начать играть более серьезную роль. [15]

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2. Практическое  применение модифицированного симплекс-метода для решения задачи линейного программирования

Задание: Решить задачу модифицированным симплекс-методом.