Государственное образовательное учреждение высшего

профессионального образования

"Московский государственный технический университет им. Н.Э. Баумана"

Калужский филиал

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

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

Теоретическая часть.

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

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

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

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

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

,

Ограничения:

1. Правые части всех ограничений должны быть неотрицательными . Если какой-нибудь из коэффициентов < 0, то необходимо коэффициенты ограничения слева и справа домножить на "-1" и изменить знак данного ограничения на противоположный;

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

Если исходные ограничения определяют расход некоторого ресурса (знак ""), то переменные следует интерпретировать как остаток, или неиспользованную часть ресурса. В этом случае – остаточная переменная и вводится в уравнение со знаком "+".

Если исходные ограничения определяют избыток некоторого ресурса (знак ""), то вводится избыточная переменная знаком "-".

Переменные:

Все переменные должны быть неотрицательными, т.е. .

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

Если такая переменная попадает в оптимальное решение, то

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

Подлежит максимизации или минимизации.

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

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

(1)

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

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

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

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

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

Первый шаг при использовании графического метода заключается в геометрическом представлении допустимых решений, т.е. построении области допустимых решений (ОДР.), в которой одновременно удовлетворяются все ограничения модели. При получении графического решения переменная откладывается по горизонтальной оси, а – по вертикальной. При формировании ОДР необходимо предотвратить получение недопустимых решений, которые связаны с необходимостью выполнения условия неотрицательности переменных. Перед построением необходимо определить квадранты, в которых будет располагаться ОДР. Квадранты определяются знаками переменных и . Условия неотрицательности переменных и ограничивают область их допустимых значений первым квадрантом. Если переменная не ограниченна в знаке, то область ограничивается первым и вторым квадрантом, если , то – первым и четвёртым квадрантом. Другие границы пространства решений на плоскости , изображены прямыми линиями, построенными по уравнениям ограничений при условии замены знака на знак "=". При этом необходимо учитывать следующее: правые части всех ограничений должны быть неотрицательными . Если какое-нибудь ограничение < 0, то необходимо коэффициенты соответствующего ограничения слева и справа до-множить на "-1" и изменить знак неравенства данного ограничения на противоположный. Области, в которых выполняются соответствующие ограничения в виде неравенств, указываются стрелками, направленными в сторону допустимых значений переменных.

В результате построений получается многоугольник, который определяет пространство решений. Если одно из ограничений имеет знак "=", то ОДР вырождается в отрезок.

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

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

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

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

Прямая задача.

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

Найти максимум (минимум) функции при условиях

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

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

Вычислительные процедуры симплекс - метода.

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

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

Обозначим: – общее количество переменных в ЗЛП, представленной в канонической форме; - количество исходных переменных; - количество ограничений, - количество дополнительных переменных, тогда .

Каждая вершина многогранника решений имеет - ненулевых переменных и () - нулевых переменных.

Ненулевые переменные называются базисными, нулевые переменные – небазисными.

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

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

При выборе начального допустимого базиса для составления симплекс-табли-цы на первом шаге СТ(0) исходные переменные приравниваются к нулю и являются небазисными, среди введённых дополнительных переменных выбираются переменные с коэффициентами равными единице. Переменные в равенствах (2) - (4) являются базисными и в - строку входят с коэффициентами, равными 0. Для заполнения симплекс-таблицы необходимо целевую функцию преобразовать к виду . Таким образом, окончательно получаем:

При составлении симплекс-таблицы придерживаются следующих правил:

в крайнем левом столбце располагаются базисные переменные и ;

в крайнем правом столбце располагаются правые части ограничений;

в первой строке располагаются переменные в определённом порядке:

сначала , потом небазисные переменные, базисные переменные располагаются в последних столбцах перед правой частью (ПЧ). Запишем коэффициенты в СТ(0):

							ПЧ
	1			0	0	0	0
	0			1	0	0
	0			0	1	0
	0			0	0	1

Оптимальность любой из вершин определяется коэффициентами при небазисных переменных в – строке текущей симплекс-таблицы:

Для задачи максимизации данная вершина является оптимальной, если все коэффициенты при небазисных переменных в – строке являются неотрицательными (>0);

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

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

Исключаемой переменой будет та базисная переменная, которая первой обратится в "0" при переходе в смежную вершину после ввода включаемой переменной.

Столбец включаемой переменной будем называть разрешающим столцом.

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

Пересечение разрешающего столбца и строки определяют разрешающий элемент (РЭ).

Чтобы определить исключаемую переменную необходимо:

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

выбрать из полученных отношений наименьшее.

Делить на "0" и отрицательную величину нельзя, т. к. это приводит к отсутствию пересекающейся вершины или к вершине вне ОДР.

Для перехода в смежную вершину необходимо сформировать матрицу перехода B(0), которая определит связь между СТ(0) и СТ(1): СТ(1) = В(0) СТ(0).

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

Каждый элемент j – столбца делится на РЭ и меняет знак на противоположный, кроме разрешающего элемента.

Искусственный начальный базис. М – метод.

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

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

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

Свойство М: При сложении (вычитании) с любой конечной величиной , определяющей любое значение, которое может принимать каждая из переменных исходной ЗЛП, её значение (переменной М) не меняется, а именно,

Формула (1.2), ограничений не отрицательности переменных (есть, нет) - формула (1.3) (1.1) i = 1,… m (1.2) (1.3) Алгоритм решения задач линейного программирования требует приведения их постановки в канонический вид, когда целевая функция...

Основой для решения экономических задач являются математические модели.

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

Составление математической модели включает:

• выбор переменных задачи
• составление системы ограничений
• выбор целевой функции

Переменными задачи называются величины Х1, Х2, Хn, которые полностью характеризуют экономический процесс. Обычно их записывают в виде вектора: X=(X 1 , X 2 ,...,X n).

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

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

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

Данная запись означает следующее: найти экстремум целевой функции (1) и соответствующие ему переменные X=(X 1 , X 2 ,...,X n) при условии, что эти переменные удовлетворяют системе ограничений (2) и условиям неотрицательности (3).

Допустимым решением (планом) задачи линейного программирования называется любой n-мерный вектор X=(X 1 , X 2 ,...,X n), удовлетворяющий системе ограничений и условиям неотрицательности.

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

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

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

Задача использования ресурсов (сырья)

Условие: Для изготовления n видов продукции используется m видов ресурсов. Составить математическую модель.

Известны:

• b i (i = 1,2,3,...,m) — запасы каждого i-го вида ресурса;
• a ij (i = 1,2,3,...,m; j=1,2,3,...,n) — затраты каждого i-го вида ресурса на производство единицы объема j-го вида продукции;
• c j (j = 1,2,3,...,n) — прибыль от реализации единицы объема j-го вида продукции.

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

Решение:

Введем вектор переменных X=(X 1 , X 2 ,...,X n), где x j (j = 1,2,...,n) — объем производства j-го вида продукции.

Затраты i-го вида ресурса на изготовление данного объема x j продукции равны a ij x j , поэтому ограничение на использование ресурсов на производство всех видов продукции имеет вид:
Прибыль от реализации j-го вида продукции равна c j x j , поэтому целевая функция равна:

Ответ - Математическая модель имеет вид:

Каноническая форма задачи линейного программирования

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

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

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

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

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

• А — матрица коэффициентов системы уравнений
• Х — матрица-столбец переменных задачи
• Ао — матрица-столбец правых частей системы ограничений

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

Приведение общей задачи линейного программирования к канонической форме

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

Это может быть сделано следующим образом:

Возьмем линейное неравенство a 1 x 1 +a 2 x 2 +...+a n x n ≤b и прибавим к его левой части некоторую величину x n+1 , такую, что неравенство превратилось в равенство a 1 x 1 +a 2 x 2 +...+a n x n +x n+1 =b. При этом данная величина x n+1 является неотрицательной.

Рассмотрим все на примере.

Пример 26.1

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

Решение:
Перейдем к задаче на отыскивание максимума целевой функции.
Для этого изменим знаки коэффициентов целевой функции.
Для превращения второго и третьего неравенств системы ограничений в уравнения введем неотрицательные дополнительные переменные x 4 x 5 (на математической модели эта операция отмечена буквой Д).
Переменная х 4 вводится в левую часть второго неравенства со знаком "+", так как неравенство имеет вид "≤".
Переменная x 5 вводится в левую часть третьего неравенства со знаком "-", так как неравенство имеет вид "≥".
В целевую функцию переменные x 4 x 5 вводятся с коэффициентом. равным нулю.
Записываем задачу в каноническом виде.

Лекция 2

В канонической форме

допустимым решением ЗЛП (допустимым планом ).

оптимальным решением ЗЛП.

Необходимость

Пример .

Запишем задачу в канонической форме

Особые ситуации графического решения ЗЛП

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

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

2. задача не разрешима из-за неограниченности ОДР, или – рисунок 3;

3. ОДР - единственная точка А, тогда ;

4. задача не разрешима , если ОДР есть пустая область.

А

Рисунок 2 Рисунок 3

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

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

Пример . Решить графически задачу линейного программирования (альтернативный оптимум ):

Вопросы для самоконтроля

1. Запишите задачу линейного программирования в общей форме.

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

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

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

5. Какое из решений и является «лучшим» для задачи минимизации функции , если ?

6. Какое из решений и является «лучшим» для задачи максимизации функции , если ?

7. Запишите стандартную форму математической модели задачи линейного программирования с двумя переменными.

8. Как построить полуплоскость, заданную линейным неравенством с двумя переменными ?

9. Что называется решением системы линейных неравенств с двумя переменными? Постройте на плоскости область допустимых решений такой системы линейных неравенств, которая:

1) имеет единственное решение;

2) имеет бесконечное множество решений;

3) не имеет ни одного решения.

10. Запишите для линейной функции вектор градиент, назовите вид линий уровня. Как расположены относительно друг друга градиент и линии уровня?

11. Сформулируйте алгоритм графического метода решения стандартной ЗЛП с двумя переменными.

12. Как найти координаты решения и значения , ?

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

1) достигается в единственной точке, а - на отрезке ОДР;

2) достигается в единственной точке ОДР, а .

14. Дайте геометрическую иллюстрацию ЗЛП, если она:

1) имеет единственные оптимальные решения для и ;

2) имеет множество оптимальных решений для .

Лекция 2

графический метод нахождения оптимального решения

1. Формы линейных математических моделей и их преобразование

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

3. Особые ситуации графического решения ЗЛП

4. Графическое решение экономических задач линейного программирования

Формы линейных математических моделей и их преобразование

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

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

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

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

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

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

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

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

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

Переход к канонической форме записи ЗЛП .

Пример .

Запишем задачу в канонической форме , вводя в левую часть первого неравенства системы ограничений дополнительную (балансовую) переменную со знаком «+», а в левую часть второго неравенства дополнительную переменную со знаком «минус».

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

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

Основные понятия моделирования

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

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

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

Экономика – это система общественного производства, осуществляющая собственно производство, распределение, обмен и потребление необходимых обществу материальных благ.

Соответственно, экономико-математическая модель – это выраженная в формально-математических терминах экономическая абстракция, логическая структура которой определяется как объективными свойствами предмета описания, так и субъективным целевым фактором исследования, для которого это описание предпринимается.

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

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

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

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

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

найти экстремум функции

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

при условиях неотрицательности

Введем обозначения:

Запасы i –го вида ресурса;

затраты i –го вида ресурса на производство j –го вида продукции;

прибыль от реализации единицы j –го вида продукции.

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

Компактная запись показывает, что модель общей задачи линейного программирования включает пять основных элементов:

Переменные величины, значение которых отыскивается в процессе решения задачи;

Технико-экономические коэффициенты при переменных в ограничениях;

Объем правой части неравенств, которые называют константами задачи;

Коэффициенты при переменных в целевой функции, которые называют оценками переменных;

Индекс переменной;

Индекс ограничения.

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

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

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

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

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

Дополнительные и вспомогательные переменные всегда имеют единичные коэффициенты (+1 или –1).

Технико-экономические коэффициенты (a ij) при переменных в системе ограничений выражают нормы затрат производственных ресурсов или норму выхода продукции в расчете на единицу измерения переменной величины.

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

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

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

Правой части ограничений (b i) называют константами, т.е. постоянными величинами. К ним относят объемы производственных ресурсов – земли, труда, техники, удобрений, капиталовложений и т.д. Производственные ресурсы должны быть определены с учетом их фактического состояния и обязательно учитывать период планирования. Кроме того, те производственные ресурсы, использование которых в течение года неравномерно, рассчитывают не только за год в целом, но и по отдельным напряженным периодам или месяцам (трудовые ресурсы).

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

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

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

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

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

v отражать в задаче только те условия, которые действительно ограничивают возможности производства;

v слишком большое количество ограничений увеличивает размеры задачи и делает ее трудноразрешимой

Ограничения бывают трех типов: равенства (=), неравенства типа меньше либо равно (≤), неравенства типа больше либо равно (≥). Например,

где i = 1, 2, … , m . Коэффициенты при переменных обозначаются a ij , где индекс i – номер ограничения, индекс j – номер переменной, свободные члены (правая часть ограничений) обозначаются b i , индекс i – номер ограничения.

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

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

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

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

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

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

Условие неотрицательности переменных записывается в виде

x j ≥ 0, j = 1, 2, …, n .

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

j = 1, …, n . (1.6)

Вектор x = (x 1 , x 2 , …, x n), компоненты x j которого удовлетворяют ограничениям (1.2) и (1.3) [или (1.5) и (1.6) в задаче на минимум], называется допустимым решением или допустимым планом задачи ЛП. Совокупность всех допустимых планов называется множеством допустимых планов.

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

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

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

1) если в исходной задаче требуется определить максимум линейной функции, то следует изменить знак и искать минимум этой функции;

2) если в ограничениях правая часть отрицательна, то следует умножить это ограничение на – 1;

3) если среди ограничений имеются неравенства, то путем введения дополнительных переменных неотрицательных переменных они преобразуются в равенства. Например, дополнительные переменные S j в ограничения типа меньше либо равно (£) вводятся со знаком плюс:

Дополнительные переменные S j в ограничения типа больше либо равно (≥) вводятся со знаком минус:

Для устранения отрицательности дополнительных переменных – S j вводят искусственные переменные со знаком плюс + М j c очень большими значениями.

1.

2. направления использования мат. моделей в экономике.

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

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

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

2. математическое програмирование как наука, его структура. Задачи оптимизации. Трудности применения классических методов оптимизации при решении экономических задач.

Математическое программирование – это раздел прикладной математики, который разрабатывает теоретические основы и методы решения экстремальных задач.

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

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

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

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

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

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

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

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

3. Понятие математической модели, виды мат. моделей

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

Модели делятся на:

1. линейные , в которых все зависимости описываются линейными соотношениями,

2. нелинейные , в которых имеются нелинейные соотношения;

3. стохастические , в которых учитывается случайный характер изучаемых процессов,

4. детерминированные , в которых учитываются усредненные значения всех параметров.

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

6. статические , в которых фактор времени не учитывается.

7. оптимизационные модели, в которых выбор осуществляется в зависимости от экстремизации некоторого критерия,

8. неоптимизационные , в которых критерия оптимальности нет.

9. макромодели (всего хозяйства в целом)

10. микромодели (отдельных звеньев или процессов экономики).

Виды математических моделей: линейные, нелинейные, квадратические, целочисленные, дискретные, параметрические, дробно-линейные, динамические, стохастические

4. Общая постановка задач математического програмирования.

Рассмотрим общую постановку задачи математического программирования.

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

Z = f (x1, x2, …, xn)

в заданной области изменения этих переменных

gi (x1, x2,…, xn)Ribi (i = 1, 2,…, m),

где Ri - один из знаков ≥, =, ≤.

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

Экономическая постановка:

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

Математическая постановка:

Пусть j – индекс вида продукции j = 1, n

i– индекс вида ресурсов i = 1, m

а ij – затраты сырья i -го вида на производство единицы продукции j -го вида;

Аi – заданное ограничение на имеющийся объём ресурсов i-го вида;

Рj – прибыль, получаемая от реализации единицы продукции j-го вида;

xj – объём выпускаемой продукции j-го вида.

z = Р1x 1 + Р2x 2 + … +Pnx n → max

а11x 1 + а12x 2 +…+ а1nx n ≤ A1

а21x 1 + а22x 2 +…+ а2nx n ≤ A2

…………………………….

a m1x1 + а m2x2 +…+ а m n x n ≤ Am

xj ≥ 0, j = 1, n

6. Задача о рационе. Экономическая постановка и построение математической модели задачи.

Экономическая постановка

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

Математическая постановка:

j – индекс вида кормов, j = 1, n

i – индекс вида питательных веществ, i = 1, m

Аi – необходимое суточное потребление питательного вещества i –го вида;

Сj – стоимость единицы кормов j-го вида.

Введём неизвестные переменные:

хj – суточный объём кормления животных j-м видом корма.

В терминах введённых обозначений данная задача запишется следующим

а11x1 + а12x2 +…+ а1nxn ≥ A1

а21x1 + а22x2 +…+ а2nxn ≥ A2

…………………………….

am1x1 + аm2x2 +…+ а mnxn ≥Am

xj ≥ 0, j = 1, n

7. Транспортная задача . Экономическая постановка и построение математической модели задачи.

Экономическая постановка :

Имеется m поставщиков однородной продукции и n потребителей этой продукции. Известны удельные затраты на доставку единицы продукции от каждого поставщика каждому потребителю. Запасы продукции у поставщиков ограничены. Известны так же потребности в продукции каждого потребителя.

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

Математическая постановка :

Введём обозначения заданных параметров:

j – индекс потребителей, j = 1, n

i – индекс поставщиков, i = 1, m

Аi – объём имеющейся продукции у i-го поставщика;

Вj – объём потребность в продукции j-го потребителя;

Cij – удельные затраты на перевозку единицы продукции от i-го поставщика j-му потребителю.

Введём неизвестные переменные:

хij – объём перевозки продукции от i-го поставщика j-му потребителю.

z = С11x11 + С12x12 +…+С1nx1n + С21x21 +…+ Сm(n -1)xm (n-1) + Сmnxmn → min

Ограничения задачи.

I. От каждого поставщика можно вывести продукцию не более имеющегося количества:

x11 + x12 +…+ x1n ≤ A1

x21 + x22 +…+ x2n ≤ A2 (2)

…………………….

xm1 + xm2 +…+ xmn ≤ Am

II. Потребность каждого потребителя в продукции должна быть удовле-

x11 + x21 +…+ xm1 ≥B1

x12 + x22 +…+ xm2 ≥B2

……………………. (3)

x1n + x2n +…+ xmn ≥Bn

III. Условие неотрицательности: xij ≥0, i = 1, m ; j = 1, n

Часто удобно записывать математическую постановку в свёрнутом виде:

, i = 1, m , j = 1, n

8. Задача о выборе назначениях или о назначениях. Экономическая постановка и построение математической модели задачи.

Экономическая постановка :

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

Математическая постановка .

Введём обозначения заданных параметров.

i – индекс работ, i = 1, m

j – индекс исполнителей, j = 1, n

Cij – себестоимость выполнения i-той работы j-тым исполнителем.

Введём неизвестные переменные. В данной задаче неизвестные переменные могут принимать только два значения 0 или 1. Такие переменные называются нулевыми.

1 - если за i-той работой закреплён j-тый исполнитель;

0 - в противном случае.

В терминах введённых обозначений данная задача запишется следующим образом:

z = С11x11 + С12x12 +…+С1nx1n + С21x21 …+ С(n-1)(n -1)x(n-1)(n-1) + Сnnxnn → min

I группа ограничений.

За каждой работой должен быть закреплён только один исполнитель:

x11 + x12 +…+ x1n = 1

x21 + x22 +…+ x2n = 1

……………………..

xn1 + xn2 +…+ xnn = 1

II. группа ограничений.

Каждый исполнитель может выполнить только одну работу:

x11 + x21 +…+ xn1 = 1

x12 + x22 +…+ xn2 = 1

……………………..

x1n + x2n +…+ xnn = 1

x ij = { 0,1} i = 1, n ; j = 1, n

9. Задача о раскрое материалов. Экономическая постановка и построение математической модели задачи.

Экономическая постановка .

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

Математическая постановка .

Введём обозначения:

i – индекс заготовок,

Аi – необходимое количество заготовок i-того типа;

j – индекс вариантов раскроя,

Сj –размер отходов при раскрое единицы исходного материала по варианту j;

а ij – количество заготовок i-того вида при раскрое единицы исходного материала по варианту j.

Введём обозначения неизвестных переменных.

хj- количество исходного материала раскроенного по варианту j.

В терминах введённых обозначений данная задача запишется следующим образом:

z = С1x1 + С2x2 + … +Сnxn → min

а11x1 + а12x2 +…+ а1nxn = A1

а21x1 + а22x2 +…+ а2nxn = A2

…………………………….

am1x1 + аm2x2 +…+ аmnxn =Am

xj ≥ 0, j = 1, n

Применение математических моделей позволяет экономить исходные материалы до 20 %.

Математическая модель раскроя строится в два этапа.

На первом этапе производится построение вариантов раскроя, в результате которого определяются значения количества вариантов n, количества заготовок каждого вида, получаемых при различных вариантах раскроя (аij), а так же значения отходов (Сj).

Построение вариантов раскроя единицы исходного материала осуществляется в виде следующей таблицы:

№ варианта

Заготовка i1

Заготовка i2

Заготовка im

Заготовки располагаются в порядке невозрастания их размеров. Построение вариантов осуществляется методом полного перебора.

10. Общая форма модели задач ЛП и ее особенности

Общая форма ЗЛП имеет вид:

z = С1x1 + … + Сnxn max (min)

а11 X1 + a12 X2 + … + а1n Xn R1 a1

а21 X1 + a22 X2 + … + а2n Xn R2 a2

………………………………………………….

am1 X1 + аm2 X2 +…+ аmnxn Rm am

хj ≥ 0, j = 1, k, k ≤ n

В общей форме каждый символ R1 , R2 ,…, Rm означает один из знаков: ≥, = или ≤ .

Общая форма модели задачи ЛП обладает следующими особенностями.

1. Система ограничений представлена в виде уравнений (жестких условий) и неравенств (нежестких условий).

2. Условия неотрицательности накладываются не на все переменные

3. Целевая функция стремится либо к максимуму, либо к минимуму.

11. Стандартная форма модели задач ЛП и ее особенности

Стандартная форма имеет следующий вид.

Найти максимум или минимум целевой функции z:

z = С1x1 + … + Сnxn → max (min) (1)

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

а11 Х1 + а12 Х2 + … + а1n Хn ≤ а1

а21 Х1 + а22 Х2 + … + а2n Хn ≤ а2

…………………………………………..

am1 Х1 + аm2 Х2 +… + аmn Хn ≥ аm

хj ≥ 0, j = 1, k, k ≤ n

Особенности стандартной формы модели задачи ЛП следующие:

1. система ограничений представлена в виде неравенств (нежестких условий)

2. условия неотрицательности накладываются на все переменные

3. целевая функция стремится либо к max, либо к min

12. Каноническая форма модели задач ЛП и ее особенности

Каноническая форма имеет вид:

Найти минимум целевой функции z:

z = С1x1 + … + Сnxn → min

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

а11 Х1 + а12 Х2 + … + а1n Хn = а1

а21 Х1 + а22 Х2 + … + а2nxn = а2

…………………………

am1x1 + аm2 X2 +… + аmn Xn = am

Xj ≥0, j = 1, n

Особенности канонической формы следующие:

1. Система ограничений представлена в виде уравнений (жестких условий).

2. Условия неотрицательности накладываются на все переменные

3. Целевая функция стремится к

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

13. Возможный, допустимый, оптимальный опорный план задачи, ОДЗ задачи ЛП

Определение 1. Значения неизвестных переменных, удовлетворяющие всем ограничениям задачи линейного программирования, называются допустимыми значениями переменных или планами .

Определение 2. Множество всех планов задачи линейного программирования называется областью допустимых значений переменных (ОДЗ ).

Определение 3. План задачи линейного программирования, при котором целевая функция принимает минимальное (или максимальное) значение на ОДЗ называется оптимальным .

14. Виды записей задач ЛП: развернутая, свернутая, матричная, векторная.

Модели задач ЛП могут быть записаны в различных видах.

1. Развернутый вид записи модели

Z = c1 X1 + c2 X2 + … + cn Xn → min

a11 X1 + a12 X2 + … + a1n Xn = a1,

a21 X1 + a22 X2 + … + a2n Xn = a2,

……………………………………………

a m1 X1 + am2 X2 + … + amn Xn = am,

Xj ≥ 0, j = 1, n.

2. Свернутый вид:

,

Xj ≥ 0, j = 1, n.

3. Модель задачи ЛП в матричном виде:

X ≥ 0

Где

а11 а12 … а1n X1 a1

A= a21 a22 … a2n , X= X2 , A0 = a2

… … … … … …

am1 am2 … amn X3 am

4. Модель задачи ЛП в векторном виде:

Где

Х1 a11 a12 a1n a1

Х2 , a21 , a22 , a2n , a2

… … … … …

Хn am1 am2 am2 am

15. Переход от стандартной и общей формы задач ЛП к канонической. Теорема связи

Для перехода от общей или стандартной формы к канонической используют следующие приёмы.

1. Преобразование переменных . Если какая-то переменная Xk неположительна (Xk ≤ 0), то вводят новую переменную Xk ", так что Xk " = –Xk . Очевидно, что Xk " ≥ 0. После этого в каждом ограничении и целевой функции переменную Xk заменяют на [ – Xk "].

Если какая-то переменная Хt может принимать любые значения, то её заменяют разностью двух неотрицательных переменных Хt’ и Хt’’, т. е. полагают, что хt = Хt’ – Хt’’, где Хt’ 0 ≥ и Хt’’ ≥ 0.

2. Преобразование ограничений. Если какое–либо из ограничений в модели имеет вид неравенства, то оно преобразуется в равенство прибавлением (если неравенство имеет тип ≤) или вычитанием (если неравенство имеет тип ≥) из его левой части. Эти переменные называют балансовыми. Балансовые переменные входят в целевую функцию с коэффициентами нуль. Балансовая переменная принимает значение индекса последовательно после уже имеющихся. Если, например, система ограничений имеет 5 переменных, то первая балансовая переменная будет Х6, а вторая – Х7 и т.д.

16. Переход от канонической формы модели ЗЛП к стандартной

Для перехода от канонической формы к стандартной можно каждое из

уравнений заменить системой неравенств:

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

С помощью метода Жордана-Гаусса выделяем в каждом уравнении базисную переменную. Такое выделение осуществляется с помощью эквивалентных (элементарных) гаусовских преобразований. К ним относятся:

а) умножение любого уравнения на константу отличную от нуля;

б) прибавление к любому уравнению любого другого уравнения, умноженного на любую константу.

Исходную систему линейных уравнений перед преобразованием удобно записывать в виде матрицы или таблицы:

Записываем задачу в стандартной форме.

17. Понятие гиперплоскости полуплоскости, опорная гиперплоскость.

18. Геометрич. интерпретация системы ограничений и целевой функции в задачи ЛП

19. Выпуклое множество: крайние (угловые) точки множества. Выпуклый многогранник

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

Выпуклое множество

Определение Точка х множества М называется угловой или крайней, если она не является внутренней ни для какого отрезка, целиком принадлежащего данному множеству.

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

х = λ 1 А + λ 2 В

λ 1 , λ 2 ≥ 0 выпуклая комбинация точек угловых точек А и В

λ 1 + λ 2 = 1

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

20. алгоритм графического метода решения задач ЛП

1. Проверяется, находится ли исходная ЗЛП в стандартной форме, если нет, то задачу необходимо преобразовать к стандартной форме.

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

3. Строится область допустимых значений переменных для ЗЛП.

4. Строится направляющий вектор c .

5. Через ОДЗ проводится исходная изоцель (перпендикулярно направляющему вектору).

6. Проводится мысленное перемещение исходной изоцели в направлении вектора c , если определяется максимальное значение целевой функции, или в противоположном направлении, если определяется её минимальное значение, до тех пор, пока изоцель не станет опорной к ОДЗ. Точки пересечения опорной изоцели и ОДЗ и будут оптимальными точками задачи.

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

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

20. алгоритм графич. метода решения задач ЛП

Алгоритм графического метода.

1. Последовательным построением каждого из условий системы ограничений задачи осуществляется построение ОДЗ.

2. Строится направляющий вектор С по коэффициентам при переменных целевой функции.

3. Перпендикулярно направляющему вектору через начало координат проводится исходная изоцель.

4. Проводится мысленное перемещение исходной изоцели в направлении возрастания значений вектора С, если определяется максимальное значение целевой функции или в противоположном направлении, если определяется ее минимальное значение, до тех пор, пока изоцель не станет опорной к ОДЗ. Точки пересечения опорной изоцели и ОДЗ будут оптимальными точками задачи.

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

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

23. теоремы об области допустимых значений задачи ЛП и о целевой ф-ции

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

Теорема 2. О целевой функции задачи линейного программирования.

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

24. Теорема об угловой точке. Достаточное и необходимое условие

25. Следствия из теоремы о свойствах решений задач ЛП и выводы. Понятие опорного плана.

Следствия из теорем.

Определение. План = (х1,х2,…,хn), положительным координатам которого соответствуют линейно независимые векторы, называется опорным планом ЗЛП .

Следствие1. Опорный план имеет не более m положительных координат.

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

Следствие 2. Каждая угловая точка ОДЗ является опорным планом.

27. Алгоритм симплексного метода.

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

1. Проверяется, находится ли задача ЛП в канонической форме. Если нет, то необходимо исходную модель преобразовать в каноническую форму.

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

3. Проводится построение исходной симплексной таблицы.

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

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

6. Из базиса выводится вектор, которому соответствует симплексное отношение, рассчитанное по формуле 0 < Ө ≤ . Данная строка называется разрешающей строкой.

7. Строится новая симплексная таблица. Соответствующим образом изменяются столбцы Б и С Б. остальная часть таблицы заполняется из предыдущей с помощью гауссовских преобразований, причем индексная строка считается m+1 строкой и также преобразуется с помощью гауссовских преобразований. Переходим к выполнению пункта 4 данного алгоритма.

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

28. выбор базиса и построение начального опорного плана при решении задач симплекс методом.

29. Симплекс-таблицы, их заполнение. Формулы расчета коэффициентов индексной строки.

30 . Теорема оптимальности плана задачи линейного программирования следствие из теоремы оценки оптимальности при решении задач симплекс методом.

Теорема 1: Если для некоторого вектора Ā j в системе

Х 1 + а 1 m +1 X m +1 + а 1 m +2 X m +2 + … + а 1 n X n = a 1

Х 2 + а 2 m +1 X m +1 + а 2 m +2 X m +2 + … + а 2 n X n = a 2

…………………………………………………..

X m + а mn +1 X m +1 + а mn +2 X m +2 + … + а mn X n = a m

Выполняется соотношение Z j – c j > 0, то план Х Б0 не является оптимальным и можно перейти к плану Х Б1 такому, что Z (Х Б1) ≤ Z (Х Б0).

Здесь Z j = (С, Ā j) – скалярное произведение векторов.

С – вектор, состоящий из коэффициентов при базисных переменных целевой функции Z

Ā j – вектор, состоящий из коэффициентов разложения соответствующего вектора по векторам базиса.

c j – коэффициент целевой функции Z при переменной Х j

Следствие из теоремы : Если для всех векторов Ā 1 , Ā 2 , …, Ā n некоторого опорного плана Х выполняется соотношение Z j – c j < 0, то опорный план Х является оптимальным. Величины (Z j – c j) – называются оценками оптимальности соответствующих векторов.

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

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

31. Выбор вектора, вводящегося в базис и выводящегося из базиса. Симплексное отношение.

Для перехода к новому опорному плану необходимо один из свободных векторов ввести в базис, а какой-то из базисных векторов вывести. Для введения в базис выберем вектор, имеющий хотя бы одну положительную координату. Пусть таким вектором будет вектор А m+1 .

Разложению –

Соотв. вектор, кот. будет являться опорным планом, если его координаты будут неотрицательными, а кол-во положительных координат будет равняться m.

Координаты вектора Х1 должны быть неотрицательными, т.е. .

Если , то эта координата будет неотрицательной.

Пусть минимум в соотношении (5) был получен при i =1, тогда если взять

то первая координата вектора 1 х станет равной нулю.

Соотношение (6) называется симплексным отношением . Таким образом, мы перешли от исходного опорного плана 0 х (базисные векторы А1,А2,…Аm) к опорному плану 1 х (базисные векторы А2,А3,…,Аm,Am+1).

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

33. Правило «четырехугольника» для перерасчета симплекс-таблицы

34. Признак единственности оптимального плана, множества оптимальных планов и отсутствия оптимального плана при решении задача ЛП симплекс-методом.

При решении задач симплекс-методом возможны следующие виды оптимальных решений:

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

2. Альтернативный оптимум (множество оптимальных решений).

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

3. ЗЛП не имеет оптимального решения, так как целевая функция не ограничена снизу . Если в симплекс таблице имеется положительная оценка, а все элементы данного столбца отрицательны и нулевые, то данный вектор можно ввести в базис. Однако никакой из базисных векторов нельзя вывести из базиса. Из этого следует, что дальнейшее уменьшение целевой функции возможно при переходе к неопорному плану.

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

5. Если ОДЗ состоит из одной точки, то решение такой задачи является тривиальным, и может быть получено без использования симплекс-метода.

35. В каких случая применяется метод искусственного базиса

искусственной.

36. Построение М-задачи в методе искусственного базиса

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

Искусственную переменную необходимо добавить в целевую функцию с очень большим положительным числом (так как целевая функция на нахождения минимума). Это число обозначается латинской буквой M. Его можно считать равным +∞. В связи с этим иногда метод искусственного базиса называют М- методом. Такое преобразование исходной задачи называется построением расширенной задачи. Если решается задача с целевой функцией на нахождение искусственную переменную необходимо добавить в целевую функцию с очень большим положительным числом (так как целевая функция на нахождения минимума). Это число обозначается латинской буквой M. Его можно считать равным +∞. В связи с этим иногда метод искусственного базиса называют М- методом. Такое преобразование исходной задачи называется построением расширенной задачи. Если решается задача с целевой функцией на нахождение максимума, то искусственные переменные входят в целевую функцию с коэффициентом –М.

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

Строится исходная симплекс таблица.

37. построение индексной строки в методе искусственного базиса

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

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

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

38. Критерий оптимальности в методе искусственного базиса. Признак построение начального опорного плана исходной задачи.

39. Алгоритм двойственного симплекс-метода

Алгоритм двойственного симплекс-метода:

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

2. Выбирают направляющую строку по наибольшему по абсолютной величине отрицательному элементу столбца свободных членов А0

3. Выбирают направляющий столбец по наименьшему по абсолютной величине отношению элементов индексной строки к отрицательным элементам направляющей строки.

4. Пересчитывают симплексную таблицу по правилу полных жордановых исключений

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

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

41. Открытые и закрытые транспортные модели. Переход от открытой транспортной модели к закрытой.

Типы транспортных задач.

Имеются m поставщиков однородной продукции с известными запасами продукции и n потребителей этой продукции с заданными объёмами потребностей. Известны так же удельные затраты на перевозку.

Если сумма объёмов запасов продукции равна объёму потребностей всех потребителей, то такая задача называется закрытой транспортной задачей

(т. е. если ∑ Ai = ∑ Bj), в противном случае транспортная задача называется открытой . Для решения транспортной задачи необходимо, чтобы она была закрытой.

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

Пусть ∑Ai > ∑Bj. В этом случае необходимо ввести фиктивного n+1 потребителя с объёмом потребностей ∑Ai – ∑Bj Удельные затраты на перевозку от поставщиков к фиктивному потребителю полагаются равными 0, так как на самом деле такие перевозки осуществляться не будут и некоторая часть продукции останется у поставщиков.

Если ∑Bj > ∑Ai . В этом случае необходимо ввести фиктивного m+1 поставщика с объёмом запасов∑Bj – ∑Ai . Удельные затраты на перевозку от фиктивного поставщика к потребителям полагаются равными 0, так как на самом деле такие перевозки осуществляться не будут и некоторую часть продукции потребители недополучат.

42. Способы построения первоначального распределения в транспортной задаче: метод северо-западного угла и метод наименьшего элемента в матрице.

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

Метод наименьшего элемента в матрице.

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

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

Дальнейшее распределение делается сначала предельно возможно по клеткам с двумя отметками, потом - с одной, а затем делается добалансировка задачи до (m + n – 1) заполнений. Заполнения организуем при прохождении таблицы слева направо и сверху вниз.

43. Свойства транспортных задач

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

Теорема 1. Закрытая транспортная задача всегда имеет решение.

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

Теорема 3. система ограничений закрытой транспортной задачи всегда линейно-зависима.

Из этой теоремы следует, что распределение закрытой транспортной задачи всегда имеет m + n – 1 базисную переменную и (m – 1) (n – 1) свободные временные.

44. Вырожденное распределение в транспортных задачах, избавление от вырожденности. Вычеркиваемая комбинация.

Распределение называется вырожденным, если количество клеток меньше чем m + n – 1.

45. Теорем оптимальности транспортной задачи.

Теорема. Если для некоторого распределения транспортной задачи вы-

полняются условия:

а). ui+vj = сij для занятых клеток

б) ui+vj ≤ сij, для свободных клеток,

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

Величины ui называют потенциалами строк, а величины vj называют потенциалами столбцов.

46. Потенциалы и способы их расчета.

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

Количество уравнений исходя из этого условия равняется m + n – 1, а количество неизвестных ui и vj равняется m + n. Т.о. количество переменных больше количества уравнений, причем все уравнения линейно независимы. Решение такой системы линейных уравнений является неопределенным, поэтому одному из потенциалов нужно присвоить любое значение. На практике ui = 0. получается система из m + n – 1 уравнений с m + n – 1 неизвестными переменными. Эту систему можно решить любым методом. На практике для расчета потенциалов рассматриваются занятые клетки, для которых один их потенциалов известен, и исходя из условия а) теоремы вычисляются значения остальных неизвестных потенциалов.

47. расчет оценок оптимальности распределения транспортных задач и критерий оптимальности.

Исходя из соотношения б) теоремы можно записать следующую формулу для вычисления оценок: δ ij = ui +vj – сij. Для того, чтобы оценки не перепутать с объёмами перевозок, они (оценки) заключаются в круги.

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

48. перераспределение поставок в транспортной задаче

Если распределение не является оптимальным, то необходимо осуществить перераспределение поставок.

Для перераспределения осуществляют построение цикла пересчета. В качестве клетки выбирается клетка с наибольшей положительной оценкой. Эта клетка помечается знаком «+», то есть в неё необходимо записать некоторый объём поставки. Но тогда нарушится баланс по данному столбцу, следовательно, одну из занятых клеток данного столбца необходимо пометить знаком «-», то есть уменьшить объём поставки на такую же величину. Но тогда изменится баланс по данной строке, следовательно, какую-то занятую клетку данной строки необходимо пометить знаком «+». Данный процесс продолжается до тех пор, пока не поставлен знак «-» в строке, где находилась исходная клетка.

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

49. цепочки перераспределения, их виды.

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

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

Для этого Q надо выбрать равным наименьшему уменьшаемому из клеток, в которых Q вычитается. На следующих рис. 7.1 и 7.2 покажем примеры циклов и правило вычисления.

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

50. Выбор объема перераспределения.

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

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

б) одна из занятых клеток должна стать свободной.

Для того, чтобы эти условия выполнялись, необходимо объём перемещаемой продукции выбрать следующим: θ=min {хij} -, где {хij} – объёмы перевозок из клеток цикла пересчёта, помеченных знаком «-».

θ = min{20;30}=20

К значениям клеток, помеченных знаком «+»прибавляется θ. От значений клеток, помеченных знаком «-», вычитается θ. Значение поставок остальных клеток переписывается без изменений. В результате получим следующую таблицу.

53. Алгоритм метода потенциалов.

Алгоритм:

1. Проверить, выполняется ли для задачи рав-во если нет, то в задачу вводится фиктивный поставщик или потребитель

2. Условие задачи записывается в форме транспорт.таблицы

3. Строится начальный опорный план

4. Определяются потенциалы пост-ков и потреб-лей

5. Вычисляются оценки свободных клеток. Если все они не отрицательные – план оптимальный и нужно выписать ответ. Матрицу перевозок Х и определить величину затрат на транспортировку. Если план не явл-ся оптимальным, т.е.среди оценок есть отриц-ые, то выбир-т перспективную клетку с наибольшей по величине отриц. оценкой и переходят по величине к след.

6. Загруж-т перспективную клетку. Оформл-т нов.опорн.план в виде трансп.таблицы. Переходят к пункту 4.

54. Учет затрат на производство и транспортировку продукции. Транспортная задача с запретами на поставки.

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

Где Cij ‘ – приведенные затрат на производство одной единицы продукции.

Cij “– затраты на транспортировку одной единицы продукции.

Задачи с запретами на поставки.

В некоторых ситуациях нельзя перевозить продукцию по какому-либо маршруту.

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

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

учет ограничений по пропускной способности маршрутов.

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

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

В некоторых случаях в задаче требуется, что например по маршруту Ak Bs должно обязательно осуществиться поставка в объема А ед. В этом случае из объема производства пункта А и объем S Bs вчитается обязательная поставка и задача решается относительно необязательности поставок. После получения оптимального решения обязательно поставка добавляется к объему стоящему в клетке Ak Bs.

56. Возможные выводы при экономич. интерпретации оптимального распределения для открытых транспортных задач.

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

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

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

57.Понятие двойственности. Экономическая постановка двойственных задач на примере задачи об оптимизации плана выпуска продукции.

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

Пусть имеется зада об оптимизации плана выпуска продукции. Она имеет следующий вид:

Исходная задача:

а 11 х 1 +а 12 х 2 +…+ а 1п х п ≤в 1 | у 1

а 21 х 1 +а 22 х 2 +…+ а 2п х п ≤в 2 | у 2

……………….. |.. (1)

а т 1 х 1 +а т 2 х 2 +…+ а т п х п ≤в 1 | у т

x j ≥0, j = 1,n(2)

z = c 1 x 1 +c 2 x 2 +…+c n x n ->max(3)

X = (x 1, x 2 ,…, x n)

a ij – кол-во сырья i- го вида, затраченного для выпуска j-го вида продукции

Двойственная задача

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

у i - цена i- го вида сырья имеющегося на предприятии.

а 11 у 1 +а 21 у 2 +…+ а т 1 у т ≥с 1

а 12 х 1 +а 22 у 2 +…+ а т 2 х п ≥с 2

……………….. (1’)

а 1п у 1 +а 2п у 2 +…+ а тп у т ≥с п

у i ≥0, j = 1,m(2’)

F = b 1 y 1 +b 2 y 2 +…+b m y m ->min(3’)

58. Соответствие между структурными элементами прямой и двойственной задачи

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

двойственную задачу по следующим правилам:

1. Во всех ограничениях исходной задачи свободные члены должны

находиться справа, а члены с неизвестными - слева.

2. Ограничения-неравенства исходной задачи должны иметь знаки,

направленные в одну строну.

3. Если целевая функция в исходной задаче минимизируется, ограничения-неравенства следует записать со знаком «≤» , тогда в двойственной задаче целевая функция будет минимизироваться и знаки ограничений-неравенств будут «≥».

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

двойственной задаче. Если переменная соответствует неравенству, она неотрицательна, если равенству – то переменная без ограничений на знак («произвольная»).

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

коэффициентов при переменных исходной задачи.

6. Свободные члены исходной задачи являются коэффициентами при

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

членами в двойственной задаче – коэффициенты при переменных в

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

59. Построение двойственных задач к исходным задачам, записанным в стандартной, канонической и общей форме модели(построение симметричных и несимметричных двойств. задач)

Стандартная форма (исходная)

Σ a ij x j ≤ b i , i=1,n(1)

x j ≥0, j=1,n(2)

z = Σ c j x j ->max(3)

Двойственная стандартная

Σ a ij y i ≤ c j , j=1,n(1)

y i ≥0, j=1,m(2)

F = Σ b i y i ->min(3)

Исходная задача в канонической форме:

Σ a ij x j = b i , i=1,m(1)

x j ≥0, j=1,n(2)

z = Σ c j x j ->min(3)

Двойственная каноническая

Σ a ij y i ≤ c j , j=1,n(1)

y i - любые (2)

F = Σ b i y i ->max(3)

Дадим экономическую интерпретацию пары двойственных задач. Рассмотрим задачу рационального использования ресурсов. Пусть предприятие располагает ресурсами b1,b2,…bm, которые могут использ-ся для выпуска n-видов продукции. Пусть также известны стоимость единицы j-вида продукции cj (j=1,n) и норма потребления i-го ресурса (i=1,m) на производство единицы j-й продукции – aij.Требуется определить объем производства продукции каждого вида xj (j=1,n), максимизирующий суммарную стоимость

f= c1x1+…+cnxn (1)

При этом расход ресурсов не должен превышать их наличия:

a11x1+…+a1nxn<=b1 }

…………………….. } (2)

am1x1+…+amnxn<=bm }

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

Xj>=0 (j=1,n). (3)

Заметим, что это задача образуют симитричную двойственную задачу.

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

Возьмем ЗЛП на максимум в канонической форме:

Max Z=(n;j=1)Σcj*xj

(n;j=1)Σaij*xj=bi (i=1,m)

Xj>=0 (j=1,n).

60.Основная и вторая теорема двойственности (сформулировать теоремы и разъяснить)

Первая теорема двойственности.

Теорема: если одна из двойственных задач имеет оптимальный план, то и другая решима, т.е. имеет опт.план. При этом экстремальные значен.целевых функций совпадают (j=от 1 до n) Σcjxj*= (i=от 1 до m)Σbiyi* если в исходн. задаче целевая функция неограниченна на множестве планов, то в двойственной задаче система ограничений несовместна.

Вторая теорема двойственности и ее эконом.интерпритация.

Для того, чтобы допустимые решения пары двойственных задач были оптимальными, необходимо и достаточно выполнение условия: xj*(∑aij yi*-cj)=0, j от 1 до n, yi*(∑aij xj*-bi)=0, I от 1 до m. Это условия дополняющей нежесткости. Из них следует: если какое-либо ограничение двойств.задачи обращ-ся оптималь.планом в строгое равенство, то соответствующая компонента опт. плана двойственной задачи должно равняться нулю.Если же какая-то компонента опт. плана равна нулю, то соответствующее ограничение двойств.задачи обращается опт.планом в строгое равенство хj*>0 следовательно (i= от 1 до m)Σaij yi*=cj (затраты на пр-во продукции=цене) – Если продукция вошла в опт.план, то если затраты>цены, объем пр-ва=0 Σaij yi* >cj следовательно xj*=0

yi*>0 следовательно (j=от 1 до n) Σaij xj*=bi (рас-ды рес-ов =запас рес-ов).

(j=от 1 до n) Σaij xj*

Смысл теоремы сводится к следующему:

Если стоимост.оценка рес-ов расход-х на пр-во ед.прод-ии=цене, то этот вид прод-ии входит в оптим.план;

Если затраты превышают цену, то прод-ию производить не следует;

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

Если рес-с израсходован неполностью, то его стоимост.оценка = 0.

61. Построение оптимального опорного плана двойственной задачи по симплексной таблице исходной задачи

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

Столбец A3: «теневая» цена ресурса S2 равна y01=0, столбец остался

единичным и по первой строке можно прочесть, что x3=9, т.е. при реализации найденного оптимального плана 1-й ресурс окажется в избытке, причем этот избыток (недоиспользование) как раз составит 9 условных единиц.

Столбец A4: «теневая» цена ресурса S2 равна y02=1, ресурс будет полностью использован и его возможное увеличение будет вести к увеличению целевой функции (т.е. дохода). И т.к. y02=1, то увеличение ресурса S2 на 1 у.е. будет давать добавку по доходу на.Z = y02· .в2 = = 1.1 = 1 (тыс. грн.) (здесь.в2 -приращение ресурса S2 и.Z - соответствующее приращение дохода). При таком приращении ресурса S2 максимальный доход уже составит Zmax=58 тыс. грн. + 1 тыс. грн = 59 тыс. грн. На рис. 6.2 проиллюстрирована эта ситуация, комментарий по отношению к которой будет приведен ниже. Из столбца A4 еще следует, что при увеличении ресурса S2 на 1 у.е. для новой оптимальной точки выпуск товара T1 сократится на ½ тонны (на пересечении строки базисной переменной x1 и столбца A4 стоит «-1/2»), а выпуск товара T2 увеличится на 3/2 тонны (т.к. в строке с базисной переменной x2 в столбце A4 имеем «3/2»).Сказанное по столбцу A4 будет ниже прокомментировано с помощьюграфических построений (рис. 6.2).Столбец A5: «теневая» цена ресурса S3 равна y03=2. Это означает, чтоувеличение ресурса S3 на 1 у.е. принесет добавку по Z на.Z = y03· .в3 = 2.1 =2(тыс. грн.) и составит Zmax=58 тыс. грн. + 2 тыс. грн = 60 тыс. грн. При этом, как следует из столбика A5 табл. 3, выпуск T1 увеличится на ½ тонны, а T2 уменьшится на ½ тонны. Запас по сырью S1 (см. 1-ю строку) увеличится на 3/2 у.е.

62. Идея метода динамического програмирования и его геометрическая интерпретация. Принцип оптимальности Беллмана.

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

Чтобы определить его, необходимо:

1.записать функциональное уравнение для последнего состояния процесса (ему соответствует l=n-1)

fn-1(Sl-1)=optimum(Rn(Sn-1,Un)+f0(Sn))

2.найти Rn(Sn-1,Un) из дискретного набора его значений при некоторых фиксированных Sn-1 и Un из соответствующих допустимых областей (так как f0(Sn)=0, то f1(Sn-1)= optimum(Rn(Sn-1,Un)

В результате после первого шага известно решение Un и соответствующее значение функции f1(Sn-1)

3.Уменьшить значение l на единицу и записать соответствующее функциональное уравнение. При l=n-k (k= 2,n) оно имеет вид

fk(Sn-k)=optimum(Rn-k+1(Sn-k,Un-k+1)+fk-1(Sn-k+1)) (2)

4.найти условно-оптимальное решение на основе выражения (2)

5.проверить, чему равно значение l.Если l=0, расчет условно-оптимальных решений закончен, при этом найдено оптимальное решение задачи для первого состояния процесса. Если l не равно 0, перейти к выполнению п.3.

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

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

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

Математически он записывается выражением вида:

fn-1(Sl)=optimum(Rl+1(Sl,Ul+1)+fn-(l+1)(Sl+1)) (1)

(l=0,n-1)Optimum в выражении означает максимум или минимум в зависимости от условия задачи.

63. Требования, предъявляемые к задачам, решаемым методом ДП

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

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

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

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

64.Экономическая постановка и построение математической модели задачи, решаемой методом ДП(на примере задачи о распределении капиталовложений). Рекуррентное соотношение Беллмана.

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

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

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

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

Все вычисления, дающие возможность найти оптимальное значение эффекта, достигаемого за n шагов, fn(S0), проводятся по формуле (1), которая носит название основного функционального уравнения Беллмана или рекуррентное соотношение. При вычислении очередного значения функции fn-1 используется значение функции fn-(l+1), полученное на предыдущем шаге, и непосредственное значение эффекта Rl+1(Sl,Ul+1), достигаемого в результате выбора решения Ul+1 при заданном состоянии системы Sl. Процесс вычисления значения функции fn-1(l=0,n-1)

Осуществляется при естественном начальном условии f0(Sn)=0, которое означает, что за пределами конечного состояния системы эффект равен нулю.

65. Задача о распределении капитальных вложений (пример).

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

Начнем с оптимального распределения выделенных капиталовложений в сумме К между двумя предприятиями. Плановые отделы предприятий на основе своих расчетов сформировали функции дохода q(x) для предприятия П1 и h(x) - для предприятия П2. Функции эти означают, что если первое или второе предприятие получит капиталовложение и размере х, то первым предприятием

будет получен доход q(x), а вторым h(x), причем величина x может принимать непрерывные или известные дискретные значения от 0 до К.

Итак, пусть предприятию П1 выделены капиталовложения в сумме х, тогда предприятию П2 выделяется сумма К - х. В этом случае от первого предприятия будет получен доход q(x), а от второго - h(К - x). Если капиталовложения К были выделены на один плановый период, то общий доход от двух предприятий составит R(K, x) = q(x) + h(K - x). Очевидно, что x и соответственно К - x надо выбирать такими, чтобы R(K, x) приняло свое максимальное значение, которое мы обозначим через F(K):

Эта запись является как бы остовом для более полных записей

функционального уравнения Беллмана. УСЛОЖНИМ нашу задачу, распределив капиталовложения на два плановых периода (два этапа). Пусть изначально решено первому предприятию П1 выделить сумму х, а второму К – х. В целом доход получался бы равным R(K, x) = q(x) +

h(K - x). Если мы будем иметь в виду, что капиталовложения распределяются на 2 периода (2 этапа), то на первом предприятии остаток капиталовложений составит.x, где , а на втором - .(К - х), где Соответственно доходы за второй период составят q(.x) -по первому предприятию и h[.(K - x)] - по второму. Оптимизацию по методу динамического программирования, как правило, начинают с концевого этапа. Поэтому начнем со второго этапа, обозначив F1 максимально возможный доход от двух предприятий на втором

этапе. Получим

Затем к рассмотренному последнему (в нашем случае второму) этапу как бы пристраиваем предшествующий (у нас первый) этап и находим максимальный доход от двух этапов вместе:

Аналогичным образом для n этапов получаем

где Fn-1 - целевая функция, дающая наилучший результат за последние (n - 1) этапы. Полученное функциональное уравнение Беллмана носит рекуррентный характер, т.е. связывает значение Fn со значением Fn-1.

В более общем начертании уравнение Беллмана имеет вид

где , Fn-1 - максимальный доход за (n - 1) последних этапов, Fn -

максимальный доход за все n этапов.

66. Понятие о решении задач нелинейного программирования

Пусть задача нелинейного программирования ставится в следующем общем виде: найти такие значения переменных х1, х2,…, хn, которые отвечают условиям:

и приносят требуемый экстремум (максимум или минимум) целевой функции

f = f(х1, х2,…, хn), (13.2)

где f(х1, …, хn) и qi(х1, …, хn) (m , 1 i =) - действительные нелинейные,

регулярные функции n действительных переменных.

По своим общим свойствам задачи нелинейного программирования могут

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

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

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

рассматриваемой задачи, а итеративный процесс расчетов начинается с точки

Далее, сначала делается переход по градиенту целевой функции, а затем возврат в область. по градиенту к нарушенной границе О2 О3 области.. На рис. 13.3 показано так, что Ai с нечетными индексами принадлежат области., а точки Аi с четными индексами не принадлежат.. По мере приближения к оптимальной точке Q направления рабочих градиентов сближаются. Поэтому идеальным критерием остановки процесса будет коллинеарность градиента цели и градиента нарушенной границы.

67. Понятие о параметрическом и целочисленном программировании .

Постановка и математич модель ЗЦЛП.

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

f=(n,j=1)∑CjXi max

(n,j=1)∑AijXj=bi, i=1,m

xi-целое,j=1,n

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

1.Методы отсечения

2.Комбинаторные

3.Приближенные методы..

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