Файл: Экономикоматематические методы и модели.pdf

23
Известны также технологические коэффициенты a
ij
, которые показыва- ют, сколько единиц i-го ресурса требуется для производства единицы изде- лия j-го вида
(
̅̅̅̅̅̅
̅̅̅̅̅).
Прибыль, получаемая предприятием при реализации изделия j-го вида, равна c
j
.
В планируемом периоде значения величин a
ij
, b
i и c
j
остаются постоян- ными.
Требуется составить такой план выпуска продукции, при реализации ко- торого прибыль предприятия была бы наибольшей.
Далее приведем пример известной задачи такого класса.
Компания специализируется на выпуске хоккейных клюшек и наборов шахмат. Каждая клюшка приносит компании прибыль в размере 2 у.е, а каж- дый шахматный набор - в размере 4 у.е. На изготовление одной клюшки тре- буется четыре часа работы на участке A и два часа работы на участке B.
Шахматный набор изготавливается с затратами шести часов на участке A, шести часов на участке B и одного часа на участке C. Доступная производ- ственная мощность участка A составляет 120 н/часов в день, участка В - 72 н/часа и участка С - 10 н/часов.
Сколько клюшек и шахматных наборов должна выпускать компания ежедневно, чтобы получать максимальную прибыль?
Условия задач указанного класса часто представляют в табличной форме
(см. таблицу 2.1).
Таблица 2.1
Исходные данные задачи об использовании производственных ресурсов
Производственные
участки
Затраты времени
на единицу продукции, н/час
Доступный фонд
времени, н/час клюшки наборы шахмат
А
4 6
120
В
2 6
72
С
-
1 10
Прибыль на единицу
продукции, у.е.
2 4
По данному условию сформулируем задачу линейного программирова- ния.
Обозначим x
1
– количество выпускаемых ежедневно хоккейных клюшек,
x
2
– количество выпускаемых ежедневно шахматных наборов.
Формулировка ЗЛП:
( ̅)
Электронный архив УГЛТУ

24
{
Подчеркнем, что каждое неравенство в системе функциональных огра- ничений соответствует в данном случае тому или иному производственному участку, а именно: первое - участку А, второе - участку В, третье - участку С.
Повторимся: методы решения ЗЛП мы будем рассматривать чуть позд- нее, а сейчас - пример задачи другого типа.
2. Задача о смесях (планирование состава продукции).
К группе задач о смесях относят задачи по отысканию наиболее дешево- го набора из определенных исходных материалов, обеспечивающих получе- ние смеси с заданными свойствами. Иными словами, получаемые смеси должны иметь в своем составе m различных компонентов в определенных количествах, а сами компоненты являются составными частями n исходных материалов.
Пример.
На птицеферме употребляются два вида кормов - I и II. В единице массы корма I содержатся единица вещества A, единица вещества В и единица ве- щества С. В единице массы корма II содержатся четыре единицы вещества А, две единицы вещества В и не содержится вещество C. В дневной рацион каждой птицы надо включить не менее единицы вещества А, не менее четы- рех единиц вещества В и не менее единицы вещества С. Цена единицы массы корма I составляет 3 руб, корма II - 2 руб.
Составьте ежедневный рацион кормления птицы так, чтобы обеспечить наиболее дешевый рацион.
Представим условие задачи в табл. 2.2.
Таблица 2.2
Исходные данные задачи о смесях
Питательные
вещества
Содержание веществ в единице массы корма,
ед.
Требуемое
количество
в смеси, ед.
корм I корм II
А
1 4
1
В
1 2
4
С
1
-
1
Цена единицы
массы корма, р
2 4
Сформулируем задачу линейного программирования.
Электронный архив УГЛТУ

25
Обозначим: x
1
– количество корма I в дневном рационе птицы, x
2
– количе- ство корма II в дневном рационе птицы.
Формулировка ЗЛП:
( ̅)
{
3. Транспортная задача.
Под транспортной задачей понимают целый ряд задач, имеющих опре- деленную специфическую структуру. Наиболее простыми транспортными задачами являются задачи о перевозках некоторого продукта из пунктов от- правления в пункты назначения при минимальных затратах на перевозку.
Пример.
Три поставщика одного и того же продукта располагают в планируемый период следующими его запасами: первый – 120 условных единиц, второй –
100 условных единиц, третий – 80 условных единиц. Этот продукт должен быть перевезен к трем потребителям, потребности которых равны 90, 90 и
120 условных единиц соответственно.
Обычно начальные условия транспортной задачи записывают в так называемую транспортную таблицу (табл. 2.3). В ячейках таблицы в левом верхнем углу записывают показатели затрат (расходы по доставке единицы продукта между соответствующими пунктами), под диагональю каждой ячейки размещается величина поставки x
ij
(т.е. x
ij
– количество единиц груза, которое будет перевезено от i-го поставщика j-му потребителю).
Таблица 2.3
Исходные данные транспортной задачи
Необходимо определить наиболее дешевый вариант перевозок, при этом каждый поставщик должен отправить столько груза, сколько имеется у него в
Электронный архив УГЛТУ

26 запасе, а каждый потребитель должен получить нужное ему количество про- дукции.
Сформулируем ЗЛП:
( ̅) 7x
11
+ 6x
12
+ 4x
13
+ 3x
21
+ 8x
22
+ 5x
23
+ 2x
31
+ 3x
32
+ 7x
33
→ min;
x
11
+ x
12
+ x
13
= 120,
x
21
+ x
22
+ x
23
= 100,
x
31
+ x
32
+ x
33
= 80,
x
11
+ x
21
+ x
31
= 90,
x
12
+ x
22
+ x
32
= 90,
x
13
+ x
23
+ x
33
= 120;
(
̅̅̅̅
̅̅̅̅)
2.2. Графическое решение задач
линейного программирования
Если система ограничений задачи линейного программирования пред- ставлена в виде системы линейных неравенств с двумя переменными, то та- кая задача может быть решена геометрически. Таким образом, данный метод решения ЗЛП имеет очень узкие рамки применения.
Однако метод представляет большой интерес с точки зрения выработки наглядных представлений о сущности задач линейного программирования.
Графический (или геометрический) метод предполагает последователь- ное выполнение ряда шагов. Ниже представлен порядок решения задачи линейного программирования на основе ее геометрической интерпретации.
1. Сформулировать ЗЛП.
2. Построить на плоскости {х
1
, х
2
} прямые, уравнения которых получа- ются в результате замены в ограничениях знаков неравенств на знаки точных равенств.
3. Найти полуплоскости, определяемые каждым из ограничений задачи.
4. Найти область допустимых решений.
5. Построить прямую зависимость c
1
x
1
+ c
2
x
2
= h, где h - любое положи- тельное число, желательно такое, чтобы проведенная прямая проходила через многоугольник решений.
6. Перемещать найденную прямую параллельно самой себе в направле- нии увеличения (при поиске максимума) или уменьшения (при поиске мини- мума) целевой функции. В результате либо отыщется точка, в которой целевая
Электронный архив УГЛТУ

27 функция принимает максимальное (минимальное) значение, либо будет уста- новлена неограниченность функции на множестве решений.
7. Определить координаты точки максимума (минимума) функции и вы- числить значение функции в этой точке.
Далее рассмотрим пример решения ЗЛП графическим методом. Для это- го воспользуемся представленной выше задачей о хоккейных клюшках и шахматных наборах.
1. Выше уже приводилась формулировка задачи, здесь нам остается лишь повторить ее:
( ̅) = 2x
1
+ 4x
2
→ max;
{
x
1
≥ 0, x
2
≥ 0.
2. Теперь построим прямые, соответствующие каждому из функцио- нальных ограничений задачи (рис. 2.1). Эти прямые обозначены на рисунке как (1), (2) и (3).
3. Штрихи на прямых указывают полуплоскости, определяемые ограни- чениями задачи.
4. Область допустимых решений (ОДР) включает в себя точки, для кото- рых выполняются все ограничения задачи. В нашем случае область ОДР представляет собой пятиугольник (на рисунке она обозначена ABCDO и окрашена синим цветом).
Рис. 2.1. Графическое решение ЗЛП
5. Прямая линия, соответствующая целевой функции (ЦФ), на рисунке представлена пунктирной линией.
6. Прямую линию ЦФ передвигаем параллельно самой себе вверх
(направление указано стрелкой), поскольку именно при движении в этом
Электронный архив УГЛТУ

28 направлении значение ЦФ увеличивается. Последней точкой многоугольника решений, с которой соприкоснется передвигаемая прямая ЦФ прежде чем покинет его, является точка C. Это и есть точка, соответствующая оптималь- ному решению задачи.
7. Осталось вычислить координаты точки С. Она является точкой пере- сечения прямых линий (1) и (2). Решив совместно уравнения этих прямых, найдем: х
1
= 24, х
2
= 4. Подставляя найденные величины в целевую функцию, найдем ее значение в оптимальной точке
( ̅
)
Таким образом, для максимизации прибыли компании следует ежеднев- но выпускать 24 клюшки и 4 набора. Реализация такого плана обеспечит ежедневную прибыль в размере 64 у.е.
2.3. Основные теоремы
линейного программирования
Для обоснования методов решения задач линейного программирования сформулируем ряд важнейших теорем, опуская их аналитические доказа- тельства. Уяснить смысл каждой из теорем поможет понятие о геометриче- ской интерпретации решения ЗЛП, данное в предыдущем подразделе.
Однако сначала напомним о некоторых понятиях, важных с точки зре- ния дальнейшего разговора.
Любые m переменных системы линейных уравнений с n переменными
(m < n) называются основными, если определитель матрицы коэффициентов при них отличен от нуля. Тогда остальные m-n переменных называются не- основными (или свободными).
Базисным решением системы m линейных уравнений c n переменными
(m < n) называется всякое ее решение, в котором все неосновные переменные имеют нулевые значения.
Теорема 1. Множество всех допустимых решений системы ограничений задачи линейного программирования является выпуклым.
В частном случае, когда в систему ограничений входят только две пере- менные x
1
и x
2
, это множество можно изобразить на плоскости. Так как речь идет о допустимых решениях (x
1
,x
2
≥ 0), то соответствующее множество бу- дет располагаться в первой четверти декартовой системы координат. Это множество может быть замкнутым (многоугольник), незамкнутым (неогра- ниченная многогранная область), состоять из единственной точки и, наконец, система ограничений-неравенств может быть противоречивой.
Теорема 2. Если задача линейного программирования имеет оптималь- ное решение, то оно совпадает с одной (двумя) из угловых точек множества допустимых решений.
Электронный архив УГЛТУ

29
Из теоремы 2 можно сделать вывод о том, что единственность опти- мального решения может нарушаться, причем, если решение не единствен- ное, то таких оптимальных решений будет бесчисленное множество (все точ- ки отрезка, соединяющего соответствующие угловые точки).
Теорема 3. Каждому допустимому базисному решению задачи линейно- го программирования соответствует угловая точка области допустимых ре- шений, и наоборот.
Следствием из теорем 2 и 3 является утверждение о том, что оптималь- ное решение (оптимальные решения) задачи линейного программирования, заданной (или приведенной) ограничениями-уравнениями, совпадает с допу- стимым базисным решением (допустимыми базисными решениями) системы ограничений.
Таким образом, оптимальное решение ЗЛП следует искать среди конеч- ного числа допустимых базисных решений.
2.4. Симплексный метод
Симплекс-метод решения ЗЛП был разработан и впервые применен для решения задач в 1947 г. американским математиком Дж. Данцигом.
Симплексный метод в отличие от графического универсален. С его по- мощью можно решить любую задачу линейного программирования [1, 4].
В основу симплексного метода положена идея последовательного улуч- шения получаемого решения.
Геометрический смысл симплексного метода состоит в последователь- ном переходе от одной вершины многогранника ограничений к соседней, в которой целевая функция принимает лучшее (или, по крайней мере, не худ- шее) значение до тех пор, пока не будет найдено оптимальное решение - вершина, где достигается оптимальное значение функции цели (если задача имеет конечный оптимум).
Таким образом, имея систему ограничений, приведенную к канониче- ской форме (все функциональные ограничения имеют вид равенств), находят любое базисное решение этой системы, заботясь только о том, чтобы найти его как можно проще. Если первое же найденное базисное решение оказалось допустимым, то проверяют его на оптимальность. Если оно не оптимально, то осуществляется переход к другому, обязательно допустимому базисному решению. Симплексный метод гарантирует, что при этом новом решении це- левая функция если и не достигнет оптимума, то приблизится к нему (или, по крайней мере, не удалится от него). С новым допустимым базисным решени- ем поступают так же, пока не отыщется решение, которое является опти- мальным.
Электронный архив УГЛТУ

30
Процесс применения симплексного метода предполагает реализацию трех его основных элементов:
1) способ определения какого-либо первоначального допустимого ба- зисного решения задачи;
2) правило перехода к лучшему (точнее, не худшему) решению;
3) критерий проверки оптимальности найденного решения.
Симплексный метод включает в себя ряд этапов и может быть сформу- лирован в виде четкого алгоритма (четкого предписания о выполнении по- следовательных операций). Это позволяет успешно программировать и реа- лизовывать его на ЭВМ. Задачи с небольшим числом переменных и ограни- чений могут быть решены симплексным методом «вручную».
Далее рассмотрим симплексный алгоритм, не углубляясь в его обосно- вание.
Реализация симплекс-метода включает восемь шагов. Опишем их, па- раллельно рассматривая пример выполнения каждого шага в применении к задаче о хоккейных клюках и шахматных наборах.
Шаг 1. Формулировка ЗЛП (формирование целевой функции и системы ограничений).
Для определенности будем считать, что решается задача на отыскание максимума. Ниже приведем общую постановку такой задачи.
( ̅)= c
1
x
1
+ c
2
x
2
+ ... + c
n
x
n
= max;
{
{ }
{ }
{ }
̅̅̅̅̅
Еще раз повторим формулировку задачи из нашего примера.
( ̅)
{
Шаг 2. Приведение задачи к канонической форме (перевод функцио- нальных ограничений в систему уравнений).
Для реализации шага в ограничения задачи вводятся дополнительные переменные. Ниже приведен порядок выполнения этой операции
Электронный архив УГЛТУ

31
{
{ }
{ }
{ }
Обозначим добавочные переменные несколько иначе, а именно:
y
1
= x
n+1
, y
2
= x
n+2
, ..., y
m
= x
n+m
,
(2.4) где n - число переменных в исходной задаче, m - число уравнений.
Все дополнительные переменные должны быть неотрицательными. В отношении добавочных переменных следует заметить, что они должны иметь тот же знак, что и свободные члены системы ограничений. В противном слу- чае используется так называемый M-метод (метод искусственного базиса).
Выполним второй шаг для нашего примера.
{
Шаг 3. Построение исходной симплекс-таблицы (получение первона- чального допустимого базисного решения).
При «ручной» реализации симплексного метода удобно использовать так называемые симплексные таблицы. Исходная симплекс-таблица соответ- ствует первоначальному допустимому базисному решению. В качестве тако- вого проще всего взять базисное решение, в котором основными являются дополнительные переменные x
n+1
, x
n+2
, ..., x
n+m
. Ниже приведены исходная симплексная таблица в общем виде (табл. 2.4) и в применении к рассматри- ваемой нами задаче (табл. 2.5).
Итак, в левом столбце записываются основные (базисные) переменные, в первой строке таблицы перечисляются все переменные задачи. Крайний правый столбец содержит свободные члены системы ограничений b
1
, b
2
, ...,
b
m
В последней строке таблицы (она называется оценочной) записываются коэффициенты целевой функции, а также значение целевой функции (с об- ратным знаком) при текущем базисном решении
( ( ̅))
В рабочую область таблицы (начиная со второго столбца и второй стро- ки) занесены коэффициенты a
ij при переменных системы ограничений.
Таким образом, в данном базисном решении неосновные переменные x
1 и x
2 равны нулю. Базисные переменные отличны от нуля: x
3
=120, x
4
=72,
x
5
= 10. Данное базисное решение является допустимым. Естественно, что
Электронный архив УГЛТУ

32 значение целевой функции в этом случае равно нулю, так как в формирова- нии целевой функции участвуют переменные, которые для данного базисно- го решения являются неосновными.
Шаг 4. Проверка условия: все c
j
≤ 0. Если «НЕТ» - осуществляется пере- ход к шагу 5, если «ДА» - задача решена. Таким образом, на данном шаге проверяется наличие положительных элементов в последней строке сим- плексной таблицы. Если такие элементы имеются, необходимо продолжать решение.
Таблица 2.4
Общий вид исходной симплекс-таблицы