Тема 5. Экономико-математические методы, применяемые в ЭА: линейное программирование

Цель: освоить метод линейного программирования, понимать линейное программирование как метод оптимального планирования хозяйственной деятельности. Иметь понятие о критерии оптимальности. Знать типы задач, решаемых методом линейного программирования, классификацию методов решения задач линейного программирования: универсальные методы, специальные методы. Уметь осуществить постановку экономической задачи линейного программирования. Знать геометрическую интерпретацию задачи линейного программирования; особенности метода и алгоритм анализа; Симплекс-метод; алгоритм симплекс-метода.

План

1. Линейное программирование как метод оптимального планирования хозяйственной деятельности.

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

3. Графический метод.

1. Линейное программирование как метод оптимального планирования хозяйственной деятельности

Управление хозяйственной деятельностью начинается с планирования. Различные варианты плана связаны с неодинаковыми материальными и трудовыми затратами, поэтому выбор наиболее оптимального из них во многом определяет конечные результаты. Его преимущество перед другими устанавливают с помощью критерия оптимальности F. Для промышленных и с\х предприятий оптимальным считается план, обеспечивающий выпуск заданного объема продукции при минимальных затратах, а также получение максимальной прибыли при ограниченном объеме ресурсов.

Критерий оптимальности F(x) называют функцией плана, а сравниваемые варианты планов (x) – аргументами этой функции. Выбор оптимального плана можно рассматривать как математическую задачу максимизации (минимизации) значения целевой функции. Один из математических методов нахождения экстремума функции, аргументы которой выбираются из ограниченной области допустимых значений это линейное программирование.

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

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

§ Задача о раскрое, т.е. как с наименьшими отходами использовать материал при заданном количестве изделий;

§ Задача диеты (смеси), т.е. оптимальные рационы кормления;

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

§ Определение оптимального ассортимента, т.е. определение плана выпуска изделий, при котором суммарные показатели эффективности принимают наибольшее значение;

§ Задача о назначении, т.е. как распределить рабочих по станкам для максимизации прибыли;

§ Создание оптимального портфеля ценных бумаг;

§ Оптимальное распределение ресурсов КБ.

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

§ Универсальные методы, позволяющие решать практически все задачи линейного программирования (симплекс-метод и его модификации)

• Спец. Методы, предназначенные для решения отдельных задач линейного программирования. Например, методы решения транспортных задач (опорный план ищется с помощью северо-западного угла, оптимальных с помощью метода потенциала, метода Фоля и т.д.), геометрический способ, Венгерский способ.

Дискретное программирование связано с физической неделимостью многих объектов (3,8 автомобиля, 3,2 дома).

Нелинейное программирование (спрос на товары: каждую след. Единицу продать сложнее).

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

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

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

Математическая модель «задача оптимизации» включает в себя 3 составляющих:

§ Целевая функция показывает, в каком смысле план должен быть оптимальным, т.е. какая характеристика должна быть максимизирована или минимизирована.

§ Ограничения определяют зависимость между величинами, влияющими на решение задачи.

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

Пример:

Для изготовления различных изделий (А, В,С) предприятие использует три различных вида сырья.

Виды сырья	Нормы затрат сырья на 1 изделие	Общее количество сырья
А	В	С
Цена 1-го изд.(грн.)

Составим математическую модель задачи. Искомый выпуск изделий А обозначим через Х₁, В-Х₂,С-Х₃. Поскольку имеются ограничения по ресурсам, то составляются следующая система неравенств. Переменные Х₁,Х₂,Х₃ должны удовлетворять следующие системы неравенств:

18Х₁+15Х₂+12Х₃<= 360

6Х₁+4Х₂+8Х₃<=192 (1)

5Х₁+3Х₂+3Х₃<=180 (ограничения)

Ообщая стоимость произведенной предприятием продукции при условии выпуска Х₁ изделий А, Х₂ изделий В,Х₃, изделий С составляет:

F= 9Х₁+10Х₂+16Х₃ (2)

(целевая функция)

По своему экономическому содержанию Х₁,Х₂,Х₃ могут принимать только лишь не отрицательные значения:

Х₁,Х₂,Х₃ >=0 (3) (граничное условие)

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

18Х₁+15Х₂+12Х₃+Y₁<= 360

6Х₁+4Х₂+8Х₃+Y₂<=192 (3)

5Х₁+3Х₂+3Х₃+Y₃<=180

F= -9(-Х₁)-10(-Х₂)-16(-Х₃)

Эти дополнительные переменные y₁,y₂,y₃ по экономическому смыслу означают неиспользуемое при данном плане производства количество сырья того или иного вида. Параметр y₁-это неиспользуемое количество сырья 1-го вида. Составим исходную симплекс-таблицу:

В общем виде:

	-х1	-х2	-х3	Свободный член
У1	а11	а12	а13	б1
У2	а21	а22	а23	б2
У3	а31	а32	а33	б3
F	-с1	-с2	-с3

Согласно данным примера:

	-х1	-х2	-х3	Свободный член
У1
У2
У3
F	-9	-10	-16

Этот план не является оптимальным, так как элементы F-строки отрицательные. Отрицательные числа свидетельствуют не только о возможности увеличения общей стоимости производимой продукции, но и показывает, на сколько увеличится та сумма при введении в план того или иного вида продукции. Так, число –9 означает, что при включении в план производства одного изделия А обеспечивается увеличение выпуска продукции на 9 грн. и т.д. Здесь с экономической точки зрения наиболее целесообразным является включение в план производства изделия С.

Оптимизация целевой функции состоит из двух этапов:

a) Поиск опорного решения;

b) Поиск оптимального решения

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

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

2. Для элементов этого столбца (кроме элементов строки-F), имеющих тот же знак, что и соответствующие им свободные члены, вычисляют неотрицательные частные и выбирают наименьшее. Соответствующий элемент строки и столбца называют разрешающим. Например, находят 360/12=30; 192/8=24; 180/3=60. Наименьшее – 24,следственно, разрешающая строка у₂, разрешающий элемент – 8.

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

§ Разрешающий элемент а22 заменяют на новый по формуле а¹₂₂=1/а₂₂

§ Элементы разрешающей строки вычисляются по формуле:

а¹₂₁=а₂₁/а₂₂; а¹₂₃=а₂₃/а₂₂; б¹₂=б₂/а₂₂

§ Элементы разрешающего столбца вычисляются по формулам:

а¹₁₂= -а₁₂/а₂₂; а¹₂₃= -а23/а₂₂; с¹₂= -с₂/а₂₂

§ Прочие элементы таблицы (включая свободные члены и элементы F - строки) вычисляют по правилу прямоугольника:

а¹₁₁=а₁₁-(а₂₁*а₁₂/а₂₂)

При всем этом меняют местами символы переменных во втором столбце, во второй строке; повторяют предыдущие пункты до получения решения.

Перейдем к следующей таблице:

	-х1	-х2	У2	Свободный член
У1			-1,5
-х3	0,75	0,5	-0,125
У3	2,75	1,5	-0,375
F		-2

Экономическая интерпретация

Найдя число 24, мы с экономической точки зрения определили какое количество изделий С предприятие может изготавливать с учетом норм расхода и имеющихся объемов сырья каждого вида. То есть ограничивающим фактором дл производства изделий С является имеющийся объем сырья второго вида. С учетом его наличия может быть изготовлено 24 изделия С. 72 кг – неиспользованное сырье первого вида; 108 кг – неиспользованное сырье третьего вида; 384 – стоимость всей произведенной продукции.

§ Экономическая интерпретация второго столбца:

Число 0,5 показывает на сколько следует уменьшить изготовление изделия С, если запланировать изготовление одного изделия В. 9 и 1,5 показывают сколько потребуется сырья первого и третьего вида при включении в план производства одного изделия В. –2 показывает, что если будет запланирован выпуск одного изделия В, то это обеспечит увеличение выпуска продукции в стоимостном выражении на две гривны. Аналогично дается экономическая интерпретация первого столбца.

§ Экономическая интерпретация третьего столбца:

Число 0,125 показывает, что увеличение объема сырья второго вида на 1 кг позволило бы увеличить выпуск изделий С на 0,125 единицы. Одновременно потребовалось бы 1,5 сырья первого вида и 0,375 кг сырья третьего вида. Увеличение выпуска изделий С на 0,125 снизит выпуск продукции на 2грн.

Данный план не является оптимальным, так как в F – строке есть элемент с отрицательным знаком. Отрицательный член свидетельствует, что в следующем плане следует пересмотреть выпуск изделия В. Переходим к третьей таблице.

Здесь в качестве разрешающего элемента берем – х₂, в качестве разрешающей строки у₁, разрешающий элемент 9

	-х1	У1	У2	Свободный член
-х2		0,11	00,017
-х3	0,25	-0,06	0,208
У3	1,25	-0,017	-0,125
F		0,22	1,67

Как видно, в строке F нет отрицательного элемента, следовательно этот план является оптимальным. План выпуска продукции, включающий 8 изделий В и 20 изделий С. при данном плане выпуска изделий полностью используется сырье первого и второго вида и остается неиспользованным 96 кг. Сырья третьего вида, а стоимость производимой продукции равна 400 грн. оптимальным планом не предусматривается изготовление изделия А. Число 56 показывает, что при данном плане включения в него выпуска единиц изделия А приводит лишь к уменьшению общей величины стоимости на 5 грн.

3. Графический метод

Если общее число переменных задачи линейного программирования n=2 или она может быть

сведена к соответствующей задаче с числом независимых переменных k=2,то такая

задача может быть легко решена графическим методом.

Итак, пусть задача имеет вид:

максимизировать f(x,x)=(c x +c x) (1)

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

g (x,x)<b;

g (x,x)<b; (2)

........

g (x,x)<b;

x >0, x >0. (3)

Графический метод решения заключается в следующем:

Х2 X2 X2

2 F max

2

3 1 F=C2

1 Xорт

R 3 F=C1

N F max 4 F max

X1

Х1 Х1

а б в

рис.1

Алгоритм решения задачи:

1. Строим допустимое множество решений R, определяемое (2) и (3).

2. Далее строим вектор нормали N к целевой функции f(x,x).Его проекция на ось Ox равна kc, a на ось Ox - kc,где k - произвольный положительный скаляр. Заметим, что N указывает направление возрастания f (x,x).

3. Перемещаем прямую f(x,x) = const в направлении N так, чтобы она оставалась перпендикулярной N до тех пор, пока эта прямая не выйдет на границу множества R.

При этом возможен один из следующих случаев:

a) f(x,x) и R будут иметь лишь одну общую точку (крайнюю точку R); эта точка определяет единственное оптимальное решение;

b) f(x,x) и R имеют целое множество общих точек, это будет в том случае, когда вектор N окажется нормален к соответствующей грани множества R, данное множество общих точек представляет собой множество оптимальных решений задачи;

c) прямая f(x,x) = const не выходит на границу множества R, сколько бы её не перемещали (это будет в случае, если множество R - неограниченно), тогда целевая функция f(x,x) оказывается также неограниченной.

Соответствующие случаи иллюстрируются рис 1 а, б, в. Заметим, что при решении задачи минимизации f (x, x) перемещают в направлении, противоположном N.