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

Cтраница 2

Из таблицы видно, что для сравнительно близких оптимальных значений целевой функции (f (z) (при отклонениях порядка 1 %) количество изделий, подлежащих выпуску по этим оптимальным планам, по отдельным наименованиям колеблется в пределах нескольких сотен. Таким образом, эта задача является неустойчивой.  

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

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

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

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

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

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

В начале любой итерации t известна верхняя оценка х оптимального значения целевой функции. Значение х определяется общепринятым способом. Кроме того, задан основной список задач, содержащий некоторое подмножество Xij 1, определяющее частичный цикл, и подмножество значений с - -, принятых в результате пересмотра равными оо. Для вычисления нижней оценки оптимального значения целевой функции, соответствующей циклу, который является дополнением частичного цикла, можно применить тот же метод, что и в алгоритме задания маршрутов. С другой стороны, можно определять оптимальное решение задачи о назначениях, включив в эту задачу коэффициенты с -, принадлежащие строкам и столбцам, не связанным с подмножеством xti 1, которые входят в частичный цикл.  

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

Теорема 4.1. Последовательность Q (Xh) сходится к оптимальному значению целевой функции детерминированной задачи, эквивалентной двухэтапной стохастической задаче линейного программирования. Последовательность лг / J содержит сходящуюся подпоследовательность. Каждая сходящаяся подпоследовательность из Xh сходится к оптимальному предварительному плану х двухэташюй стохастической задачи.  

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

В начале любой итерации t известна верхняя оценка х а оптимального значения целевой функции.  

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

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

Для нахождения максимума целевой функции используйте функцию maximize, формат которой следующий maximize(<функция>, <система ограничений>, <опции>);

При этом условие неотрицательности переменных удобно указать опцией NONNEGATIVE.

> optimum:=maximize(f,syst_ogr,NONNEGATIVE);

Используйте команду subs, которая позволяет подставить значения переменных x 1 и x 2 в функцию f .

> fmax:=subs(x1=83/17,x2=19/17,f);

Примените функцию evalf для представления ответа в форме действительного числа с 4 значащими цифрами.

> fmax:=evalf(fmax,4);

Ознакомиться с вариантом решения задачи ЛП без пояснений можно в приложении.

Решение оптимизационных задач в специализированном пакете SimplexWin. Http://www.Simplexwin.Narod.Ru/

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

Задача . Найти значения переменных x 1 и x 2 , при которых

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

Порядок выполнения работы :

Запустите программу SimplexWin и установите требуемый размер матрицы ограничений, выбрав в меню команду Настройки – Размер матрицы (рис. 13).

Рис. 13 . Определение размера матрицы.

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

Рис.14 . Ввод данных.

II. Нахождение оптимального плана и оптимального значения целевой функции.

Рис. 15 . Форма Результаты.

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

Рис. 16 . Решение задачи.

Решение оптимизационных задач в Excel

Рассмотрим пример нахождения для следующей задачи линейного программирования.

Задача . Найти значения переменных x 1 и x 2 , при которых

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

Порядок выполнения работы :

I. Оформление исходных данных.

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

Рис. 17 . Экранная форма задачи (курсор в ячейке D6).

Замечание : В экранной форме на рис. 17 каждой переменной и каждому коэффициенту задачи поставлена в соответствие конкретная ячейка в Excel. Так, например, переменным задачи соответствуют ячейки B3 (), C3 (),коэффициентам целевой функции соответствуют ячейки B6 (
), C6 (
), правым частям ограничений соответствуют ячейки F10 (
), F11 (
),F12 (
)и т.д.

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

Согласно условию задачи значение целевой функции определяется выражением
. Используя обозначения соответствующих ячеек вExcel, формулу для расчета целевой функции можно записать как сумму произведений каждой из ячеек, отведенных для значений переменных задачи (B3, C3), на соответствующие ячейки, отведенные для коэффициентов целевой функции (B6, C6).

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

– поставьте курсор в ячейку D6 ;

– вызовите окно Мастер функций – шаг 1 из 2 , нажав кнопку на стандартной панели инструментов;

– в окне Функция выберите функцию СУММПРОИЗВ ;

– в появившемся окне СУММПРОИЗВ в строку Массив 1 введите выражение B$3:C$3 , а в строку Массив 2 – выражение B6 :С6 ;

– нажмите кнопку OK .

Рис. 18 . Ввод формулы для расчета ЦФ в окне Мастер функций.

После ввода ячеек в строки Массив 1 и Массив 2 в окне СУММПРОИЗВ появятся числовые значения введенных массивов (рис. 18), а в экранной форме появится текущее значение, вычисленное по введенной формуле, то есть 0 (так как в момент ввода формулы значения переменных задачи нулевые) (рис. 19).

Замечание : Символ $ перед номером строки означает, что при копировании этой формулы в другие места листа Excel номер строки 3 не изменится. Символ : означает, что в формуле использованы все ячейки, расположенные между ячейками, указанными слева и справа от двоеточия.

Левые части ограничений задачи представляют собой сумму произведений каждой из ячеек, отведенных для значений переменных задачи (B3, C3), на соответствующую ячейку, отведенную для коэффициентов конкретного ограничения (B10, C10 – 1 ограничение; B11, C11 – 2 ограничение; B12, C12 – 3 ограничение).

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

Для расчета значений левых частей ограничений выполните следующее:

– поставьте курсор в ячейку D6 и скопируйте в буфер содержимое ячейки (клавишами Ctrl+C);

– поставьте курсор поочередно в поля левой части каждого из ограничений, то есть D 10 ,D 11 , D 12 , и вставляйте в эти поля содержимое буфера (клавишами Ctrl+V) (при этом номер ячеек во втором массиве формулы будет меняться на номер той строки, в которую была произведена вставка из буфера).

После ввода на экране в полях D 10 ,D 11 , D 12 появится 0 (нулевое значение) (рис. 19).

Рис. 19 . Экранная форма задачи после вода

всех необходимых формул.

Проверьте правильность введения формул.

Для этого:

– произведите поочередно двойное нажатие левой клавиши мыши на ячейки с формулами, при этом на экране рамкой будут выделяться ячейки, используемые в формуле (рис. 20 и рис. 21).

Рис. 20

формулы в целевую ячейку D6.

Рис. 20 . Проверка правильности введения

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

Задайте целевую функцию и введите ограничения в окне Поиск решения (рис. 21).

Для этого:

– поставьте курсор в ячейку D6 ;

– вызовите окно Поиск решения , выбрав на панели инструментов Данные – Поиск решения ;

– поставьте курсор в поле Установить целевую ячейку ;

– введите адрес целевой ячейки $D$6 или сделайте одно нажатие левой клавишей мыши на целевую ячейку в экранной форме, что будет равносильно вводу адреса с клавиатуры;

– укажите направление оптимизации целевой функции, щелкнув один раз левой клавишей мыши по селекторной кнопке максимальному значению ;

– в окне Поиск решений в поле Изменяя ячейки введите ячейки со значениями переменных $B$3:$C$3 , выделив их в экранной форме, удерживая левую кнопку мыши;

Рис. 21 . Окно Поиск решения.

– нажмите кнопку Добавить ;

– в соответствии с условием задачи выберите в поле знака необходимый знак, например, для 1 ограничения это знак ;

– в поле Ограничение введите адрес ячейки правой части, рассматриваемого ограничения, например $F$10 ;

– аналогичным образом установите соотношения между правыми и левыми частями других ограничений ($D$ 11$F$1 1 , $D$ 12$F$1 2) ;

– подтвердите ввод всех перечисленных условий нажатием кнопки OK (рис. 22 и рис. 23).

Рис. 22 . Добавления условия.

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

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

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) допустимы, то они обе имеют решение и одинаковое значение .

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

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

Переменные задачи

Построим модель задачи.

Решение

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

1) Что является искомыми величинами задачи?

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

3) Какие условия в отношении искомых величин и ресурсов задачи должны быть выполнены?

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

Только после экономического ответа на всœе эти вопросы можно приступать к записи этих ответов в математическом виде, ᴛ.ᴇ. к записи математической модели.

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

x1 – суточный объём производства краски 1-го вида, [т краски/сутки];

x2 – суточный объём производства краски 2-го вида, [т краски/сутки].

В условии задачи сформулирована цель – добиться максимального дохода от реализации продукции. Т.е. критерием эффективности служит параметр суточного дохода, который должен стремиться к максимуму. Чтобы рассчитать величину суточного дохода от продажи красок обоих видов, крайне важно знать объёмы производства красок, ᴛ.ᴇ. x1 и x2 т краски в сутки, а также оптовые цены на краски 1-го и 2-го видов – согласно условию, соответственно 3 и 2 тыс. руб. за 1 т краски. Τᴀᴋᴎᴍ ᴏϬᴩᴀᴈᴏᴍ, доход от продажи суточного объёма производства краски 1-го вида равен 3 x 1 тыс. руб. в сутки, а от продажи краски 2-го вида – 2x 2 тыс. руб. в сутки. По этой причине запишем целœевую функцию в виде суммы дохода от продажи красок 1-го и 2-го видов (при допущении независимости объёмов сбыта каждой из красок)

Целевая функция - понятие и виды. Классификация и особенности категории "Целевая функция" 2017, 2018.

- Основные понятия. Критерии эффективности. Целевая функция

ГЛАВА 16. ЭФФЕКТИВНОСТЬ МЕНЕДЖМЕНТА КОНТРОЛЬНЫЕ ВОПРОСЫ 1. Чем вызвана необходимость внешнеэкономической деятельности предприятия? 2. Что благоприятствует внешнеэкономической деятельности предприятия? 3. Что является препятствием для... .

- В нашем примере целевая функция имеет вид

F(X) = 75X1 + 800/X1 + 78X2 + 1600/X2 . Функция выпукла, если F"(x)>0 для любого x. Проверим: ; ; ; . Значит, функция выпукла, поскольку "x>0. Следовательно, выбор оптимального числа поездов на двух участках оказывается задачей выпуклого программирования, которая может быть решена... .

- Целевая функция потребления и моделирование поведения потребителей

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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