Министерство образования и науки Российской Федерации

ФГАОУ ВПО «Уральский федеральный университет -имени первого Президента России Б.Н.Ельцина»

Институт физической культуры, социального сервиса и туризма
Кафедра «Управление в сфере физической культуры и спорта»


РЕФЕРАТ

Тема «Линейное программирование. Метод Гаусса»
Выполнил:

Студент гр. ФК – 38011                                                  А.П. Упадышева
Проверил:

доц., канд. наук                                                                  Н.И. Корзников
Екатеринбург

2010

СОДЕРЖАНИЕ
     Введение...................................................................................................... 3

1.     Основы линейного программирования

1.1 Теоретические основы линейного программирования................... 4

1.2 Основные теоремы линейного программирования......................... 6

2. Типовые задачи, решаемые при помощи методов линейного программирования

2.1 Оптимальное использование ресурсов при производственном    

    планировании............................................................................................... 8

2.2 Транспортная задача...................................................................... 10

2.3 Геометрическое решение задач линейного программирования... 11

3. Симплекс-метод.................................................................................... 14

Заключение............................................................................................... 19

Список литературы.................................................................................. 21
ВВЕДЕНИЕ
В 1939 году Леонид Витальевич Канторович опубликовал работу «Математические методы организации и планирования производства», в которой сформулировал новый класс экстремальных задач с ограничениями и разработал эффективный метод их решения, таким образом были заложены основы линейного программирования.
1.     Основы линейного программирования
1.1 Теоретические основы линейного программирования
Линейное программирование – направление математики, изучающее методы решения экстремальных задач, которые характеризуются линейной зависимостью между переменными и линейным критерием оптимальности.

Несколько слов о самом термине линейное программирование. Он требует правильного понимания. В данном случае программирование - это, конечно, не составление программ для ЭВМ. Программирование здесь должно интерпретироваться как планирование, формирование планов, разработка программы действий.

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

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

·                   задача об оптимальном использовании ресурсов при производственном планировании;

·                   задача о смесях (планирование состава продукции);

·                   задача о нахождении оптимальной комбинации различных видов продукции для хранения на складах (управление товарно-материальными запасами или "задача о рюкзаке");

·                   транспортные задачи (анализ размещения предприятия, перемещение грузов).

Линейное программирование – наиболее разработанный и широко применяемый раздел математического программирования (кроме того, сюда относят: целочисленное, динамическое, нелинейное, параметрическое программирование). Это объясняется следующим:

·                   математические модели большого числа экономических задач линейны относительно искомых переменных;

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

·                   многие задачи линейного программирования, будучи решенными, нашли широкое применение;

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

Экономико-математическая модель любой задачи линейного программирования включает: целевую функцию, оптимальное значение которой (максимум или минимум) требуется отыскать; ограничения в виде системы линейных уравнений или неравенств; требование неотрицательности переменных.

В общем виде модель записывается следующим образом:

целевая функция:  = c1x1 + c2x2 + ... + cnxn → max(min);       (2.1)

       ограничения
:       a11x1 + a12x2 + ... + a1nxn {≤ = ≥} b1,

           
a21x1 + a22x2 + ... + a2nxn {≤ = ≥} b2,

           
...           

          
am1x1 + am2x2 + ...
+ amnxn {≤ = ≥} bm;        (2.2)

                                       требование неотрицательности: xj ≥ 0,       (2.3)

При этом aij, bi, cj (   ) - заданные постоянные величины.

Задача состоит в нахождении оптимального значения функции (2.1) при соблюдении ограничений (2.2) и (2.3).

Систему ограничений (2.2) называют функциональными ограничениями задачи, а ограничения (2.3) - прямыми.

Вектор , удовлетворяющий ограничениям (2.2) и (2.3), называется допустимым решением (планом) задачи линейного программирования. План , при котором функция (2.1) достигает своего максимального (минимального) значения, называется оптимальным.
1.2 Основные теоремы линейного программирования
Для обоснования методов решения задач линейного программирования сформулируем ряд важнейших теорем, опуская их аналитические доказательства. Уяснить смысл каждой из теорем поможет понятие о геометрической интерпретации решения ЗЛП, данное в предыдущем подразделе.

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

Любые m переменных системы m линейных уравнений с n переменными (m < n) называются основными, если определитель матрицы коэффициентов при них отличен от нуля. Тогда остальные m-n переменных называются неосновными (или свободными).

Базисным решением системы m линейных уравнений c n переменными (m < n) называется всякое ее решение, в котором все неосновные переменные имеют нулевые значения.

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

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

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

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

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

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

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

Предприятие выпускает n различных изделий. Для их производства требуется m различных видов ресурсов (сырья, материалов, рабочего времени и т.п.). Ресурсы ограничены, их запасы в планируемый период составляют, соответственно, b1, b2,..., bm условных единиц.

Известны также технологические коэффициенты aij, которые показывают, сколько единиц i-го ресурса требуется для производства единицы изделия j-го вида (   ).

Прибыль, получаемая предприятием при реализации изделия j-го вида, равна cj.

В планируемом периоде значения величин aij, bi и cj остаются постоянными.

Требуется составить такой план выпуска продукции, при реализации которого прибыль предприятия была бы наибольшей.

Далее приведем простой пример задачи такого класса.

Компания специализируется на выпуске хоккейных клюшек и наборов шахмат. Каждая клюшка приносит компании прибыль в размере $2, а каждый шахматный набор - в размере $4. На изготовление одной клюшки требуется четыре часа работы на участке A и два часа работы на участке B. Шахматный набор изготавливается с затратами шести часов на участке A, шести часов на участке B и одного часа на участке C. Доступная производственная мощность участка A составляет 120 н-часов в день, участка В - 72 н-часа и участка С - 10 н-часов.

Сколько клюшек и шахматных наборов должна выпускать компания ежедневно, чтобы получать максимальную прибыль?

Условия задач указанного класса часто представляют в табличной форме (см. таблицу 2.1).

Таблица 2.1 - Исходные данные задачи об использовании производственных ресурсов

Производственные участки	Затраты времени на единицу продукции, н-час		Доступный фонд времени, н-час	прибыль на единицу продукции, $
				клюшки	наборы шахмат
	клюшки	наборы шахмат
А	4	6	120	2	4
В	2	6	72
С	-	1	10

По данному условию сформулируем задачу линейного программирования.

Обозначим: x1 - количество выпускаемых ежедневно хоккейных клюшек, x2 - количество выпускаемых ежедневно шахматных наборов.

Формулировка ЗЛП:  = 2x1 + 4x2 → max;          

                     4x1 + 6x2 ≤ 120,

                      2x1 + 6x2 ≤ 72,

                      x2 ≤ 10;

    x1 ≥ 0,   x2 ≥ 0.   

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

Три поставщика одного и того же продукта располагают в планируемый период следующими его запасами: первый – 120 условных единиц, второй – 100 условных единиц, третий – 80 условных единиц. Этот продукт должен быть перевезен к трем потребителям, потребности которых равны 90, 90 и 120 условных единиц, соответственно.

Обычно начальные условия транспортной задачи записывают в так называемую транспортную таблицу (см. таблицу 2.3). В ячейках таблицы в левом верхнем углу записывают показатели затрат (расходы по доставке единицы продукта между соответствующими пунктами), под диагональю каждой ячейки размещается величина поставки xij (т.е. xij – количество единиц груза, которое будет перевезено от i-го поставщика j-му потребителю).



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

Сформулируем ЗЛП:  = 7x11 + 6x12 + 4x13 + 3x21 + 8x22 + 5x23 + 2x31 + 3x32 + 7x33 → min;         

x11 + x12 + x13 = 120,

         x21 + x22 + x23 = 100,

x31 + x32 + x33 = 80,

x11 + x21 + x31 = 90,

x12 + x22 + x32 = 90,

x13 + x23 + x33 = 120;

          

xij ≥ 0.
2.3 Геометрическое решение задач линейного программирования
Если система ограничений задачи линейного программирования представлена в виде системы линейных неравенств с двумя переменными, то такая задача может быть решена геометрически. Таким образом, данный метод решения ЗЛП имеет очень узкие рамки применения.

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

Геометрический (или графический) метод предполагает последовательное выполнение ряда шагов. Ниже представлен порядок решения задачи линейного программирования на основе ее геометрической интерпретации.

1. Сформулировать ЗЛП.

2. Построить на плоскости {х1, х2} прямые, уравнения которых получаются в результате замены в ограничениях знаков неравенств на знаки точных равенств.

3. Найти полуплоскости, определяемые каждым из ограничений задачи.

4. Найти область допустимых решений.

5. Построить прямую c1x1 + c2x2 = h, где h - любое положительное число, желательно такое, чтобы проведенная прямая проходила через многоугольник решений.

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

7. Определить координаты точки максимума (минимума) функции и вычислить значение функции в этой точке.

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

1. Выше уже приводилась формулировка задачи, здесь нам остается лишь повторить ее:  = 2x1 + 4x2 → max;  

4x1 +6x2 ≤ 120,

2x1 +6x2 ≤ 72,

x2 ≤ 10;
x1 ≥ 0,   x2 ≥ 0.
2. Теперь построим прямые, соответствующие каждому из функциональных ограничений задачи (см. рисунок 2.1). Эти прямые обозначены на рисунке (1), (2) и (3).



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

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

5. Прямая, соответствующая целевой функции, на рисунке представлена пунктирной линией.

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

7. Осталось вычислить координаты точки С. Она является точкой пересечения прямых (1) и (2). Решив совместно уравнения этих прямых, найдем: , . Подставляя найденные величины в целевую функцию, найдем ее значение в оптимальной точке .

Таким образом, для максимизации прибыли компании следует ежедневно выпускать 24 клюшки и 4 набора. Реализация такого плана обеспечит ежедневную прибыль в размере $64.

3. Симплекс-метод
Этот один из первых специализированных методов оптимизации, нацеленный на решение задач линейного программирования, в то время как методы простого и направленного перебора могут быть применены для решения практически любой задачи оптимизации. Симплекс-метод был предложен американцем Г. Данцигом в 1951 г. Основная его идея состоит в продвижении по выпуклому многограннику ограничений от вершины к вершине, при котором на каждом шаге значение целевой функции улучшается до тех пор, пока не будет достигнут оптимум. Разберем пример на основе данных таблицы.

	Кухни	Кофеварки	Самовары
Штамповка	20000	30000	12000
Отделка	30000	10000	10000
Сборка	20000	12000	8000
Объем выпуска	Х1	Х2	Х3
Удельная прибыль (на одно изделие)	15	12	14

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

Х1  ≥ 0 , Х2 ≥ 0 , Х3  ≥ 0 , (0)

Х1  / 200 + Х2 / 300 + Х3   / 120 ≤ 100 , (1)

Х1  / 300 + Х2 / 100 + Х3   / 100 ≤ 100 , (2)

Х1 / 200 ≤ 100 , (3)

Х2 / 120 ≤ 100 , (4)

Х3 / 80 ≤ 100 , (5)

F = 15 Х1 + 12 Х2  + 14 Х3 → max .

 Здесь:

(0) - обычное в экономике условие неотрицательности переменных,

(1) - ограничение по возможностям штамповки (выраженное для облегчения восприятия в процентах),

(2) - ограничение по возможностям отделки,

(3) - ограничение по сборке для кухонь,

(4) - то же для кофемолок,

(5) - то же для самоваров (как уже говорилось, все три вида изделий собираются на отдельных линиях).

Наконец, целевая функция F - общая прибыль предприятия.

F = 15 Х1 + 12 Х2  + 14 Х3 → max .

Х1  / 200 + Х2 / 300 + Х3   / 120 ≤ 100 ,

Х1  / 300 + Х2 / 100 + Х3   / 100 ≤ 100 ,

Х3 / 80 ≤ 100 .

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

 В соответствии с симплекс-методом введем т.н. "свободные переменные" Х4, Х5, Х6, соответствующие недоиспользованным мощностям, т.е. от системы неравенств перейдем к системе уравнений:

Х1  / 200 + Х2 / 300 + Х3   / 120 + Х4  = 100 ,

Х1  / 300 + Х2 / 100 + Х3   / 100 + Х5 = 100 ,

Х3 / 80 + Х6  = 100 ,

15 Х1 + 12 Х2  + 14 Х3   = F .

У этой системы имеется очевидное решение, соответствующее одной из вершин многогранника допустимых значений переменных:

Х1 = Х2  = Х3  = 0, Х4  = Х5 = Х6  = 100,  F = 0.
В терминах исходной задачи это означает, что ничего не надо выпускать. Такое решение приемлемо только на период летних отпусков.

 В соответствии с симплекс-методом выбираем переменную, которая входит в целевую функцию F с самым большим положительным коэффициентом. Это Х1.

 Сравниваем частные от деления свободных членов в первых трех уравнениях на коэффициенты при только что выбранной переменной Х1:

100 / (1/200) = 20000, 100 / (1/300) =30000, 100/0 = + ∞ .

Выбираем строку из системы уравнений, которой соответствует минимальное из всех положительных отношений. В рассматриваемом примере - это первая строка, которой соответствует отношение 20000.

Умножим первую строку на 200, чтобы получить Х1  с единичным коэффициентом:

Х1  + 2/3 Х2  + 2/1,2 Х3   + 200 Х4  = 20000 .

Затем умножим вновь полученную строку на (-1/300) и сложим со второй строкой, чтобы исключить член с Х1, получим

7/900 Х2  + 4/900 Х3  - 2/3 Х4 + Х5 = 100/3.

Ту же преобразованную первую строку умножим на (-15) и сложим со строкой, в правой части которой стоит F, получим:

2 Х2  - 11 Х3  - 3000 Х4  =   F - 300000.

В результате система уравнений преобразуется к виду, в котором переменная Х1  входит только в первое уравнение:

Х1  + 2/3 Х2  + 2/1,2 Х3   + 200 Х4  = 20000 ,

7/900 Х2  + 4/900 Х3  - 2/3 Х4 + Х5 = 100/3,

Х3 / 80 + Х6  = 100 ,

2 Х2  - 11 Х3  - 3000 Х4  = F - 300000.

Очевидно, у новой системы имеется улучшенное по сравнению с исходным решение, соответствующее другой вершине выпуклого многогранника в шестимерном пространстве:
Х1  = 20000, Х2  = Х3   = Х4  = 0, Х5 = 100/3, Х6   = 100, F = 300000.

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

 Повторим описанную выше операцию. В строке с F имеется еще один положительный коэффициент - при Х2 (если бы положительных коэффициентов было несколько - мы взяли бы максимальный из них). На основе коэффициентов при Х2 (а не при Х1, как в первый раз) образуем частные от деления соответствующих свободных членов на эти коэффициенты:

20000 / (2/3) = 30000, (100/3) / (7/900) = 30000/7, 100/0 = + ∞.

Таким образом, нужно выбрать вторую строку, для которой имеем наименьшее положительное отношение 30000/7. Вторую строку умножим на 900/7 (чтобы коэффициент при Х2  равнялся 1). Затем добавим обновленную строку ко всем строкам, содержащим Х2, предварительно умножив их на подходящие числа, т.е. такие, чтобы все коэффициенты при Х2 стали бы после сложения равны 0, за исключением коэффициента второй строки, который уже стал равняться 1. Получим систему уравнений:

Х1  + 9/7 Х3  + 1800/7 Х4   - 600/7 Х5  = 120000/7 ,

Х2  + 4/7 Х3  - 600/7 Х4 + 900/7 Х5 = 30000/7,

Х3 / 80 + Х6 = 100 ,

- 85/7 Х3  - 19800/7 Х4  - 1800/7 Х5  = F - 308571.

Поскольку все переменные неотрицательны, то из последнего уравнения следует, что прибыль F достигает своего максимального значения, равного 308571, при Х3  = Х4  = Х5  = 0. Из остальных уравнений следует, что при этом Х1  = 120000/7 = 17143, Х2  = 30000/7 = 4286, Х6  = 100. Поскольку в строке с F не осталось ни одного положительного коэффициента при переменных, то алгоритм симплекс-метода закончил свою работу, оптимальное решение найдено.
 Практические рекомендации таковы: надо выпустить 17143 кухни, вчетверо меньше, т.е. 4286, кофемолок, самоваров не выпускать вообще. При этом прибыль будет максимальной и равной 308571. Все производственное оборудование будет полностью загружено, за исключением линии по сборке самоваров.
ЗАКЛЮЧЕНИЕ
Экономико-математические модели и методы - ЭМММ представляют собой логический системный подход к решению проблемы управления. Схематически его можно изобразить так:



С точки зрения ЭМММ центральным моментом становится конструирование модели - абстрактного представления существующей проблемной ситуации. Обычно такая модель представляется в виде математического соотношения или графика.

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

Следует отметить определенную переоценку значимости экономико-математических моделей в реальной практике управления экономико-производственными системами. Это связано с непреодолимыми пока сложностями моделирования процессов в экономико-производственных системах из-за непрерывности изменений продукции, нерегулярности производства, внутренних дестабилизирующих факторов, нерегулярности снабжения, финансирования, сбыта и т.д.
Большинство этих факторов носит нестационарный характер, что фактически исключает возможность использования эконометрических моделей в планировании и управлении реальным производством.
СПИСОК ЛИТЕРАТУРЫ
1. Барсов А.С. Что такое линейное программирование

2. Орлов А.И. МЕНЕДЖМЕНТ: УЧЕБНИК

3. Юдин Д.Б., Гольштейн Е.Г. Линейное программирование. Теория, методы и приложения

4. http://www.alleng.ru/d/manag/man059.htm