Эффективное решение производственных проблем и задач
Способы линейного программирования.
Тема 2. Способы линейного
программирования.
Многие
задачки, с которыми приходится иметь дело в ежедневной практике, являются
многовариантными. Посреди огромного количества вероятных вариантов в критериях рыночных отношений
приходится искать лучшие в неком смысле при ограничениях, налагаемых
на природные, экономические и технологические способности. В связи с этим
появилась необходимость использовать для анализа и синтеза экономических ситуаций
и систем математические способы и современную вычислительную технику? Такие
способы соединяются воединыжды под общим заглавием — математическое программирование.
Главные
понятия
Математическое
программирование — область арифметики, разрабатывающая теорию и численные
способы решения многомерных экстремальных задач с ограничениями, т. е. задач на
экстремум функции многих переменных с ограничениями на область конфигурации этих
переменных.
Функцию,
экстремальное значение которой необходимо отыскать в критериях экономических
способностей, именуют мотивированной, показателем эффективности либо аспектом
оптимальности. Экономические способности формализуются в виде системы
ограничений. Все это составляет математическую модель. Математическая
модель задачки — это отражение оригинала в виде функций, уравнений,
неравенств, цифр и т. д. Модель задачки математического программирования включает:
1) совокупа
неведомых величин, действуя на которые, систему можно
улучшать. Их именуют планом задачки (вектором управления,
решением, управлением, стратегией, поведением и др.);
2) мотивированную
функцию (функцию цели, показатель эффективности, аспект оптимальности,
функционал задачки и др.). Мотивированная функция позволяет выбирать лучший
вариант - из огромного количества вероятных. Лучший вариант доставляет мотивированной функции
экстремальное значение. Это может быть прибыль, объем выпуска либо реализации,
издержки производства, издержки воззвания, уровень обслуживания либо
дефицитности, число комплектов, отходы и т. д.;
Эти условия
следуют из ограниченности ресурсов, которыми располагает общество в хоть какой
момент времени, из необходимости ублажения насущных потребностей, из
критерий производственных и технологических процессов. Ограниченными являются не
только вещественные, денежные и трудовые ресурсы. Такими могут быть
способности технического, технологического и вообщем научного потенциала.
Часто потребности превосходят способности их ублажения. Математически
ограничения выражаются в виде уравнений и неравенств. Их совокупа образует
область допустимых решений (область экономических способностей). План,
удовлетворяющий системе ограничений задачки, именуется допустимым.
Допустимый план, доставляющий функции цели экстремальное значение, именуется хорошим.
Среднее решение, вообщем говоря, не непременно единственно, вероятны
случаи, когда оно не существует, имеется конечное либо бессчетное огромное количество
хороших решений.
Один
из разделов математического программирования - линейным программированием.
Способы и модели линейного программирования обширно используются при оптимизации
процессов во всех отраслях народного хозяйства: при разработке производственной
программки предприятия, рассредотачивании ее по исполнителям, при размещении
заказов меж исполнителями и по временным интервалам, при определении
лучшего ассортимента выпускаемой продукции, в задачках многообещающего,
текущего и оперативного планирования и управления; при планировании
грузопотоков, определении плана товарооборота и его рассредотачивании; в задачках
развития и размещения производительных сил, баз и складов систем воззвания
вещественных ресурсов и т. д. В особенности обширное применение способы и модели
линейного программирования получили при решении задач экономии ресурсов (выбор
ресурсосберегающих технологий, составление консистенций, раскрой материалов),
производственно-транспортных и других задач.
Начало
линейному программированию было положено в 1939 г. русским математиком-экономистом Л. В. Канторовичем в работе «Математические способы
организации и планирования производства». Возникновение этой работы открыло новый
шаг в применении арифметики в экономике. Спустя 10 лет южноамериканский
математик Дж. Данциг разработал действенный способ решения данного класса задач
— симплекс-метод. Общая мысль симплексного способа (способа поочередного
улучшения плана) для решения ЗЛП состоит в последующем:
1) умение
отыскивать исходный опорный план;
2) наличие
признака оптимальности опорного плана;
3) умение
перебегать к нехудшему опорному плану.
Постановка
задачки линейного программирования и
характеристики ее решений
Линейное
программирование — раздел математического программирования, используемый при
разработке способов отыскания экстремума линейных функций нескольких переменных
при линейных дополнительных ограничениях, налагаемых на переменные. По типу
решаемых задач его способы делятся на универсальные и особые. При помощи
универсальных способов могут решаться любые задачки линейного программирования
(ЗЛП). Особые способы учитывают особенности модели задачки, ее мотивированной
функции и системы ограничений.
Особенностью задач линейного программирования будет то, что
экстремума мотивированная функция добивается на границе области допустимых решений.
Традиционные же способы дифференциального исчисления связаны с нахождением
экстремумов функции во внутренней точке области допустимых значений. Отсюда —
необходимость разработки новых способов.
Формы записи задачки линейного программирования:
Общей задачей линейного программирования именуют задачку
(2.1)
при ограничениях
(2.5)
- произвольные (2.6)
где - данные действительные числа; (2.1) – мотивированная функция; (2.1) – (2.6)
–ограничения; -
план задачки.
Пусть ЗЛП представлена в последующей записи:
Чтоб задачка (2.7) – (2.8) имела решение, системе её ограничений (2.8)
должна быть совместной. Это может быть, если r
этой системы не больше числа неведомых n.
Случай r>n
вообщем неосуществим. При r=n система имеет единственное решение, которое
будет при хорошим.
В данном случае неувязка выбора рационального решения теряет смысл. Выясним
структуру координат угловой точки многогранных решений. Пусть r
этом воспримут неотрицательные значения, то приобретенное личное решение системы
(8) именуют опорным решением (планом).
Аксиома. Если система векторов содержит m
линейно независящих векторов, то допустимый план
(2. 10)
является последней точкой полиэдра планов.
Аксиома. Если ЗЛП имеет решение, то мотивированная функция добивается
экстремального значения хотя бы в одной из последних точек полиэдра решений.
Если же мотивированная функция добивается экстремального значения более чем в одной
последней точке, то она добивается такого же значения в хоть какой точке, являющейся их
выпуклой линейной композицией.
Графический метод решения ЗЛП
Геометрическая
интерпретация экономических задач дает возможность наглядно представить, их
структуру, выявить особенности и открывает пути исследования более сложных
параметров. ЗЛП с 2-мя переменными всегда можно решить графически. Но уже в
трехмерном пространстве такое решение усложняется, а в местах, размерность
которых больше 3-х, графическое решение, вообщем говоря, нереально. Случай
2-ух переменных не имеет особенного практического значения, но его рассмотрение
проясняет характеристики ОЗЛП, приводит к идее ее решения, делает геометрически
приятными методы решения и пути их практической реализации.
Пусть дана задачка
Дадим геометрическую интерпретацию частей этой задачки. Каждое из
ограничений (2.12), (2.13) задает на плоскости некую полуплоскость. Полуплоскость
— выпуклое огромное количество. Но скрещение хоть какого числа выпуклых множеств является
выпуклым обилием. Отсюда следует, что область допустимых решений задачки
(2.11) — (2.13) есть выпуклое огромное количество.
Перейдем к геометрической интерпретации мотивированной функции. Пусть область
допустимых решений ЗЛП — непустое огромное количество, к примеру многоугольник
Выберем случайное значение мотивированной функции Это
уравнение прямой полосы. В точках прямой NМ мотивированная функция сохраняет
одно и то же неизменное значение . Считая в равенстве (2.11) параметром,
получим уравнение семейства параллельных прямых, именуемых линиями уровня
мотивированной функции (линиями неизменного значения).
Найдём личные производные мотивированной функции по и :
Личная производная (2.14) (так же как и (2.15)) функции указывает
скорость ее возрастания повдоль данной оси. Как следует, и — скорости
возрастания соответственно
повдоль осей и
. Вектор называется
градиентом функции. Он указывает направление наискорейшего возрастания мотивированной
функции:
Вектор указывает
направление наискорейшего убывания мотивированной функции. Его именуют антиградиентом.
Вектор перпендикулярен
к прямым семейства
Из геометрической интерпретации частей ЗЛП вытекает
последующий порядок ее графического решения.
1.
С учетом системы ограничений
строим область допустимых решений .
2.
Строим вектор наискорейшего возрастания
мотивированной функции — вектор градиентного направления.
3. Проводим произвольную линию
уровня
4.
При решении задачки на максимум
перемещаем линию уровня в направлении вектора так, чтоб она
касалась области допустимых решений в ее последнем положении (последней точке).
В случае решения задачки на минимум линию уровня перемещают в антиградиентном
направлении.
5.
Определяем лучший план и экстремальное
значение мотивированной функции
Симплексный
способ решение ЗЛП
Общая мысль
симплексного способа (способа поочередного улучшения плана) для решения ЗЛП
состоит
1) умение
отыскивать исходный опорный план;
2) наличие
признака оптимальности опорного плана;
3) умение
перебегать к нехудшему опорному плану.
Пусть ЗЛП представлена системой ограничений в
каноническом виде:
Молвят, что
ограничение ЗЛП имеет желательный вид, если при неотрицательной правой
части левая
часть ограничений содержит переменную, входящую с коэффициентом, равным единице,
а в другие ограничения равенства - с коэффициентом, равным нулю.
Пусть система
ограничений имеет вид
Сведем задачку
к каноническому виду. Для этого прибавим к левым частям неравенств
дополнительные переменные
В мотивированную
функцию дополнительные переменные вводятся с коэффициентами, равными нулю
Пусть дальше
система ограничений имеет вид
Сведём её к
эквивалентной вычитанием дополнительных переменных из левых частей неравенств
системы. Получим систему
Но сейчас
система ограничений не имеет желательного вида, потому что дополнительные
переменные входят
в левую часть (при ) с коэффициентами, равными –1.
Потому, вообщем говоря, базовый план не является допустимым. В данном случае
вводится так именуемый искусственный базис. К левым частям ограничений-равенств,
не имеющих желательного вида, добавляют искусственные переменные . В мотивированную
функцию переменные , вводят с коэффициентом М в
случае решения задачки на минимум и с коэффициентом - М для задачки на
максимум, где М - огромное положительное число. Приобретенная задачка именуется
М-задачей, соответственной начальной. Она всегда имеет желательный
вид.
Пусть начальная
ЗЛП имеет вид
(2.18)
причём ни одно из ограничений не имеет
предпочтительной переменной. М-задача запишется так:
(2.21)
Задачка (2.19)
- (2.21) имеет желательный план. Её исходный опорный план имеет вид
Если некие
из уравнений (2.17) имеют желательный вид, то в их не следует вводить
искусственные переменные.
Аксиома. Если
в рациональном плане
(2.22)
М-задачи
(2.19) - (2.21) все искусственные переменные
является хорошим планом
начальной задачки (2.16) - (2.18).
Для того чтоб решить
задачку с ограничениями, не имеющими желательного вида, вводят
искусственный базис и решают расширенную М - задачку, которая имеет исходный
опорный план
Решение
начальной задачки симплексным способом методом введения искусственных переменных называется симплексным
способом с искусственным базисом.
Если в
итоге внедрения симплексного способа к расширенной задачке получен
лучший план, в каком все искусственные переменные , то его 1-ые
n составляющие дают лучший план начальной задачки.
Аксиома.
Если в рациональном плане М-задачи хотя бы одна из
искусственных переменных отлична от нуля, то начальная задачка не имеет
допустимых планов, т. е. ее условия несовместны.
Признаки оптимальности.
Аксиома.
Пусть начальная задачка решается на максимум. Если для некого опорного плана
все оценки неотрицательны, то
таковой план оптимален.
Аксиома.
Если начальная задачка решается на минимум и для некого опорного плана все
оценки неположительны, то
таковой план оптимален.
Теория
двойственности
Понятие
двойственности разглядим на примере задачки рационального использования сырья.
Пусть на предприятии решили правильно использовать отходы основного производства.
В плановом периоде появились отходы сырья m видов в
объемах единиц
. Из этих
отходов, беря во внимание специализацию предприятия, можно сделать выпуск
n видов неосновной продукции. Обозначим через норму расхода
сырья i-го вида на единицу j-й продукции, - стоимость реализации
единицы j-й продукции (реализация обеспечена).
Неведомые величины задачки: — объемы выпуска j-й продукции, обеспечивающие предприятию максимум
выручки.
Математическая
модель задачки:
(2.25)
Представим
дальше, что с самого начала при исследовании вопроса об использовании отходов
основного производства на предприятии появилась возможность реализации их
некой организации. Нужно установить прикидочные оценки (цены) на эти
отходы. Обозначим их
Оценки должны
быть установлены исходя из последующих требований, отражающих несовпадающие
интересы предприятия и организации:
1) общую цена отходов сырья
покупающая организация стремится минимизировать;
2) предприятие согласно
уступить отходы только по таким ценам, при которых оно получит за их выручку,
не наименьшую той, что могло бы получить, организовав собственное создание.
Эти требования
формализуются в виде последующей ЗЛП.
Требование 1
покупающей организации – минимизация покупки:
Требование 2
предприятия, реализующего отходы сырья, можно сконструировать в виде системы
ограничений. Предприятие откажется от выпуска каждой единицы продукции первого
вида, если,
где левая часть значит выручку за сырьё идущее на единицу продукции первого
вида; правая – её стоимость.
Подобные рассуждения разумно провести в
отношении выпуска продукции каждого вида. Потому требование предприятия, реализующего
отходы сырья, можно формализовать в виде сл. системы ограничений:
(2.27)
По смыслу
задачки оценки не должны быть отрицательными:
(2.28)
Переменные называют
двоякими оценками либо беспристрастно обусловленными оценками.
Задачки (2.23)
- (2.25) и (2.26) - (2.28) именуют парой взаимно двояких ЗЛП.
Меж прямой и
двоякой задачками можно установить последующую связь:
1.
Если ровная задачка на максимум, то
двоякая к ней — на минимум, и напротив.
2.
Коэффициенты целевой функции прямой
задачки являются свободными членами ограничений двоякой задачки.
3.
Свободные члены ограничений прямой
задачки являются коэффициентами мотивированной функции двоякой.
4.
Матрицы ограничений прямой и
двоякой задач являются транспонированными друг к другу.
5.
Если ровная задачка на максимум, то
ее система ограничений представляется в виде неравенств типа . Двоякая
задачка решается на минимум, и ее система ограничений имеет вид неравенств типа .
6.
Число ограничений прямой задачки
равно числу переменных двоякой, а число ограничений двоякой — числу
переменных прямой.
7.
Все переменные в обеих задачках
неотрицательны.
Главные
аксиомы двойственности и их экономическое содержание
Аксиома. Для
всех допустимых планов прямой и
двоякой ЗЛП справедливо
неравенство
(2.29)
– основное
неравенство теории двойственности.
Аксиома
(аспект оптимальности Канторовича).
Если для
неких допустимых планов и пары двояких задач производится
неравенство,
то и являются
хорошими планами соответственных задач.
Аксиома
(малая аксиома двойственности).
Для существования
рационального плана хоть какой из пары двояких задач нужно и довольно
существование допустимого плана для каждой из их.
Аксиома.
Если одна из двояких задач имеет среднее решение, то и другая имеет
среднее решение, при этом экстремальные значения мотивированных функций равны: Если одна из
двояких задач неразрешима вследствие неограниченности мотивированной функции на
огромном количестве допустимых решений, то система ограничений другой задачки
противоречива.
Экономическое
содержание первой аксиомы двойственности состоит в последующем: если задачка
определения рационального плана, максимизирующего выпуск продукции, разрешима,
то разрешима и задачка определения оценок ресурсов. При этом стоимость продукции, приобретенной
при реализации рационального плана, совпадает с суммарной оценкой ресурсов.
Совпадение значений мотивированных функций для соответственных планов пары
двояких задач довольно для того, чтоб эти планы были хорошими. Это
означает, что план производства и вектор оценок ресурсов являются хорошими
и тогда только тогда, когда стоимость произведенной продукции и суммарная оценка ресурсов
совпадают. Оценки выступают как инструмент балансирования издержек и результатов.
Двоякие оценки, владеют тем свойством, что они гарантируют
рентабельность рационального плана, т. е. равенство общей оценки продукции и
ресурсов, и обусловливают убыточность всякого другого плана, хорошего от рационального.
Двоякие оценки позволяют сравнить и сбалансировать издержки и результаты
системы.
Аксиома
(о дополняющей нежесткости)
Для того,
чтоб планы и
пары
двояких задач были оптимальны, нужно и довольно выполнение критерий:
Условия
(2.30), (2.31) именуются критериями дополняющей нежесткости. Из их следует:
если какое-либо ограничение одной из задач ее хорошим планом обращается в
серьезное неравенство, то соответственная компонента рационального плана
двоякой задачки должна приравниваться нулю; если же какая-либо компонента рационального
плана одной из задач положительна, то соответственное ограничение в
двоякой задачке ее хорошим планом должно обращаться в серьезное
равенство.
Экономически
это значит, что если по некому хорошему плану производства расход i-го ресурса строго меньше его припаса , то в рациональном плане
соответственная двоякая оценка единицы этого ресурса равна нулю. Если же
в неком рациональном плане оценок его i-я
компонента строго больше нуля, то в рациональном плане производства расход
соответственного ресурса равен его припасу. Отсюда следует вывод: двоякие
оценки могут служить мерой дефицитности ресурсов. Дефицитный ресурс (вполне
применяемый по хорошему плану производства) имеет положительную оценку, а
ресурс лишний (применяемый не вполне) имеет нулевую оценку.
Аксиома (об
оценках). Двоякие оценки демонстрируют приращение функции цели,
вызванное малым конфигурацией свободного члена соответственного ограничения
задачки математического программирования, поточнее
(2.32)
Главные
виды экономических задач, сводящихся к ЗЛП
Задачка о
лучшем использовании ресурсов. Пусть некая производственная единица
(цех, завод, объединение и т. д.), исходя из конъюнктуры рынка, технических
либо технологических способностей и имеющихся ресурсов, может выпускать
n разных видов продукции (продуктов), узнаваемых под
номерами, обозначаемыми индексом j . Будем обозначать эту продукцию .
Предприятие при производстве этих видов продукции должно ограничиваться имеющимися
видами ресурсов, технологий, других производственных причин (сырья,
полуфабрикатов, рабочей силы, оборудования, электроэнергии и т. д.). Все эти
виды ограничивающих причин именуют ингредиентами . Пусть их число равно m; припишем им индекс i . Они ограничены, и
их количества равны соответственно условных единиц. Таким макаром, - вектор
ресурсов. Известна финансовая выгода (мера полезности) производства
продукции каждого вида, исчисляемая, скажем, по отпускной стоимости продукта, его
прибыльности, издержкам производства, степени ублажения потребностей и т.
д. Примем в качестве таковой меры, к примеру, стоимость реализации
, т.е. — вектор цен. Известны
также технологические коэффициенты , которые указывают, сколько единиц i–го ресурса требуется для производства
единицы продукции
>j-го вида. Матрицу коэффициентов называют
технологической и обозначают буковкой А. Имеем . Обозначим через план производства,
показывающий, какие виды продуктов нужно создавать и в каких
количествах, чтоб обеспечить предприятию максимум объема реализации при
имеющихся ресурсах.
Потому что - стоимость реализации
единицы j-й продукции, стоимость реализованных единиц будет равна
, а общий
объем реализации
Это
выражение — мотивированная функция, которую необходимо максимизировать.
Потому что - расход i-го ресурса на создание единиц j-й продукции, то, просуммировав расход i-го ресурса на выпуск всех n
видов продукции, получим общий расход этого ресурса, который не должен превосходить
единиц:
Чтоб разыскиваемый
план был
реализован, вместе с ограничениями на ресурсы необходимо наложить условие неотрицательности
на объёмы выпуска
продукции:
Таким макаром,
модель задачки о лучшем использовании ресурсов воспримет вид:
(2.33)
при
ограничениях:
(2.35)
Потому что
переменные входят
в функцию и
систему ограничений исключительно в первой степени, а характеристики являются неизменными в
планируемый период, то (2.33)-(2.35) – задачка линейного программирования.
Задачка о консистенциях
В разных
отраслях народного хозяйства появляется неувязка составления таких рабочих
консистенций на базе начальных материалов, которые обеспечивали бы получение
конечного продукта, владеющего определенными качествами. К этой группе задач
относятся задачки о выборе диеты, составлении кормового рациона в
животноводстве, шихт в металлургии, горючих и смазочных консистенций в
нефтеперерабатывающей индустрии, консистенций для получения бетона в строительстве
и т. д. Высочайший уровень издержек на начальные сырьевые материалы и необходимость
увеличения эффективности производства выдвигает на 1-ый план последующую задачку:
получить продукцию с данными качествами при меньших издержек на начальные
сырьевые материалы.
Пример.
Для откорма животных употребляется три вида комбикорма: А, В
и С. Каждому животному в день требуется более 800 г. жиров, 700 г. белков и 900 г. углеводов. Содержание в 1 кг. каждого вида комбикорма жиров белков и углеводов (гр) приведено в таблице:
