В. И. Векленко экономико-математические




НазваниеВ. И. Векленко экономико-математические
страница5/22
Дата публикации29.06.2013
Размер2.89 Mb.
ТипУчебное пособие
zadocs.ru > Экономика > Учебное пособие
1   2   3   4   5   6   7   8   9   ...   22

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

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

Рассмотрим числовой пример М-метода.

Найти максимум целевой функции: max f()=3xl+2х23 при условиях:

12=8,

х123=6,

х10, х20, х30

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

Построим М-задачу: найти максимум целевой функции max f() = 3х1 + 2х2 + х3 - Myl при условиях:

12+y1=8,

х123=6,

х10, х20, х30, y10.

М-задачу решаем симплекс-методом. Начальный опорный план (0,0,6,8). Решение проводим в симплекс-таблицах (табл. 7).
Таблица 7 – Решение задачи ЛП М-методом


Номер симплекс-таблицы




сj

0

3

2

1






ci

П

Б

в0

х1

х2

х3

y1

со

0



y1

8

2

1

0

1

4

1

х3

6

1

1

1

0

6

-



-8М+6

-2М-2

-М-1

0

0

-

1

3

1

х1

х3

4

2

1

0

0,5

0,5

0

1







-



14

0

0

0








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

Полученное решение является допустимым планом исходной задачи. Для него все j0, поэтому он оптимальный. Следовательно, получен оптимальный план исходной задачи (4,0,2), максимальное значение целевой функции f (X*) = 14.

Лекция4. ЭКОНОМИКО-МАТЕМАТИЧЕСКИЙ АНАЛИЗ

^ ОПТИМАЛЬНЫХ РЕШЕНИЙ ЗАДАЧ

ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ


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

  2. Экономические свойства двойственных оценок

  3. Анализ оптимального решения по последней симплексной таблице



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


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

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

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

(1)

(2)

(3)
Переменные двойственной задачи yi называют объективно обусловленными оценками, или двойственными оценками. Модель двойственной задачи имеет вид:

(4)

(5)

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

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

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

2) Матрица ,

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

.

3) Число переменных в двойственной задаче равно числу функциональных ограничений исходной задачи (2), а число ограничений в системе двойственной задачи (5) – числу переменных в исходной задаче.

4) Коэффициентами при неизвестных в целевой функции двойственной задачи (4) являются свободные члены в системе ограничений исходной задачи (2), а правыми частями в ограничениях двойственной задачи (5) – коэффициенты при неизвестных в целевой функции исходной задачи (1).

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

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

^ Первая теорема двойственности утверждает:

1. Если прямая и двойственная задачи имеют оптимальные решения, то значения целевых функций в их оптимальных планах совпадают: max f() = min g() .

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

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

4. Обе из рассматриваемых задач не имеют допустимых решений.

Вторая теорема двойственности утверждает правила дополняющей нежесткости. Пусть = (xl,x2,...,xn) – допустимое решение прямой задачи (1)-(3), а = (y1, y2,...,ym) – допустимое решение двойственной задачи (4)-(6). Для того чтобы они были оптимальными решениями соответствующих взаимодвойственных задач (1)-(3) и (4)-(6), необходимо и достаточно, чтобы выполнялись следующие соотношения:

, (7)

. (8)

Условия (7) и (8) позволяют по данным оптимального решения одной из взаимодвойственных задач найти оптимальное решение другой задачи.
^ 2. Экономические свойства двойственных оценок
Конкретными экономическими свойствами оценок yi оптимального плана является:

Свойство 1. Оценки как мера дефицитности ресурсов и продукции.

Свойство 2. Оценки как мера влияния ограничений на функционал.

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

Свойство 4. Оценки как инструмент балансирования суммарных затрат и результатов.

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

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

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

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

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

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

^ 3. Анализ оптимального решения по последней

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

задачи с тремя ресурсами





сj

0

4

10

0

0

0

ci

П

Б

b0

х1

х2

х3

х4

х5

0

х4

30

0

0

30

1

-15

10

х2

1

0

1

-0,5

0

0,125

4

х1

4

1

0

1,5

0

-0,125






26

0

0

1

0

0,75


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

=30-30=0

=1+0,5=1,5

=4-1,5=2,5

=42,5+10 1,5=25

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

=4+1,5=5,5

=1-0,5=0,5

=30+30=60

=45,5+101,5=27

=27-26=1
Выполнение ограничений:

  1. По площади пашни:

5,5 га + 0,5 га = 6 га (вместе 5 га)

  1. По использованию трудовых ресурсов:

30 чел. – дн.5,5 га +150 чел. – дн. 5,0 га = 240 чел. – дн.

Недоиспользование трудовых ресурсов составило:

300 чел. – дн. – 240 чел. – дн. = 60 чел. – дн. (х4=60).

3. По механизированным работам:

4 усл. га5,5 га + 12 усл. га0,5 га=28 усл. га

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

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

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

При уменьшении ресурсов пашни уменьшаются базисные переменные х4 и х1. При уменьшении пашни на 1 га переменная х4 уже достигнет нулевого значения (1=30/30). По переменной х1 нулевой значение будет достигнуто при уменьшении пашни на га (=4/1,5). Поэтому в случае, когда уменьшается ресурс и в таблице соответствующей небазисной переменной имеется несколько положительных коэффициентов замещения, среди соотношений значений коэффициентов столбца b0 и соответствующих положительных коэффициентов в столбце с небазисной переменной, обозначающей недоиспользование рассматриваемого ресурса, выбирается минимальное, которое и укажет на максимальную величину снижения объема ресурса.

Таким образом, предельное уменьшение пашни в хозяйстве может составить 1 га. Предельное изменение ресурса пашни в хозяйстве, при котором состав базисных переменных не изменится, составляет от 4 до 7 га.

При увеличении объемов механизированных работ максимальное значение составит:

min (30/15; 4/0,125)= 2 (усл. га),

а при уменьшении:

1/0,125=4 (усл. га).

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

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

Лекция 5. РАСПРЕДЕЛИТЕЛЬНЫЙ МЕТОД РЕШЕНИЯ

^ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ


  1. Постановка и экономико-математическая модель
    распределительной (транспортной) задачи


  2. Общая характеристика метода потенциалов

  3. Решение транспортной задачи

  4. Особые случаи решения транспортной задачи

  5. Дополнительные ограничения в транспортной задаче



  1. Постановка и экономико-математическая модель

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

(1)

, (2)



В т пунктах отправления А1, А2,...,Ат,, которые в дальнейшем будем называть поставщиками, находится аi (i = 1, 2, ..., т) единиц некоторого однородного продукта. Данный продукт потребляется в п пунктах В1, В2,…, Вn, которые будем называть потребителями; объем потребления обозначим bj (j = 1, 2, ..., п). Известны расходы на перевозку единицы продукта из пункта Ai в пункт Bj, которые равны cij и приведены в матрице транспортных расходов С = ij).

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

Обозначим количество продукта, перевозимого из пункта Ai в пункт Bj, через xij. Совокупность всех переменных xij для краткости обозначим , тогда целевая функция задачи представляет собой линейную форму:

(3)

Условия (1) означают полное удовлетворение спроса во всех пунктах потребления; условия (2) определяют полный вывоз продукции от всех поставщиков.

Необходимым и достаточным условием разрешимости задачи (1) – (3) является условие баланса:

(4)

^ 2. Общая характеристика метода потенциалов
Транспортная задача, в которой имеет место равенство (4), называется закрытой и может быть решена как задача линейного программирования с помощью симплексного метода. Однако благодаря особенностям переменных задачи и системы ограничений разработаны специальные, менее громоздкие методы ее решения. Наиболее применяемым методом является метод потенциалов, при котором для каждой i-й строки (i-го поставщика) определяется потенциал ui, а для каждого столбца j - потенциал vj. Сумма потенциалов для перевозки груза от i-го поставщика к j-му потребителю должна быть равна величине транспортных расходов cij, т.е. быть оценена с точки зрения критерия решаемой задачи:

cij=vj+ui (5)
Если баланс (4) не выполняется, то ограничения (1) или (2) имеют вид неравенств типа «меньше или равно»; транспортная задача в таком случае называется открытой. Для решения открытой транспортной задачи методом потенциалов ее сводят к закрытой задаче путем ввода фиктивного потребителя, если в неравенства превращаются условия (2), или фиктивного поставщика в случае превращения в неравенства ограничений (1).

Рассмотрим этапы реализации метода потенциалов для закрытой транспортной задачи. Прежде всего следует отметить, что при условии баланса (4) ранг системы линейных уравнений (1), (2) равен т + п - 1; таким образом из общего числа (m n) неизвестных базисных неизвестных будет (т + п – 1). Вследствие этого при любом допустимом базисном распределении в матрице перевозок, представленной в общем виде в табл. 9, будет занято ровно т + п - 1 клеток, которые будем называть базисными в отличие от остальных свободных клеток. Коэффициент целевой функции в занятых клетках будем выделять полукругом.

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



Вj

Ai

B1

B2

……

Bn

b1

b2

……

bn

А1

a1


c11

x11

c12

x12

……

c1n

x1n

А2

a2


c21

x21

c22

x22

……

c2n

x2n

……

……

……

……

……

……

Аm

am


cm1

xm1

cm2

xm2

……

cmn

xmn

^ 3. Решение транспортной задачи
Имеется 3 поставщика и 3 потребителя. Ресурсы 1-го поставщика составляют 10 ед. , 2-го – 8, 3-го – 13. Потребности потребителя А составляют 6 ед., Б – 14 ед., В – 11 ед. Транспортная задача закрытая.

Издержки на транспортировку единицы груза с учетом расстояния между поставщиками и потребителями приведены в таблице 10.
Таблица 10 - Издержки на транспортировку единицы груза

от поставщиков к потребителю


Поставщики

Потребители

А

Б

В

1

4

5

4

2

2

3

6

3

1

2

4


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

^ Сформируем задачу линейного программирования:

Х11 – объем перевозки грузов от 1-го поставщика в потребителю А,



Хij – объем перевозки груза от i-го поставщика к потребителю j,



Х33 – объем перевозки от 3-го поставщика к потребителю В.
Ограничения по объемам поставки:

1-го поставщика: Х11 + Х12 + Х13 = 10

2-го поставщика: Х 21 + Х22 + Х23 = 8

3-го поставщика: Х31 + Х32 + Х33 = 13

Ограничения по потребностям:

Потребителя А: Х11 + Х21 + Х31 = 6

Потребителя Б: Х12 + Х22 + Х32 = 8

Потребителя В: Х13 + Х23 + Х33 = 13

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

С (min) = 4 Х11 + 5Х12 + 4Х13 + 2Х21 + 3Х22 + 6Х23 + Х31 + 2Х32 + 4Х33

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

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


Алгоритм метода северо-западного угла

  1. Выбирается левая верхняя клетка таблицы.

  2. В эту клетку записывается базисная переменная:

  1. Сравниваем ресурсы (а1) и потребности (b1).

Если а1>b1, то Х11 = b1 и клетка объявляется базисной. В клетку записывается Х11.

Подсчитывается новый ресурс: 1b1 из таблицы исключается первый столбец.

Делается переход к п. 1 для новой таблицы (без исключенного столбца).

  1. Если а1<b1, то Х11 = а1. Подсчитывается новая потребность =b1 – а1. Из таблицы исключается первая строка.

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

  1. Если а1 = b1, то Х11 = а1 = b1. Подсчитывается = 0 (или =0). Из таблицы исключается столбец или строка (условно можно принять исключение строки).

Переход к п. 1 новой таблицы (без строки).
1   2   3   4   5   6   7   8   9   ...   22

Похожие:

В. И. Векленко экономико-математические iconМетодические указания к выполнению тестовых заданий по учебной дисциплине...
Курс «Экономико-математические методы и модели» посвящен современным методам количественного обоснования управленческих решений,...

В. И. Векленко экономико-математические iconМетодические указания по проведению практических занятий и выполнению...
Методические указания предназначены для проведения практических занятий и выполнения домашних заданий по дисциплине «Экономико-математические...

В. И. Векленко экономико-математические iconРабочая программа по курсу «Математические модели в управлении» для...
Целью преподавания курса является обучение студентов основам работы с экономико-математическими моделями в управлении экономическими...

В. И. Векленко экономико-математические iconВопросы к экзамену по курсу экономико-математические методы и прикладные модели
Общая запись оптимизационной эмм (задача оптимального программирования). Основные элементы и понятия

В. И. Векленко экономико-математические iconТемы магистерских диссертаций по кафедре ипфм на 2012/2013 уч год...
Экономико-математические методы оптимизации работы с клиентами предприятия финансовой сферы

В. И. Векленко экономико-математические iconЛабораторная работа выполняется по темам: «Оптимизационные экономико-математические...
Лабораторная работа выполняется и защищается в соответствии с утвержденным расписанием занятий

В. И. Векленко экономико-математические iconКонтрольная работа по предмету Экономико-математические модели и методы
Номером варианта контрольной работы является последняя цифра в шифре зачетной книжки. Пример оформления контрольной работы предложен...

В. И. Векленко экономико-математические iconКонтрольные работы по дисциплине Экономико-математические методы и модели
Студентом выбирается вопросы по номеру в соответствии с последней цифрой зачетной книжки. (Например, если последняя цифра в зачетной...

В. И. Векленко экономико-математические iconМетодические указания и контрольные задания для студентов экономического...
Методические указания написаны в соответствии с программой курса «Математические методы решения задач» и предназначены для самостоятельного...

В. И. Векленко экономико-математические iconКоролевство Великобритания
«Математические начала натуральной философии», в котором он изложил закон всемирного тяготения и три закона механики, ставшие основой...

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
zadocs.ru
Главная страница

Разработка сайта — Веб студия Адаманов