Аналитические методы решения задач линейного программирования

РОССИЙСКИЙ ГОСУДАРСТВЕННЫЙ 
СОЦИАЛЬНЫЙ УНИВЕРСИТЕТ 
КАФЕДРА ВЫСШЕЙ МАТЕМАТИКИ

 

 

 

 

 

 

 

 

 

 

 

АНАЛИТИЧЕСКИЕ МЕТОДЫ 
РЕШЕНИЯ ЗАДАЧ 
ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

 

 

 

 

 

 

 

Курсовая работа

студента заочного отделения 3 курса

специальности «Прикладная информатика 
в экономике»

 

Научный руководитель

кандидат экономических  наук, доцент

 

 

 

 

 

 

г. Москва

2011

ОГЛАВЛЕНИЕ

 

 

Введение 3

I. Решение задачи линейного  программирования графическим методом 3

II. Решение задачи линейного  программирования симплекс-методом 6

Заключение 11

 

Введение.

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

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

I. Решение задачи линейного программирования графическим методом.

Покажем решение задачи линейного  программирования графическим методом  на примере конкретной задачи (вариант 7):

При решении будем следовать алгоритму построения оптимального решения.

Решение:

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

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

Итак, строим на плоскости граничные прямые и полуплоскости, соответствующие заданной системе неравенств

и условию неотрицательности  . Направление полуплоскостей обозначим штриховкой.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

2. Построим вектор-градиент .

Построим прямую , проходящую через начало координат перпендикулярно вектору .

Будем перемещать прямую параллельно в направлении области допустимых решений. Первое пересечение с ОДР будет в точке , которая соответствует минимуму целевой функции, а последнее – в точке , которая соответствует максимуму функции.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

Ответ: при .

II. Решение задачи линейного программирования симплекс-методом.

Решение задачи линейного программирования симплекс методом так же покажем  на примере конкретной экономической  задачи (вариант 7), для чего составим математическую модель задачи и найдём её оптимальное решение симплекс методом.

Задача: Для приобретения оборудования, размещаемого на производственной площади 32 , фирма выделяет 24 тыс. у.е. Имеются единицы оборудования двух типов: оборудование типа А стоимостью 3 тыс. у.е., требующее производственную площадь 8 и имеющее производительность 4 тыс. единиц продукции за смену, и типа Б стоимостью 6 тыс. у.е., занимающее производственную площадь 5 и имеющее производительность 5 тыс. единиц продукции за смену.

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

Решение:

Пусть – количество оборудования типа А, а – количество оборудования типа Б. Целевая функция будет иметь вид:

 при ограничениях:

Так же из условия задачи следует, что  .

Для решения задачи симплекс методом  приведём полученную систему неравенств к каноническому виду. Для этого  обратим неравенства в равенства, введя в каждое из них соответствующую неотрицательную балансовую (или выравнивающую) переменную. Так как неравенства имеют знак , балансовые переменные вводятся со знаком +. В результате получим систему уравнений:

Все переменные подчинены условию неотрицательности:

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

Шаг 1.1. Для нашей системы ограничений базисными переменными (БП) являются а свободными переменными (СП) – .

Шаг 1.2. Из полученной ранее системы уравнений выразим БП через СП:

Шаг 1.3. Положив СП равными нулю, найдём допустимое базисное решение .

Шаг 1.4. При выбранном базисном решении вычислим значение целевой функции .

Шаг 1.5. Проверим, доставляет ли выбранное базисное решение максимум целевой функции . Для этого воспользуемся критерием оптимальности решения при нахождении максимума линейной функции:

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

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

Шаг 1.6. В соответствии с основным правилом перехода к лучшему решению:

«в новый состав базисных переменных вводится та свободная переменная, которая имеет наибольший положительный коэффициент в целевой функции»

введём в новый состав БП переменную . Для определения того, какая из старых БП перейдёт в разряд СП, нужно определить, при каких значениях каждая из старых БП останется неотрицательной. Т.е. необходимо выполнение следующих неравенств:

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

При переменная в системе выше обратиться в нуль, т.е. перейдёт в разряд СП.

Шаг 2.1. Новыми БП являются а СП – .

Шаг 2.2. Из полученной ранее системы уравнений выразим БП через СП:

После необходимых преобразований:

система примет вид:

Шаг 2.3. Положив СП равными нулю, найдём допустимое базисное решение .

Шаг 2.4. Выразим целевую функцию через СП и определим её значение при базисном решении :

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

Шаг 2.6. В соответствии с основным правилом перехода к лучшему решению введём в новый состав БП переменную . Для определения того, какая из старых БП перейдёт в разряд СП, нужно определить, при каких значениях каждая из старых БП останется неотрицательной. Т.е. необходимо выполнение следующих неравенств:

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

При переменная в системе выше обратиться в нуль, т.е. перейдёт в разряд СП.

Шаг 3.1. Новыми БП являются а СП – .

Шаг 3.2. Из полученной ранее системы уравнений выразим БП через СП:

После необходимых преобразований:

система примет вид:

Шаг 3.3. Положив СП равными нулю, найдём допустимое базисное решение .

Шаг 3.4. Выразим целевую функцию через СП и определим её значение при базисном решении :

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

Ответ: , .

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

Найдём эти переменные.

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

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

1. , неизвестен;

2. , неизвестен.

Проанализируем каждый случай для системы неравенств

и вычислим заданную функцию  для них.

Вариант 1:

Вариант 2:

Так как функция  , то запишем окончательный ответ:

Ответ: .

Заключение:

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

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

Список литературы:

1. Г.С. Жукова. Математическое моделирование  социально-экономических процессов.  Учебное пособие, Москва, 2008