Оптимальное значение целевой функции называется. Смотреть страницы где упоминается термин функция целевая

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

Примеры

Гладкие функции и системы уравнений

Задача решения любой системы уравнений

{ F 1 (x 1 , x 2 , … , x M) = 0 F 2 (x 1 , x 2 , … , x M) = 0 … F N (x 1 , x 2 , … , x M) = 0 {\displaystyle \left\{{\begin{matrix}F_{1}(x_{1},x_{2},\ldots ,x_{M})=0\\F_{2}(x_{1},x_{2},\ldots ,x_{M})=0\\\ldots \\F_{N}(x_{1},x_{2},\ldots ,x_{M})=0\end{matrix}}\right.}

может быть сформулирована как задача минимизации целевой функции

S = ∑ j = 1 N F j 2 (x 1 , x 2 , … , x M) (1) {\displaystyle S=\sum _{j=1}^{N}F_{j}^{2}(x_{1},x_{2},\ldots ,x_{M})\qquad (1)}

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

Для всякой гладкой целевой функции можно приравнять к 0 {\displaystyle 0} частные производные по всем переменным. Оптимум целевой функции будет одним из решений такой системы уравнений. В случае функции (1) {\displaystyle (1)} это будет система уравнений метода наименьших квадратов (МНК). Всякое решение исходной системы является решением системы МНК. Если исходная система несовместна, то всегда имеющая решение система МНК позволяет получить приближённое решение исходной системы. Число уравнений системы МНК совпадает с числом неизвестных, что иногда облегчает и решение совместных исходных систем.

Линейное программирование

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

Комбинаторная оптимизация

Типичным примером комбинаторной целевой функции является целевая функция задачи коммивояжёра. Эта функция равна длине гамильтонова цикла на графе. Она задана на множестве перестановок n − 1 {\displaystyle n-1} вершины графа и определяется матрицей длин рёбер графа. Точное решение подобных задач часто сводится к перебору вариантов.

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

Линейное программирование

Линейное программирование – это направление математического программирования, изучающее методы решения экстремальных задач, которые характеризуются линейной зависимостью между переменными и линейным критерием. Такие задачи находят обширные приложения в различных сферах человеческой деятельности. Систематическое изучение задач такого типа началось в 1939 – 1940 гг. в работах Л.В. Канторовича.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(1.1) при ограничениях

(1.2) требования неотрицательности

(1.3) где x j – переменные (неизвестные);

- коэффициенты задачи линейного программирования.

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

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

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

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

Симплекс-метод был разработан и впервые применен для решения задач в 1947 г. американским математиком Дж. Данцигом.

Двумерные задачи линейного программирования решаются графически. Для случая N=3 можно рассмотреть трехмерное пространство и целевая функция будет достигать своё оптимальное значение в одной из вершин многогранника.

Допустимым решением (допустимым планом) задачи ЛП, данной в стандартной форме, называется упорядоченное множество чисел (х1, х2, …, хn), удовлетворяющих ограничениям; это точка в n-мерном пространстве.

Множество допустимых решений образует область допустимых решений (ОДР) задачи ЛП. ОДР представляет собой выпуклый многогранник (многоугольник).

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

Базисным называется решение, при котором все свободные переменные равны нулю.

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

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

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

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

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

В основу симплексного метода положена идея последовательного улучшения получаемого решения.

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

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

Процесс применения симплексного метода предполагает реализацию трех его основных элементов:

способ определения какого-либо первоначального допустимого базисного решения задачи;

правило перехода к лучшему (точнее, не худшему) решению;

критерий проверки оптимальности найденного решения.

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

6.1.Введение

Оптимизация. Часть 1

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

6.2.Основы теории оптимизации

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

Рассматривая некоторую произвольную систему, описываемую m уравнениями с n неизвестными, можно выделить три основных типа задач. Если m=n , задачу называют алгебраической. Такая задача обычно имеет одно решение. Если m>n, то задача переопределена и, как правило, не имеет решения. Наконец, при m

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

Проектные параметры

Этим термином обозначают независимые переменные параметры, которые полностью и однозначно определяют решаемую задачу проектирования. Проектные параметры - неизвестные величины, значения которых вычисляются в процессе оптимизации. В качестве проектных параметров могут служить любые основные или произ-водные величины, служащие для количественного описания системы. Так, это могут быть неизвестные значения длины, массы, време-ни, температуры. Число проектных параметров характеризует сте-пень сложности данной задачи проектирования. Обычно число проектных параметров обозначают через n, а сами проектные пара-метры через х с соответствующими индексами. Таким образом n проектных параметров данной задачи будем обозначать через

X1, x2, x3,...,xn.

Целевая функция

Это - выражение, значение которого инженер стремится сделать максимальным или минимальным. Целевая функция позволяет количественно сравнить два альтернативных решения. С мате-матической точки зрения целевая функция описывает некоторую (n+1) - мерную поверхность. Ее значение определяется проектными параметрами

M=M(x 1 , x 2 ,...,x n).

Примерами целевой функции, часто встречающимися в инженерной практике, являются стоимость, вес, прочность, габариты, КПД. Если имеется только один проектный параметр, то целевую функцию можно представить кривой на плоскости (рис.6.1). Если проектных параметров два, то целевая функция будет изображаться поверх-ностью в пространстве трех измерений (рис.6.2). При трех и более проектных параметрах поверхности, задаваемые целевой функцией, называются гиперповерхностями и не поддаются изобра-

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

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

Рис.1.Одномерная целевая функция.

Рис.6.2.Двумерная целевая функция.

замкнутой математической форме, в других случаях она может

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

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

Поиск минимума и максимума

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

Пространство проектирования

Так называется область, определяемая всеми n проектными параметрами. Пространство проектирования не столь велико, как может показаться, поскольку оно обычно ограничено рядом

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

Рис.6.3.Изменением знака целевой функции на противоположный

задача на максимум превращается в задачу на минимум.

удовлетворительного решения. Ограничения делятся на две группы: ограничения - равенства и ограничения - неравенства.

Ограничения - равенства

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

C 1 (x 1 , x 2 ,...,x n)=0,

C 2 (x 1 , x 2 ,...,x n)=0,

..................

C j (x 1 , x 2 ,...,x n)=0.

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

Ограничения - неравенства

Это особый вид ограничений, выраженных неравенствами. В общем случае их может быть сколько угодно, причем все они имееют вид

z 1 r 1 (x 1 , x 2 ,...,x n) Z 1

z 2 r 2 (x 1 , x 2 ,...,x n) Z 2

.......................

z k r k (x 1 , x 2 ,...,x n) Z k

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

Локальный оптимум

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

Рис.6.4.Произвольная целевая функция может иметь несколько

локальных оптимумов.

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

Глобальный оптимум

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

Пример 6.1

Пусть требуется спроектировать прямоугольный контейнер объемом 1м , предназначенный для перевозки неупакованного волокна. Желательно, чтобы на изготовление таких контейнеров затрачивалось как можно меньше материала (при условии посто-янства толщины стенок это означает, что площадь поверхности должна быть минимальной), так как при этом он будет дешевле. Чтобы контейнер удобно было брать автопогрузчиком, его ширина должна быть не менее 1,5м.

Сформулируем эту задачу в виде, удобном для применения алгоритма оптимизации.

Проектные параметры: x 1 , x 2 , x 3 .

Целевая функция (которую требуется минимизировать) - площадь боковой поверхности контейнера:

A=2(x 1 x 2 +x 2 x 3 +x 1 x 3), м2.

Ограничение - равенство:

Объем = x 1 x 2 x 3 =1м3.

Ограничение - неравенство:

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

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

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

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

В зависимости от вида функций и задачи математического программирования делятся на ряд классов (линейной, нелинейное, выпуклое, целочисленное, стохастическое, динамическое программирование и др.).

В общем виде задача ЛП имеет следующий вид:

, (5.1)

, , (5.2)

, , (5.3)

где , , – заданные постоянные величины.

Функцию (5.1) называют целевой функцией; системы (5.2), (5.3) – системой ограничений; условие (5.4) – условием неотрицательности проектных параметров.

Совокупность проектных параметров , удовлетворяющих ограничениям (5.2), (5.3) и (5.4), называют допустимым решением или планом .

Оптимальным решением или оптимальным планом задачи ЛП называется допустимое решение , при котором целевая функция (5.1) принимает оптимальное (максимальное или минимальное) значение.

Стандартной задачей ЛП называют задачу нахождения максимального (минимального) значения целевой функции (5.1) при условии (5.2) и (5.4), где , , т.е. т.е. ограничения только в виде неравенств (5.2) и все проектные параметры удовлетворяют условию неотрицательности, а условия в виде равенств отсутствуют:

, , (5.5)

Канонической (основной) задачей ЛП называют задачу нахождения максимального (минимального) значения целевой функции (5.1) при условии (5.3) и (5.4), где , , т.е. т.е. ограничения только в виде равенств (5.3) и все проектные параметры удовлетворяют условию неотрицательности, а условия в виде неравенств отсутствуют:

Каноническую задачу ЛП можно также записать в матричной и векторной форме.

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

Векторная форма канонической задачи ЛП.

Целевая функция. Если доход от реализации одного стола равен С 1 рублей, то от реализации столов в объеме х 1 штук месячный доход

составит С 1 х 1 рублей. Аналогично месячный доход от реализации шкафов составит С 2 х 2 рублей. Обозначив общий доход (в руб.) через Z , можно дать следующую математическую формулировку целевой функции: определить (допустимые) значения х 1 , и х 2 , максимизирующие величину общего дохода Z = С 1 х 1 + С 2 х 2 =

∑

j=1

C j x j .

Ограничения. При решении рассматриваемой задачи должны быть учтены ограничения на расход ресурсов. Пиломатериал идет на изготовление и столов и шкафов. На один стол идет а 11 (м 3) пиломатериала, тогда на столы в количестве x 1 штук потребуется а 11 x 1 (м 3) пиломатериала. На изготовление шкафов в количестве х 2 штук потребуется а 12 х 2 (м 3) пиломатериала. Всего пиломатериала потребуется а 11 х 1 + а 12 x 2 (м 3). Расход его не должен превышать величины b 1 (м 3). Тогда ограничение на пиломатериал запишем в виде неравенства

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

х 1 ≥ 0, х 2 ≥ 0,

где х 1 , х 2 - целые числа.

Итак, математическую модель задачи можно записать следующим образом: определить месячные объемы производства столов х 1 и шкафов х 2 , при которых достигается

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

Для определения переменных рассмотренной модели могут использоваться методы линейного программирования. Базовым методом ЛП является симплекс-метод, разработанный Г. Данцигом . Задачу ЛП можно решить и графически. Графическое представление решения задачи поможет понять и идею симплекс-метода. Конкретизируем задачу, представив исходные данные в табл. 3.1 (данные приводятся условные).

Таблица 3.1


Ресурсы	Расход ресурсов на единицу продукции		Запас ресурсов
Ресурсы	Стол	Шкаф	Запас ресурсов
Пиломатериалы (м 3)	0,06	0,07	42
Шурупы (кг)	0,04	0,085	34
Краска (кг)	0,035	0,12	42
Цена единицы продукции (руб.)	500	750	-

Запишем модель задачи с приведенными данными:

В дальнейшем ограничение (3.5) учитывать не будем, а решение задачи получим округлением найденных переменных задачи (3.0-3.4).

44 :: 45 :: 46 :: 47 :: Содержание

47 :: 48 :: 49 :: 50 :: 51 :: Содержание

3.2.2. Графический способ решения ЗЛП

Для определения решения ЗЛП с двумя переменными выполним следующие действия.

1. Построим множество допустимых решений Ω задачи. Данное множество Ω образуется в результате пересечения полуплоскостей (ограничений) (3.1-3.4). На рис. 3.2 множество допустимых решений показано в виде пятиугольника. Области, в которых выполняются соответствующие ограничения в виде неравенств, указываются стрелками, направленными в сторону допустимых значений переменных. Полученный многогранник Ω называют симплексом. Отсюда и название метода поиска оптимального решения.

2. Построим вектор-градиент С, составленный из производных целевой функции по переменным задачи, который указывает направление возрастания целевой функции по этим переменным. С = (С 1 , С 2) = (500,750). Начало этого вектора лежит в точке с координатами (0, 0), а конец - в точке (500, 750). Ряд параллельных штриховых линий, перпендикулярных вектору-градиенту, образует множество целевых

Функций при произвольно выбранных значениях Z . При Z = 0 прямая (целевая функция) проходит через точку (0, 0), а целевая функция Z принимает минимальное значение.

Рис. 3 2 Геометрическая интерпретация ЗЛП

3. Переместим прямую, характеризующую доход Z , в направлении вектор-градиента (для задачи max Z ) до тех пор, пока она не сместится в область недопустимых решений. На рис. 3.2 видно, что оптимальному решению соответствует точка X* = (х 1 *, х 2 *). Так как точка X* является точкой пересечения прямых (3.1) и (3.2), значения х 1 * и х 2 * определяются решением системы двух уравнений:

Решение указанной системы уравнений дает результат х 1 * = 517,4 и х 2 * =156,5. Полученное решение означает, что месячный объем производства столов должен составить 517 шт., а шкафов - 156 шт. Доход, полученный в этом случае, составит:

Z = 517 · 500 + 156 · 750 = 375500 рублей

ЗЛП со многими переменными можно решить графически, если в ее канонической записи число неизвестных n и число линейно независимых уравнений m связано соотношением n-m ≤ 2. Запишем каноническую форму ЗЛП, рассмотренную выше. Для этого введем новые переменные x 3 , x 4 и x 5 .

Для данной ЗЛП число переменных n = 5, а число линейно-независимых уравнений m = 3. Эта и другие ЗЛП в канонической форме могут быть решены графически, если n-m ≤ 2.

Выберем любые m неизвестные и выразим каждую из них через оставшиеся (n-m ) переменные. В нашем случае удобно взять переменные x 3 , x 4 и x 5 и выразить их через x 1 и x 2 .

Учитывая неотрицательность всех переменных, в том числе х 3 ≥ 0, х 4 ≥ 0 и х 5 ≥ 0, а также зависимость последних от двух переменных x 1 и х 2 , можно графически показать решение расширенной задачи с проекцией на переменные x 1 и х 2 . Полуплоскость х 3 ≥ 0 (см. рис. 3.2) совпадает с ограничением (3.1), полуплоскость х 4 ≥ 0 - с ограничением (3.2), а полуплоскость х 5 ≥ 0 - с ограничением (3.3). Точка оптимума в координатах x 1 и х 2 образуется в результате пересечения полуплоскостей х 3 и х 4: x 1 * = 517,4; х 2 = 156,5. Соответственно значения переменных х 3 Ä х 4 будут нулевыми: x 3 * =0; х 4 * = 0. Тогда из (3.9) следует, что x 5 * = 42 - 0,035·517,4 - 0,12·156,5 = 5,1. Решением ЗЛП (3.6-3.10) будет вектор X* = (517,4; 156,5; 0; 0; 5,1).

Геометрическое представление ЗЛП отражает следующее:

1) множество допустимых решений Ω выпуклое;

2) оптимальное решение не существует, если множество Ω пустое или неограниченное в направлении перемещения семейства гиперплоскостей уровня цели поиска экстремума;

3) решение находится в одной из угловых точек (вершин) множества допустимых решений Ω, получивших название базисных;

4) для канонической ЗЛП базисные решения характеризуются вектором X - (x 1 , x 2 ,..., х n), в котором значения m переменных отличны от нуля, где m - число линейно независимых уравнений задачи (число базисных переменных угловой точки множества Ω).

Для оптимального решения X* рассмотренного примера базисными переменными стали переменные x 1 , х 2 и х 5 . Оставшиеся переменные (n - m ) называют небазисными или свободными. Их значения в угловой точке равны нулю.

Обратите внимание на то, что любая базисная переменная может быть выражена через небазисные, и базисная переменная в модели (3.6)-(3.10) записывается один раз с коэффициентом единица.

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

47 :: 48 :: 49 :: 50 :: 51 :: Содержание

50 :: 51 :: 52 :: 53 :: 54 :: 55 :: 56 :: 57 :: 58 :: 59 :: 60 :: 61 :: Содержание

3.2.3. Алгебраический (симплексный) метод решения ЗЛП

Рассмотренный выше графический способ решения задачи ЛП позволяет понять идею методов оптимизации, в том числе и методов линейного программирования. Сущность всех методов математического программирования заключается в том, чтобы вместо "слепого" перебора вариантов плана вести перебор выборочный, организованный, направленный на скорейшее, а в некоторых случаях и последовательное, улучшение решения.

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

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

К точке оптимума можно подобраться последовательно, переходя от одной угловой точки к соседней, например, каждый раз от исходной (опорной) точки X 0 (х 1 = 0, х 2 = 0) последовательно к той соседней, которая ближе и быстрее приближает к X*. Перебор точек решения по такой схеме позволяет предложенный Р. Данцигом симплекс-метод . Для нашего примера на первом шаге (итерации) от опорной точки X 0 мы перейдем по схеме симплекс-метода к точке X 1 с координатами (700, 0) и на втором шаге перейдем к точке X*. По другому же пути к точке X* можно добраться лишь за три шага. С вычислительной точки зрения симплекс-метод реализуется через так называемые симплекс-таблицы, которые рассчитываются для каждой угловой точки, начиная с опорной. Симплекс-таблицы позволяют определить оптимальность принимаемого решения, значения переменных, оценить ресурсные параметры (ограничения) на предмет их дефицитности, и в случае неоптимального решения, указывают, как перейти к соседней точке (следующей таблице). В силу различных особенностей и постановок задач ЛП симплекс-метод имеет различные модификации: прямой, двойственный, двухэтапный .

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

Пусть система ограничений такова:

Добавив к левым частям неравенства дополнительные переменные x n+i ≥ 0, i = 1, m , получим каноническую (расширенную) задачу, стратегически эквивалентную исходной, с системой ограничений:

Тогда начальным опорным планом будет вектор

Который удовлетворяет допустимости решения (он является базисным, т.к. число ненулевых элементов равно m , и опорным, т.к. все x j ≥ 0). Пусть система ограничений такова:

Вычтя из левых частей неравенства дополнительные переменные x n+i ≥ 0, i = 1, m , получим расширенную задачу, стратегически эквивалентную исходной, с системой ограничений:

Однако теперь дополнительные переменные входят в левую часть ограничений с коэффициентами, равными минус единице. Поэтому план

не удовлетворяет условиям допустимости решения (он базисный, но не опорный).

Как в первом, так и во втором случае при добавлении дополнительных переменных (они же становятся базисными переменными) в систему ограничений эти же переменные вводятся в целевую функцию с коэффициентами, равными нулю: C n+i ≥ 0, i = 1, m , т.е. в целевой функции при базисных переменных стоят нулевые коэффициенты, а при небазисных - коэффициенты С j , j = 1, n . Пусть целевая функция стремится к минимуму. Тогда значение целевой функции может быть уменьшено, если в базис вводить ту переменную x j , при которой коэффициент С j целевой функции имеет знак минус. И если все коэффициенты в целевой функции имеют знак плюс, то уменьшить ее значение не представляется возможным. Поэтому признаком оптимальности решения ЗЛП служат коэффициенты (оценки) в целевой функции при небазисных переменных.

В зависимости от выполнения условий оптимальности и допустимости применяют ту или иную схему решения ЗЛП .

Методы решения ЗЛП разбиваются на две группы:

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

Точке за конечное число шагов (итераций). К этой группе относятся прямой симплекс-метод, метод потенциалов и другие;

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

При выборе алгоритма решения задачи ЛП исходят из следующих данных. Пусть ЗЛП приведена к каноническому виду, решается на минимум и свободные коэффициенты b i ≥ 0, i = 1, m . Тогда, если в целевой функции задачи имеются отрицательные коэффициенты (условие оптимальности решения задачи не выполняется), а начальный план задачи не имеет отрицательных значений переменных (условие допустимости решения задачи выполняется), то для решения предлагаемой задачи следует воспользоваться алгоритмом прямого симплекс-метода (табл. 3.2). Двойственный симплекс-метод применяется, если условие оптимальности решения задачи выполняется, а допустимости - нет. Двухэтапный симплекс-метод применяется, если условия и оптимальности и допустимости решения задачи не выполняются.

Таблица 3.2

Рассмотрим прямой симплекс-метод решения задач ЛП на следующем примере.

Пример 3.1

Минимизировать функцию Z = -x 1 - х 2 при ограничениях: 0,5х 1 + х 2 ≤ 1;

2х 1 + х 2 ≤ 2;

х 1 , х 2 ≥ 0.

Графическое представление задачи (3.11-3.14) показано на рис. 3.3.

Рис. 3.3. Графическое представление задачи (3.11) - (3.14)

Начальной базисной опорной точкой задачи будет вектор Х 0 = (0; 0; 1; 2). Значение целевой функции в этой точке Z (X 0) = 0.

Перенесем в целевой функции (3.11) переменную Z за знак равенства и данную задачу запишем в виде табл. 3.3, называемой симплекс-таблицей (нулевая итерация).

Таблица 3.3

В литературе описаны и другие формы записи симплекс-таблицы . По симплекс-таблице всегда можно сказать, является ли найденное решение оптимальным. В данном случае решение х 1 = 0; х 2 = 0; х 3 = 1; х 4 = 2 не является наилучшим, так как можно ввести в базис одну из переменных х 1 или х 2 (при этих переменных стоят коэффициенты со знаком минус с 1 = -1 и с 2 = - 1), уменьшив значение целевой функции. Тогда вводя в базис одну из небазисных переменных х 1 или х 2 (увеличив ее значение), следует вывести из базиса переменную х 3 или х 4 (доведя ее значение до нуля). В прямом симплекс-методе рассматриваются последовательно вопросы:

переход к новой канонической форме ЗЛП (к следующей итерации симплекс-таблицы).

. Целесообразно включить в базис ту переменную, коэффициент при которой имеет наименьшее значение. Коэффициенты при небазисных переменных в неоптимальном решении имеют отрицательные значения. Пусть это будет переменная x s , для которой C s = min j , с j < 0, j не∈ базису. В нашем примере c 1 = c 2 = -1, поэтому включим в базис любую переменную х 1 или х 2 (пусть х 1). Столбец в симплекс-таблице с переменной x s назовем ведущим столбцом, в нашем случае s = l.

. Если в базис включаем переменную x 1 , то это значит, что увеличиваем ее значение с нуля до каких-то определенных пределов. До каких? Обратимся к рис. 3.3. Крайним значением для переменной х 1 будет единица, при этом переменная (прямая) х 4 в ограничении (3.13) примет значение, равное нулю, то есть из базиса выйдет х 4 , а ее место займет переменная x 1 . Из уравнения (3.12) определим значение х 3 = 1 - 0,5 · 1 = 0,5. Таким образом, на следующей итерации (шаге) допустимым решением будет вектор X 1 = (1; 0; 0,5; 0). Значение целевой функции в этой точке Z (1) = -1.

Не прибегая к графическому представлению задачи, определение предельного значения x l и определение переменной х 4 , которую следует вывести из базиса, можно провести на следующем распределении. Если вывести из базиса переменную х 3 , т.е. должно быть х 3 = 0, то из (3.12) следует x l = b 1 /а 1 s = 1/0,5 = 2. Если вывести из базиса переменную х 4 , т.е. сделать х 4 = 0, то из (3.13) x l = b 2 /а 2 s = 1/1 = 1. Получается, что значение x l = 1 или x l = 2. Но при x l = 2 в уравнении (3.13) переменная х 4 = 1 - 2 - 0,5 · 0 = -1, что противоречит условию допустимости решения (3.14). Поэтому включаем в базис x l с наименьшим значением, которое определено из второго ограничения. В этом ограничении находится исключаемая переменная из базиса х 4 . В общем случае переменная x s , включаемая в базис, может увеличиваться до значения

Пусть максимум достигается в строке r , т.е. x s = b r /a rs , тогда в этой строке базисная переменная обращается в нуль, т.е. выводится из базиса. Строку r называют ведущей строкой , а элемент а rs - ведущим элементом . Если в ведущем столбце не найдутся положительные a is , то это означает, что ЗЛП не имеет области допустимых решений.

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

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

Эта таблица на итерации 2 соответствует оптимальному решению X* = X 2 = (2/3; 2/3; 0; 0).

Значение целевой функции Z (X*) = -4/3.

Таблица 3.4

Рассмотрим двойственный симплекс-метод решения задачи ЛП на следующем примере.

Пример 3.2

Максимизировать функцию Z = -х 1 - х 2 при ограничениях:

0,5х 1 + х 2 ≤ 1;

2х 1 + х 2 ≥ 2;

х 1 , х 2 ≥ 0.

В канонической форме ЗЛП примет вид

Графическое представление задачи показано на рис. 3.4.

Рис. 3.4. Графическое представление задачи (3.15) - (3.18)

Составим симплекс-таблицу 3.5.

Таблица 3.5

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

Однако начальное решение Х 0 = (0; 0; 1; -2) является отрицательным.

Попытаемся решить задачу (в противоположность прямому симплекс-методу) последовательным движением от исходной недопустимой точки Х 0 к X*, рассматривая вопросы:

поиск переменной для исключения из базиса;
поиск переменной для включения в базис;
переход к новой форме ЗЛП (последующей итерации решения).

Поиск переменной для исключения из базиса . Из базиса исключается переменная из ведущей строки r , имеющая наименьшее отрицательное значение. Если все переменные, расположенные в базисе, будут положительными, то вычисления заканчиваются, так как решение

Будет и оптимальным и допустимым. В нашем примере исключаем переменную х 4 = -2.

Поиск переменной для включения в базис . Какую небазисную переменную включить в базис х 1 или х 2 ? В принципе любую можно включить в базис с целью движения в область допустимых решений. Из графического представления задачи (см. рис. 3.4) видно, что при включении в базис переменной х 2 мы попадаем сразу в допустимую и оптимальную точку X*. В литературе показано, что к оптимальному решению можно добраться быстрее, если выбирать для включения в базис переменную x s такую, что для нее отношение C s /|a rs | для всех элементов a rs ведущей строки будет минимальным:

Если все элементы a rj · ≥ 0, то это будет означать, что задача не имеет допустимых решений. В нашем примере минимальное отношение (3.19) достигается для переменной х 1 и равно 1/2. Решим задачу табличным способом (табл. 3.6).

Таблица 3.6

Оптимальное решение: X* = (1; 0; 1/2; 0;); Z (X* ) = -z" = -1.

Предположим, что при решении предыдущего примера (см. табл. 3.6) в базис включили бы не х 1 , а переменную х 2 , то получили бы на итерации 1 следующую табл. 3.7.

Таблица 3.7

Нулевая строка в табл. 3.7 указывает на то, что признак оптимальности решения задачи не выполнен, и промежуточное решение X 1 = (0; 2; -1; 0) является недопустимым. Далее задачу можно решать двухэтапным симплекс-методом, методом больших штрафов и другими . Рассмотрим двухэтапный симплекс-метод .

1. Вводим дополнительно по одной переменной, делая их базисными, в те уравнения, в которых не выполнялись условия допустимости. В нашем случае вводим переменную х 5 в строку (1), прежде изменив знаки на противоположные (табл. 3.8), и столбец под х 5:

3/2 х 1 - х 3 - х 4 + х 5 = 1.

2. Вводим новую (фиктивную) целевую функцию W как сумму вновь вводимых дополнительных переменных, выраженную через небазисные переменные. В нашем случае W = х 5 = 1 - 3/2 x 1 + х 3 + х 4 . Вносим дополнительно строку (3) в табл. 3.8 с фиктивной целевой функцией -W - 3/2 х 1 + х 3 + х 4 = -1.

3. Применяем прямой симплекс-метод для минимизации фиктивной целевой W с пересчетом всех коэффициентов. Первый этап заканчивается, если фиктивная целевая функция W обратится в нуль W = 0, а следовательно, и дополнительные переменные тоже будут с нулевыми значениями. Далее строка с фиктивной целевой функцией и столбцы с дополнительными переменными не рассматриваются. Если в результате минимизации целевой W получим оптимальное значение W , отличное от нуля W ≠ 0, то это будет означать, что исходная ЗЛП не имеет допустимых решений.

Применяем прямой симплекс-метод для оптимизации основной

целевой функции Z . Включаем в базис переменную х 3 вместо переменной х 2 . Делаем пересчет коэффициентов на итерации 3 и получаем оптимальное решение: X* = (1; 0; 1/2; 0;); Z (X*) = -z" = -1.

Таблица 3.8

50 :: 51 :: 52 :: 53 :: 54 :: 55 :: 56 :: 57 :: 58 :: 59 :: 60 :: 61 :: Содержание

61 :: 62 :: 63 :: 64 :: 65 :: 66 :: 67 :: 68 :: 69 :: 70 :: Содержание

3.2.4. Анализ модели задачи линейного программирования

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

Рассмотрим задачу линейного программирования (3.20)-(3.22) на примере задачи использования ресурсов. Если для этой исходной ЗЛП (назовем ее прямой) ввести переменные y i для оценки ресурсных ограничений (3.21) и сделать переход к математической постановке другой задачи (двойственной или обратной) вида (3.23)-(3.25), то решения прямой и двойственной задач будут находиться во взаимной зависимости, выраженной через соответствующие теоремы двойственности .

Очевидно, задача, двойственная двойственной, совпадает с исходной. Поэтому нет разницы, какую принять в качестве прямой, а какую - двойственной. Говорят о паре взаимно двойственных задач.

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

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

Скачать заметку в формате , рисунки в формате

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

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

Рассмотрим пример построения математической модели линейного программирования

Николай Кузнецов управляет небольшим механическим заводом. В будущем месяце он планирует изготавливать два продукта (А и В), по которым удельная маржинальная прибыль оценивается в 2500 и 3500 руб., соответственно.

Изготовление обоих продуктов требует затрат на машинную обработку, сырье и труд (рис. 1). На изготовление каждой единицы продукта А отводится 3 часа машинной обработки, 16 единиц сырья и 6 единиц труда. Соответствующие требования к единице продукта В составляют 10, 4 и 6. Николай прогнозирует, что в следующем месяце он может предоставить 330 часов машинной обработки, 400 единиц сырья и 240 единиц труда. Технология производственного процесса такова, что не менее 12 единиц продукта В необходимо изготавливать в каждый конкретный месяц.

Рис. 1. Использование и предоставление ресурсов

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

Линейная модель может быть построена в четыре этапа.

Этап 1. Определение переменных

Существует целевая переменная (обозначим её Z), которую необходимо оптимизировать, то есть максимизировать или минимизировать (например, прибыль, выручка или расходы). Николай стремится максимизировать маржинальную прибыль, следовательно, целевая переменная:

Z = суммарная маржинальная прибыль (в рублях), полученная в следующем месяце в результате производства продуктов А и В.

Существует ряд неизвестных искомых переменных (обозначим их х 1 , х 2 , х 3 и пр.), чьи значения необходимо определить для получения оптимальной величины целевой функции, которая, в нашем случае является суммарной маржинальной прибылью. Эта маржинальная прибыль зависит от количества произведенных продуктов А и В. Значения этих величин необходимо рассчитать, и поэтому они представляют собой искомые переменные в модели. Итак, обозначим:

х 1 = количество единиц продукта А, произведенных в следующем месяце.

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

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

Этап. 2. Построение целевой функции

Целевая функция – это линейное уравнение, которое должно быть или максимизировано или минимизировано. Оно содержит целевую переменную, выраженную с помощью искомых переменных, то есть Z выраженную через х 1 , х 2 … в виде линейного уравнения.

В нашем примере каждый изготовленный продукт А приносит 2500 руб. маржинальной прибыли, а при изготовлении х 1 единиц продукта А, маржинальная прибыль составит 2500 * х 1 . Аналогично маржинальная прибыль от изготовления х 2 единиц продукта В составит 3500 * х 2 . Таким образом, суммарная маржинальная прибыль, полученная в следующем месяце за счет производства х 1 единиц продукта А и х 2 единиц продукта В, то есть, целевая переменная Z составит:

Z = 2500 * х 1 + 3500 *х 2

Николай стремится максимизировать этот показатель. Таким образом, целевая функция в нашей модели:

Максимизировать Z = 2500 * х 1 + 3500 *х 2

Этап. 3. Определение ограничений

Ограничения – это система линейных уравнений и/или неравенств, которые ограничивают величины искомых переменных. Они математически отражают доступность ресурсов, технологические факторы, условия маркетинга и иные требования. Ограничения могут быть трех видов: «меньше или равно», «больше или равно», «строго равно».

В нашем примере для производства продуктов А и В необходимо время машинной обработки, сырье и труд, и доступность этих ресурсов ограничена. Объемы производства этих двух продуктов (то есть значения х 1 их 2) будут, таким образом, ограничены тем, что количество ресурсов, необходимых в производственном процессе, не может превышать имеющееся в наличии. Рассмотрим ситуацию со временем машинной обработки. Изготовление каждой единицы продукта А требует трех часов машинной обработки, и если изготовлено х 1 , единиц, то будет потрачено З * х 1 , часов этого ресурса. Изготовление каждой единицы продукта В требует 10 часов и, следовательно, если произведено х 2 продуктов, то потребуется 10 * х 2 часов. Таким образом, общий объем машинного времени, необходимого для производства х 1 единиц продукта А и х 2 единиц продукта В, составляет 3 * х 1 + 10 * х 2 . Это общее значение машинного времени не может превышать 330 часов. Математически это записывается следующим образом:

3 * х 1 + 10 * х 2 ≤ 330

Аналогичные соображения применяются к сырью и труду, что позволяет записать еще два ограничения:

16 * х 1 + 4 * х 2 ≤ 400

6 * х 1 + 6 * х 2 ≤ 240

Наконец следует отметить, что существует условие, согласно которому должно быть изготовлено не менее 12 единиц продукта В:

Этап 4. Запись условий неотрицательности

Искомые переменные не могут быть отрицательными числами, что необходимо записать в виде неравенств х 1 ≥ 0 и х 2 ≥ 0. В нашем примере второе условия является избыточным, так как выше было определено, что х 2 не может быть меньше 12.

Полная модель линейного программирования для производственной задачи Николая может быть записана в виде:

Максимизировать: Z = 2500 * х 1 + 3500 *х 2

При условии, что: 3 * х 1 + 10 * х 2 ≤ 330

16 * х 1 + 4 * х 2 ≤ 400

6 * х 1 + 6 * х 2 ≤ 240

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

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

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

Рис. 2. Оси графика линейного программирования

Рассмотрим, например, первое ограничение: 3 * х 1 + 10 * х 2 ≤ 330. Это неравенство описывает область, лежащую ниже прямой: 3 * х 1 + 10 * х 2 = 330. Эта прямая пересекает ось х 1 при значении х 2 = 0, то есть уравнение выглядит так: 3 * х 1 + 10 * 0 = 330, а его решение: х 1 = 330 / 3 = 110

Аналогично вычисляем точки пересечения с осями х 1 и х 2 для всех условий-ограничений:

Область допустимых значений	Граница допустимых значений	Пересечение с осью х 1	Пересечение с осью х 2
3 * х 1 + 10 * х 2 ≤ 330	3 * х 1 + 10 * х 2 = 330	х 1 = 110; х 2 = 0	х 1 = 0; х 2 = 33
16 * х 1 + 4 * х 2 ≤ 400	16 * х 1 + 4 * х 2 = 400	х 1 = 25; х 2 = 0	х 1 = 0; х 2 = 100
6 * х 1 + 6 * х 2 ≤ 240	6 * х 1 + 6 * х 2 = 240	х 1 = 40; х 2 = 0	х 1 = 0; х 2 = 40
х 2 ≥ 12	х 2 = 12	не пересекает; идет параллельно оси х 1	х 1 = 0; х 2 = 12

Графически первое ограничение отражено на рис. 3.

Рис. 3. Построение области допустимых решений для первого ограничения

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

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

Рис. 4. Область допустимых решений для модели в целом

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

Z = 2500 * х 1 + 3500 *х 2

разделим (или умножим) коэффициенты перед х 1 и х 2 на одно и тоже число, так чтобы получившиеся значения попали в диапазон, отражаемый на графике; в нашем случае такой диапазон – от 0 до 120; поэтому коэффициенты можно разделить на 100 (или 50):

Z = 25х 1 + 35х 2

затем присвоим Z значение равное произведению коэффициентов перед х 1 и х 2 (25 * 35 = 875):

875 = 25х 1 + 35х 2

и, наконец, найдем точки пересечения прямой с осями х 1 и х 2:

Нанесем это целевое уравнение на график аналогично ограничениям (рис. 5):

Рис. 5. Нанесение целевой функции (черная пунктирная линия) на область допустимых решений

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

Рис. 6. Линия целевой функции достигла максимума в пределах области допустимых решений (в точке С)

Можно сделать вывод, что оптимальное решение будет находиться в одной из крайних точек области принятия решения. В какой именно, будет зависеть от угла наклона целевой функции и от того, какую задачу мы решаем: максимизации или минимизации. Таким образом, не обязательно чертить целевую функцию – все, что необходимо, это определить значения х 1 и х 2 в каждой из крайних точек путем считывания с диаграммы или путем решения соответствующей пары уравнений. Найденные значения х 1 и х 2 затем подставляются в целевую функцию для расчета соответствующей величины Z. Оптимальным решением является то, при котором получена максимальная величина Z при решении задачи максимизации, и минимальная – при решении задачи минимизации.

Определим, например значения х 1 и х 2 в точке С. Заметим, что точка С находится на пересечении линий: 3х 1 + 10х 2 = 330 и 6х 1 + 6х 2 = 240. Решение этой системы уравнений дает: х 1 = 10, х 2 = 30. Результаты расчета для всех вершин области допустимых решений приведены в таблице:

Точка	Значение х 1	Значение х 2	Z = 2500х 1 + 3500х 2
А	22	12	97 000
В	20	20	120 000
С	10	30	130 000
D	0	33	115 500
E	0	12	42 000

Таким образом, Николай Кузнецом должен запланировать на следующий месяц производство 10 изделий А и 30 изделий В, что позволит ему получить маржинальную прибыль в размере 130 тыс. руб.

Кратко суть графического метода решения задач линейного программирования можно изложить следующим образом:

Начертите на графике две оси, представляющие собою два параметра решения; нарисуйте только I-й квадрант.
Определите координаты точек пересечения всех граничных условий с осями, подставляя в уравнения граничных условий поочередно значения х 1 = 0 и х 2 = 0.
Нанести линии ограничений модели на график.
Определите на графике область (называемую допустимой областью принятия решения), которая соответствует всем ограничениям. Если такая область отсутствует, значит, модель не имеет решения.
Определите значения искомых переменных в крайних точках области принятия решения, и в каждом случае рассчитайте соответствующее значение целевой переменной Z.
Для задач максимизации решение – точка, в которой Z максимально, для задач минимизации, решение – точка, в которой Z минимально.

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

Целевая функция – есть обобщенный показатель системы, который характеризует степень достижения системой ее цели. Составление целевой функции одна из важнейших задач при проектировании системы. Однако нет общей теории построения целевых функций, есть только некоторые рекомендации.

Целевая функция составляется по указаниям ТЗ о критерии оптимизации путем анализа внешних параметров системы и ограничений на них.

Целевая функция должна существенно зависеть от внешних параметров или части их. В противном случае оптимизация по данной целевой функции не имеет смысла. Целевая функция представляет вектор в m -мерном пространстве внешних параметров системы

Обычно целевая функция задается в скалярном виде.

Используются следующие четыре формы целевой функции.

1. Наиболее часто используется целевая функция одного внешнего параметра

В этом случае целевая функция просто равна одному из внешних параметров или его обратной величине

Все остальные (m – 1) внешних параметров переводятся в систему ограничений.

Физический смысл целевой функции приведенных видов заключается в том, что чем больше (или меньше) параметр y i , тем лучше при прочих равных условиях данная система, причем равенство прочих условий понимается в смысле ограничений на остальные внешние параметры. Типичные задачи с приведенной формой целевой функции: оптимизация системы по надежности (y = P (t )), помехоустойчивости, стоимости и другим внешним параметрам. Такая целевая функция имеет ясный физический (технический или экономический) смысл, объективно характеризует систему и поэтому часто используется. То есть в этом случае целевой функцией является внешний параметр системы. Он и называется целевой функцией системы. Это могут быть: точность, быстродействие, время, стоимость, надежность, масса, габариты, какой-то технологический показатель и т.п.

2. Вторая форма целевой функции – это сумма параметров одной размерности или сумма функций от этих параметров

Такая форма характерна при оптимизации по экономическим критериям, по критериям сложности и т.п.

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

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

3. Третья форма целевой функции – ранжированная форма – представляет собой упорядоченную совокупность целевых функций первой формы с приоритетами

Первая целевая функция наиболее важная, последняя целевая функция наименее важная.

В частном случае целевая функция этого вида записывается так:

Пример ранжирования – это (например) такая последовательность целевых функций: точность, надежность, стоимость. Смысл целевой функции третьей формы состоит в следующем. Самым главным – первым по рангу – признается некоторый i -й параметр системы – y i (например, точность). Если у некоторой системы этот i -ый параметр больше, чем у всех других систем, то независимо от значений других параметров (если только они удовлетворяют ограничениям) данная система считается лучшей. Затем по второму параметру и т.д.

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

4. Четвертая – наиболее общая – форма целевой функции представляет собой произвольную зависимость от всех или части (но не меньше двух) разнородных внешних параметров

При этом разнородные параметры преобразуются в безразмерные (или одноразмерные) и целевая функция формируется как некоторая композиция (например, среднее арифметическое) полученных безразмерных показателей.

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

где F S (y i ) – одна из k целевых функций третьей формы;

ω S – ее весовой коэффициент.

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

Экстремальное значение полученной суммы будет считаться оптимальным.

Таким образом, можно указать, что в большинстве случаев (1-я и 3-я формы) показатели качества системы оцениваются численными значениями компонентов векторной целевой функции, которые носят названия функционалов :

- - - - - - - - - - - - - - - - - -

Так как системы работают в условиях случайных воздействий, то значения функционалов часто оказываются случайными величинами. Это неудобно при использовании функционалов в виде показателей качества. Поэтому в таких случаях обычно пользуются средними значениями соответствующих функционалов. Например: среднее количество изделий, выпускаемых за смену; средняя стоимость продукции и т.д.

В некоторых случаях показатели качества представляют собой вероятности некоторых случайных событий. При этом в качестве целевой функции выбирается вероятность
выполнения системой поставленной цели (задачи)

Например, вероятность обнаружения цели радиолокатором и т.п.

Целевая функция – это математическое представление зависимости критерия оптимальности от искомых переменных.

2. Градиент функции.

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

называется градиентом функции , вычисленным в точке.

3. Общая задача линейного программирования.

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

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

где - заданные числа.

4. Стандартная задача лп.

В стандартной форме задача линейного программирования является задачей на максимум (минимум) линейной целевой функции. Система ограничений ее состоит из одних линейных неравенств типа « <= » или « >= ». Все переменные задачи неотрицательны.

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

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

2 вариант ответа:

Стандартная задача ЛП. или, в матричной записи,где- матрица коэффициентов. Векторназывается вектором коэффициентов линейной формы,- вектором ограничений.

5. Каноническая задача лп.

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

К канонической форме можно преобразовать любую задачу линейного программирования.

Короткая запись канонической задачи ЛП:

Х=(х1, х2, …, хn), С=(с1, с2, …, сn).

2 вариант ответа:

Каноническая задача ЛП. или, в матричной записи,

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

Двойственная задача линейного программирования. Рассмотрим задачу ЛП (1) или, в матричной записи,(2) Задачей, двойственной к (1) (двойственной задачей), называется задача ЛП отпеременныхвида(3) или, в матричной записи,(4) где. Правила построения задачи (3) по форме записи задачи (1) таковы: в задаче (3)

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

Симметричные двойственные задачи

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