Курсовая работа: Применение линейного программирования для решения экономических задач (оптимизация прибыли)

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

(1.6)

(1.7)

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

(1.8)

(1.9)

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

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

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

Задачи линейного программирования решаются несколькими методами:

1. графический метод;

2. симплексный метод;

3. двойственность в ЛП;

4.двойственный симплексный метод.

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

Графический метод довольно прост и нагляден. Он основан на геометрическом представлении допустимых решений задачи. Каждое из неравенств задачи ЛП определяет на координатной плоскости некоторую полуплоскость, а система неравенств в целом – пересечение соответствующих плоскостей. Множество точек пересечения данных полуплоскостей называется областью допустимых решений (ОДР). ОДР всегда представляет собой выпуклую фигуру, т.е. обладающую следующим свойством: если две точки А и В принадлежат этой фигуре, то и весь отрезок АВ принадлежит ей. ОДР графически может быть представлен выпуклым многоугольником, неограниченным выпуклой многоугольной областью, отрезком, лучом и т.д. В случае несовместности системы ограничений задачи ОДР является пустым множеством.

При поиске оптимального решения задач линейного программирования возможны следующие ситуации: существует единственное решение задачи, существует бесконечное множество решений (альтернативный оптимум); ЦФ не ограничена; область допустимых решений– единственная точка; задача не имеет решений. [3 c.55-57]

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

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

Переход от одного базиса к другому позволяет находить решения почти всех задач ЛП. Определив все крайние точки, можно вычислить значения целевой функции и найти оптимальное решение. Однако для больших значений m и n это практически невозможно. [1 c.15]

Алгоритм решения задачи ЛП табличным симплексом-методом состоит из следующих этапов:

1. рассчитывают и заполняют начальную симплекс-таблицу с допустимым единичным базисом, включая индексную строку.

2. находят разрешающий столбец;

3. находят разрешающую строку;

4. рассчитывают методом Жордано-Гаусса все параметры матрицы;

5. анализируют полученные данные в индексной строке.

Таблицы симплекс-метода необходимо строить до тех пор, пока не будет получен оптимальный план. План будет считаться оптимальным, если в последней индексной строке симплекс-таблицы будут только нули и положительные числа. [1 c.20-22]

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

Метод искусственного базисаприменяется при наличии в ограничении знаков “равно”, “больше либо равно”, “меньше либо равно” и является модификацией табличного метода. Решение системы производится путём ввода искусственных переменных со знаком, зависящим от типа оптимума, т.е. для исключения из базиса этих переменных последние вводятся в целевую функцию с большими отрицательными коэффициентами m, а в задачи минимизации - с положительными m. Таким образом, из исходной получается новая m - задача.