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

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

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

27 августа 2017 в 14:20

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

Введение

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

Постановка задачи

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

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

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

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

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

Учитывая высокий уровень математической подготовки подавляющего большинства пользователей данного ресурса не стану приводить балансовые уравнения с верхними и нижними ограничениями и введением для перехода к равенствам дополнительных переменных. Поэтому сразу приведу обозначения используемых в решении переменных:
N – количество видов производимых изделий;
m– количество видов используемого сырья;
b_ub - вектор имеющихся ресурсов размерности m;
A_ub – матрица размерности m×N, каждый элемент которой является расходом ресурса вида i на производство единицы изделия вида j;
с - вектор прибыли от производства единицы изделия каждого вида;
x – искомые объёмы производимых изделий каждого вида (оптимальный план производства) обеспечивающие максимальную прибыль.

Функция цели
maxF(x)=c×x

Ограничения
A×x≤b

Численные значения переменных:
N=5; m=4; b_ub = ; A_ub = [, , ,]; c = .

Задачи
1.Найти x для обеспечения максимальной прибыли
2. Найти использованные ресурсы при выполнении п.1
3. Найти остатки ресурсов (если они есть) при выполнении п.1

Для определения максимума (по умолчанию определяется минимум коэффициенты целевой функции нужно записать с отрицательным знаком c = [-25, -35,-25,-40,-30] и проигнорировать знак минус перед прибылью.

Используемые при выводе результатов обозначения:
x – массив значений переменных, доставляющих минимум (максимум) целевой функции;
slack – значения дополнительных переменных. Каждая переменная соответствует ограничению-неравенству. Нулевое значение переменной означает, что соответствующее ограничение активно;
success – True, если функции удалось найти оптимальное решение;
status – статус решения:
0 – поиск оптимального решения завершился успешно;
1 – достигнут лимит на число итераций;
2 – задача не имеет решений;
3 – целевая функция не ограничена.
nit – количество произведенных итераций.

Листинг решения прямой задачи оптимизации

#!/usr/bin/python # -*- coding: utf-8 -*- import scipy from scipy.optimize import linprog # загрузка библиотеки ЛП c = [-25, -35,-25,-40,-30] # список коэффициентов функции цели b_ub = # список объёмов ресурсов A_ub = [, # матрица удельных значений ресурсов , , ] d=linprog(c, A_ub, b_ub) # поиск решения for key,val in d.items(): print(key,val) # вывод решения if key=="x": q=#использованные ресурсы print("A_ub*x",q) q1= scipy.array(b_ub)-scipy.array(q) #остатки ресурсов print("b_ub-A_ub*x", q1)

Результаты решения задачи
nit 3
status 0

success True
x [ 0. 0. 18.18181818 22.72727273 150. ]
A_ub*x
b_ub-A_ub*x [ 0. 0. 0. 90.90909091]
fun -5863.63636364
slack [ 0. 0. 0. 90.90909091]

Выводы

1. Найден оптимальный план по видам продукции
2. Найдено фактическое использование ресурсов
3. Найден остаток не использованного четвёртого вида ресурса [ 0. 0 0.0 0.0 90.909]
4. Нет необходимости в вычислениях по п.3, так как тот же результат выводить в переменной slack

Решение двойственной задачи о оптимальной производственной программе

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

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

C – вектор имеющихся ресурсов;
b_ub – вектор прибыли от производства единицы изделия каждого вида;
A_ub_T– транспонированная матрица A_ub.

Функция цели
minF(x)=c×x

Ограничения
A_ub_T ×x≥ b_ub

Численные значения и соотношения для переменных:
с = ; A_ub_T transpose(A_ub); b_ub = .

Задача:
Найти x показывающий ценность для производителя каждого вида ресурсов.

Особенности решения с библиотекой scipy. optimize
Для замены ограничений сверху на ограничения с низу необходимо умножить на минус единицу обе части ограничения – A_ub_T ×x≥ b_ub… Для этого исходные данные записать в виде: b_ub = [-25, -35,-25,-40,-30]; A_ub_T =- scipy.transpose(A_ub).

Листинг решения двойственной задачи оптимизации

#!/usr/bin/python # -*- coding: utf-8 -*- import scipy from scipy.optimize import linprog A_ub = [, , , ] c= b_ub = [-25, -35,-25,-40,-30] A_ub_T =-scipy.transpose(A_ub) d=linprog(c, A_ub_T, b_ub) for key,val in d.items(): print(key,val)

Результаты решения задачи
nit 7
message Optimization terminated successfully.
fun 5863.63636364
x [ 2.27272727 1.81818182 6.36363636 0. ]
slack [ 5.45454545 2.27272727 0. 0. 0. ]
status 0
success True

Выводы

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

Результаты сравнения прямой и двойственной задачи

1. Двойственная задача расширяет возможности планирования выпуска продукции, но средствами scipy. optimize решается за вдвое большее чем прямая количество итераций.
2. Переменная slack выводит информацию об активности ограничений в виде неравенств, что может быть использовано, например, для анализа остатков сырья.
3. Прямая задача является задачей максимизации, а двойственная - задачей минимизации, и наоборот.
4. Коэффициенты функции цели в прямой задаче являются ограничениями в двойственной задаче.
5. Ограничения в прямой задаче становятся коэффициентами функции цели в двойственной.
6. Знаки неравенств в ограничениях меняются на противоположные.
7. Матрица системы равенств транспонируется.

Ссылки

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

Функция, связывающая цель (оптимизируемую переменную) с управляемыми переменными в задаче оптимизации.

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

См. также

• Бурак Я. И., Огирко И. В. Оптимальный нагрев цилиндрической оболочки с зависящими от температуры характеристиками материала // Мат. методы и физ.-мех. поля. - 1977. - Вып. 5. - С.26-30

Wikimedia Foundation . 2010 .

• ЦНИИ робототехники и технической кибернетики
• 1885 год в театре

Смотреть что такое "Целевая функция" в других словарях:

целевая функция - — [Я.Н.Лугинский, М.С.Фези Жилинская, Ю.С.Кабиров. Англо русский словарь по электротехнике и электроэнергетике, Москва, 1999 г.] целевая функция В экстремальных задачах — функция, минимум или максимум которой требуется найти. Это… …

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

целевая функция - 3.1.8 целевая функция (business function): Набор процессов, обеспечивающих достижение конкретной цели деятельности. Источник: Р 50.1.041 2002: Инфор … Словарь-справочник терминов нормативно-технической документации

целевая функция - tikslo funkcija statusas T sritis automatika atitikmenys: angl. objective function vok. Zielfunktion, f rus. функция цели, f; целевая функция, f pranc. fonction de cible, f … Automatikos terminų žodynas

Целевая функция - функция, экстремальное значение которой ищется на допустимом множестве в задачах математического программирования (См. Математическое программирование) … Большая советская энциклопедия

ЦЕЛЕВАЯ ФУНКЦИЯ - функция цели название оптимизируемой функции в задачах математического программирования … Математическая энциклопедия

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

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

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

целевая функция автоматизированной медицинской системы - целевая функция АМС Совокупность действий автоматизированной медицинской системы, обеспечивающая эффективное выполнение заданной медицинской программы. [ГОСТ 27878 88] Тематики системы и комплексы медицинские Обобщающие термины системы и… … Справочник технического переводчика

Книги

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

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

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

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

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

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

Рассмотрим потребителя, который в результате своего существования потребляет некоторые блага. Уровень удовлетворения потребностей потребителя обозначим через U .Предположим, что имеется n видов благ Б 1 , Б 2 ,…, Б n . В качестве благ могут выступать:

· продовольственные товары;

· товары первой необходимости;

· товары второй необходимости;

· предметы роскоши;

· платные услуги и т. д.

Пусть количество потребления каждого блага равно х 1 , х 2 ,…, х n . Целевой функцией потребления называется зависимость между степенью (уровнем) удовлетворения потребностей U и количеством потребляемых благ: х 1 , х 2 , …, х n . Эта функция имеет вид .

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

Пример 6.3 . Целевая функция потребления имеет вид . Найти кривые безразличия.

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

Каждый потребитель стремится максимизировать уровень удовлетворения потребностей, то есть . Однако максимизации степени удовлетворения потребностей будут мешать возможности потребителя. Обозначим цену на единицу каждого блага через р 1 , р 2 ,…, р n , а доход потребителя через D .Тогда должно выполняться бюджетное ограничение , имеющее смысл закона, согласно которому затраты потребителя не должны превышать сумму дохода:

В результате для нахождения оптимального набора благ необходимо решать задачу оптимального программирования:

(6.3)

Рассмотрим двухфакторную функцию потребления , где х 1 - объем потребления продуктов питания и х 2 - потребление непродовольственных товаров и платных услуг. Кроме того, предположим, что весь доход потребитель направляет на удовлетворение своих потребностей. В этом случае бюджетное ограничение будет содержать только два слагаемых, и неравенство превратится в равенство. Задача оптимального программирования при этом примет вид:

(6.4)

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

х 2

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

Пример 6.4 . Целевая функция потребления имеет вид . Цена на благо Б 1 равна 20, цена на благо Б 2 равна 50. Доход потребителя составляет 1800 единиц. Найти кривые безразличия, оптимальный набор благ потребителя, функцию спроса на первое благо по цене, функцию спроса на первое благо по доходу.

Решение. Кривые безразличия имеют вид:

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

Находим оптимальный набор благ. Задача оптимального программирования имеет вид:

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

Находим производную и приравниваем ее к нулю

Получаем .

Таким образом, оптимальный набор благ составляют 30,5 и 23,8 единиц. Находим теперь функцию спроса на первое благо по цене на него. Для этого в бюджетном ограничении вместо фиксированного значения вводим цену первого блага , получая уравнение: . Выражаем

или , откуда находим функцию спроса на первое благо по цене: .

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

Находим производную и приравниваем ее к нулю:

Отсюда находим функцию спроса на первое благо по доходу

7. Модель
межотраслевого баланса

Балансовые модели предназначены для анализа и планирования производства и распределения продукции на различных уровнях - от отдельного предприятия до народного хозяйства в целом. Если вспомнить историю народного хозяйства как Советского Союза и России, так и других развитых стран, то можно наблюдать, что в экономике многих государств в разное время случались экономические кризисы разных крайностей от кризисов перепроизводства (США, середина ХХ века), до дефицита (Россия, конец ХХ века). Все эти экономические кризисы связаны с нарушением баланса между производством и потреблением. Из этих фактов видно, что баланс между произведенной продукцией и потреблением является важным критерием как для макроэкономики, так и для микроэкономики.

Экономико-математические модели баланса пытались выстроить многие экономисты и математики с самого начала возникновения проблемы, однако, наиболее полную балансовую модель удалось построить в 1936 г. американским экономистом В. Леонтьевым (который после революции эмигрировал в США и за свою модель получил Нобелевскую премию в области экономики). Эта модель позволяла рассчитать баланс между несколькими взаимодействующими отраслями, хотя ее можно легко обобщить и для организаций микроэкономики, например, для вычисления баланса между несколькими взаимодействующими предприятиями или между подразделениями одного предприятия (например, цехами одного завода).

Цель балансового анализа - ответить на вопрос, возникающий в макроэкономике и связанный с эффективностью ведения многоотраслевого хозяйства: каким должен быть объем производства каждой из п отраслей, чтобы удовлетворить все потребности в продукции этой отрасли? При этом каждая отрасль выступает, с одной стороны, как производитель некоторой продукции; а с другой - как потребитель продукции и своей, и произведенной другими отраслями.

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

Рассмотрим процесс производства за некоторый период времени (например, год). Так как валовой объем продукции любой i -й отрасли равен суммарному объему продукции, потребляемой n отраслями, и конечного продукта, то уравнение баланса между производством и потреблением будет иметь вид

, (i = 1, 2, …, n ). (7.1)

Уравнения (7.1) называются соотношениями баланса.

. (7.2)

Все ранее рассмотренные показатели можно записать в основную балансовую таблицу:

Отрасль	Потребление отраслей,	Конечный продукт,	Валовойпродукт,
		…	n
			…
			…
…		…			…	…
n			…
Чистый продукт			…

В результате основная балансовая таблица содержит четыре матрицы: матрицу межотраслевых производственных связей

; матрицу валовой продукции ; матрицу конечной продукции и матрицу чистой продукции .

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

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

. (7.4)

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

Из последнего выражения можно найти значение конечного продукта при известном значении валового

где - единичная матрица того же размера, что и А .

Пример 7.1 . Баланс четырех отраслей за предыдущий период имеет матрицу межотраслевых производственных связей вида и матрицу валовой продукции вида . Необходимо определить конечный продукт Y и чистый продукт C каждой отрасли.

Конечный продукт Y получается в результате вычитания из каждого элемента матрицы валовой продукции суммы элементов соответствующих строк матрицы . Например, первое значение равно 100 – (10 + 20 + 15 + 10) = 45. Чистый продукт С получается в результате вычитания из каждого элемента матрицы валовой продукции Х суммы элементов соответствующих столбцов матрицы . Например, первое значение равно 100 – (10 + 5 + 25 + 20) = 40. В результате получим основную балансовую таблицу:

Отрасль	Потребление отраслей,	Конечный продукт,	Валовойпродукт,
Чистый продукт,					S = 210	S = 400

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

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

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

Можно выделить следующие причины, по которым экономические системы являются стохастическими:

1) система сложная, многокритериальная, описывается многоуровневой иерархической структурой;

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

3) преднамеренное искажение информации, сокрытие информации и целенаправленная экономическая диверсия.

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

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

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