Задачи линейного программирования

Ведущим столбцом может быть назначен любой столбец матрицы, удовлетворяющий одному из условий:

• первый столбец, содержащий положительный элемент (кроме нуля) в строке (векторе) решений;
• столбец, содержащий наибольший положительный элемент в строке (векторе) решений;
• если столбец t удовлетворяет условию:

 при решении задач на максимум;

 при решении  задач на минимум,

причем – коэффициент целевой функции в столбце j и – коэффициент в столбце j выбранной строки i матрицы A.

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

Критерием останова алгоритма поиска решения будет:

• для поиска максимума целевой функции – все коэффициенты вектора решений или равны нулю или отрицательны.
• для поиска минимума целевой функции – все коэффициенты вектора решений или равны нулю, или положительны.

Двойственные ЗЛП

Определение двойственной ЗЛП

Рассмотрим ЗЛП в стандартной форме

(1)

 

ЗЛП

(2)

называется двойственной задачей по отношению к ЗЛП (1), рассмотренной выше.

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

Если в прямой ЗЛП задано нахождение максимального значения целевой функции, то в двойственной (или обратной) ЗЛП — нахождение минимума целевой функции. Правило составления обратной ЗЛП таково.

Вместо неизвестных величин x в прямой ЗЛП вводятся новые неизвестные переменные y, количество которых равно количеству выражений ограничений в прямой ЗЛП.

Количество выражений ограничений в обратной ЗЛП будет равно количеству неизвестных в целевой функции прямой ЗЛП.

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

Коэффициентами целевой функции обратной ЗЛП будут свободные члены выражений ограничений прямой ЗЛП.

Существует три разновидности двойственной задачи.

1. Симметричная  двойственная задача.

Симметричной двойственной задачей называется такая задача, в которой целевая функция содержит все переменные с коэффициентами, отличными от нуля; все уравнения и неравенства условий ограничений также содержат все переменные с коэффициентами, отличными от нуля; количество ограничении равно количеству переменных.

2. Несимметричная  двойственная задача.

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

3. Смешанная  двойственная задача.

Смешанная двойственная задача может иметь произвольную структуру математической модели (по отношению к симметричной и несимметричной задачам).

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

Основные теоремы двойственности

1. Основное неравенство двойственных задач. Если прямая (1) и двойственная (2) задачи линейного программирования имеют непустые допустимые множества, то для любых их допустимых решений x и y выполняется неравенство , то есть значение целевой функции прямой задачи не превышает значения целевой функции двойственной задачи.
2. Первая теорема двойственности. Если допустимые множества прямой (1) и двойственной (2) задач непусты, то они имеют оптимальные решения x* и y*, причем оптимальные значения целевых функций двух задач совпадают: . Аналогично, если для прямой ЗЛП отсутствует область допустимых решений, то двойственная ЗЛП не имеет решения.
3. Вторая теорема двойственности. Оптимальные решения x* и y* пары двойственных задач связаны между собой следующими равенствами:

 

4. Если одна из пары двойственных задач решена симплексным методом, то в исходной прямоугольной матрице A решенной задачи можно выделить квадратную подматрицу B, столбцы которой соответствуют базисным переменным оптимального решения. Тогда оптимальное решение двойственной задачи вычисляется по формуле где – вектор строка оптимального решения; – вектор-строка, координаты которой равны коэффициентам целевой функции исходной задачи при базисных переменных последней симплексной таблицы.

Решение задачи линейного программирования

Некоторая компания выпускает краску для внутренних и наружных работ из сырья двух типов: A1, A2. В таблице ниже представлены основные данные задачи.

	Расход сырья (в тоннах) на тонну краски		Максимально возможный ежедневный расход сырья
	для внутренних работ	для наружных работ
Сырье А1	4	6	24
Сырье А2	2	1	6
Доход (в $1000) на тонну краски	4	5

 

Директор, в связи с финансовыми проблемами, поставил два условия:

1. ограничить ежедневный выпуск краски для внутренних работ до 2 т;
2. ежедневное производство краски для внутренних работ не должно превышать более чем нa тонну аналогичный показатель производства краски для внешних работ.

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

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

Обозначим

за – ежедневный объем производства краски для наружных работ;

за – ежедневный объем производства краски для внутренних работ.

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

.

Из таблицы и условий директора находим ограничения:

 

Условия неотрицательности появились потому, что количество краски не может быть отрицательным значением.

Задача содержит всего две переменные, поэтому проще всего решить её графическим методом.

Рис. 2

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

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

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

 

находим, что наибольшее значение функция достигает при

 

Заключение

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

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

Список используемой литературы

1. Аттетков А.В. Введение в методы оптимизации: учеб. Пособие / А.В. Аттетков, В.С. Зарубин, А.Н. Канатников. – М.: Финансы и статистика; ИНФРА-М, 2008. – 272 с.: ил.
2. Агальцов В.П., Волдайская И.В. Математические методы в программировании: Учебник. – М.: ИД «ФОРУМ»: ИНФРА-М, 2006 – 224 с.: ил.
3. Палий И.А. Линейное программирование. Учебное пособие / И.А. Палий – М.: Эксмо, 2008. – 256 с.
4. Исследование операций в экономике: Учебное пособие для вузов / Н.Ш. Кремер, Б.А. Путко, И.М. Тришин, М.Н. Фридман; под ред. проф. Н.Ш. Кремера. - М.: ЮНИТИ, 2004. Гл. 1-6.
5. Партыка Т.Л., Попов И.И. Математические методы: Учебник – М.: ФОРУМ: ИНФРА-М, 2005. – 464 с.: ил.