bannerka.ua

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

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

1. Обзор темы

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

1.1 Экономическая интерпретация задачи, двойственной к задаче использования ресурсов.

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

1.3 Связь между решениями прямой и двойственной задач.

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

1.5 Анализ продолжительности (устойчивости) двойственных оценок.

1.6 Двойственный симплексный метод.

1.1. Экономическая интерпретация задачи, двойственной к задаче использования ресурсов

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

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

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

Вид корма

Суточный рацион

Запасы кормов

Норки

Нутрии

И

2

3

180

ИИ

4

1

240

ИИИ

6

7

426

Прибыль

16

6

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

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

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

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

Двойственные задачи.

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

Двойственные задачи.

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

Сформулируем с Вами Алгоритм перехода от прямой к двойственной задачи.

1) Целевая функция прямой задачи стремится к максимуму, а целевая функция двойственной задачи — к минимуму.

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

Транспонирование матрицы — Замена строк столбцами, а столбцов — строками.

3) Число переменных двойственной задачи равно числу ограничений прямой задачи.

4) Число ограничений двойственной задачи равно числу переменных прямой задачи.

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

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

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

8) Если Двойственные задачи-то соотношение прямой задачи является неравенством, то Двойственные задачи-и переменная двойственной задачи Двойственные задачи. В противном случае переменная Двойственные задачи может принимать как положительные, так и отрицательные значения.

Исходя из построенного алгоритма запишем определение двойственной задачи по отношению к общей задачи ЛП:

Пусть задана задача:

Двойственные задачи (1.1)

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

Двойственные задачи (1.2)

1.3 Связь между решениями прямой и двойственной задач

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

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

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

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

Решение двойственной задачи находят из последней симплексной таблицы решения прямой задачи.

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

Базис

Сб

План

16

6

0

0

0

Х1

Х2

Х3

Х4

Х5

1

Х3

0

30

0

0

1

2/11

-5/11

2

Х1

16

57

1

0

0

7/22

-1/22

3

Х2

6

12

0

1

0

-3/11

2/11

M +1

984

0

0

0

38/11

4/11

У4

У5

У1

У2

У3

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

Решение двойственной задачи выписывают из (m +1)-й строки. Над соответствующими переменными находятся их значение. Итак, Двойственные задачи в точкеДвойственные задачи.

1.4 Экономическое содержание двойственных оценок

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

Растолкуем экономическое содержание двойственной оценки Двойственные задачи. Если увеличить количество корма ИИ вида на единицу, т. е. если его количество составит 241, то общая прибыль увеличится на 38/11 и составит 984 +38 / 11 = 987 5/11 гр. от.. При этом числа, находящихся в соответствующем переменной Двойственные задачи столбце, показывают, как при этом изменится план выпуска продукции: остаток сырья первого вида увеличится на 2/11 и составит Двойственные задачи, количество продукции 1-го вида увеличится на 7/22 и составит Двойственные задачи, количество продукции второго вида уменьшится на 3/11 и составит Двойственные задачи.

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

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

Двойственные задачи.

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

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

1.5 Анализ продолжительности (устойчивости) двойственных оценок

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

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

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

В общем случае Изменение коэффициентов исходной задачи Может привести К одной из Ситуаций:

1) Текущий базисный решение остается допустимым.

2) Текущий базисный решение становится недопустимым.

3) Текущий базисный решение становится неоптимальным.

4) Текущий базисный решение становится неоптимальным и недопустимым.

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

К Недопустимости текущего Оптимального Решения может Привести:

A) изменение правых частей ограничений (т. е. изменение вектора Двойственные задачи)

B) введение в систему ограничений нового ограничения.

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

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

Предположим, что фермер планирует расширить собственное хозяйство в условиях увеличения запасов кормов на 20%, то есть запасы кормов будут составлять 216, 288 и 511,2 усл. ед. соответственно.

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

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

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

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

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

Первое неравенство Двойственные задачи превращается в Двойственные задачи.

То есть, интервалом устойчивости для ресурса первого вида является интервал изменения его количества от -30 до 0. Следовательно, только уменьшая запасы корма (ресурса) первого вида к Двойственные задачи мы будем получать допустимые решения.

Предположим, что часть средств, тратились на корм первого вида (его остатки составляют 30 гр. Ед.), Фермер решил потратить на закупку кормов 2 и 3 видов. Пусть новые запасы кормов составляют 155, 250 и 450 усл. ед. соответственно. Найдем новый решение

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

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

1.6 Двойственный симплексный метод

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

Особенности двойственного симплексного метода:

1) Критерий оптимальности: столбик План не содержит отрицательных элементов.

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

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

Правила пересчета элементов новой симплексной таблицы аналогичны обычному симплексном метода.

3. Рекомендуемая литература

Курносов А. П., Сысоев И. А. Вычислительная техника т экономико-математические методы в сельском хозяйстве. — М., 1989. Кузнецов Ю. Н., Кузобов В. И., Ермольев Ю. М. Математическое программирование. — М.: Высш. шк., 1976. Математическое Программирование в примерах и задачах. М.: Высшая школа, 1986. Исследование операций в экономике: Учебн. пособие для вузов / Н. Ш. Кремер, Б. А. Путко, И. М. Тришин. М. Н. Фридман; Под ред. проф. Н. Ш. Кремера. — М.: Банки и биржи, ЮНИТИ, 1997. Акулич И. Л. Математическое программирование в примерах и задачах. — М.: Высш. Шк. », 1986, — 319 с. Ляшенко И. Н. Линейное и нелинейное программирование. — И К. Вищашк., 1975, -371 с.

7. Математическое моделирование экономических процессов в сельском хозяйстве / Гатаулин А. М. и др.; Под ред. А. М. Гатаулина. — М.: Агропромиздат, 1990. — 432с.: Ил.

8. Эддоус М., Стэнфилд Р. Методы принятия решений / Пер. с англ. под ред. член-корр. РАН И. И. Елисеевой. — М.: Аудит, ЮНИТИ, 1997. — 590С.

Крушевский А. В., Шевцов К. И. Математическое Программирование и моделирование в экономике.: Учеб. пособие для вузов. — М.: Высшая школа. Головное изд-во, 1979. — 456с. Курицкий Б. Я. Поиск оптимальных решений средствами Excel 7.0. — СПб.: ВНV — Санкт-Петербург, 1997. — 384с., Ил. Ляшенко И. Н. Линейное и нелинейное программирование. — М.: Высшая школа., 1975. Степанюк В. В. Методы математического программирования. — М.: Высшая школа., 1984. Кузнецов Ю. Н., Кудрявцев В. И. Математическое программирование. — М., 1980. Франс Дж. и др. Математические модели в сельском хозяйстве. М.: Агропромиздат, 1987 Кравченко Р. Г. Математическое моделирование в сельском хозяйстве. М.: Колос, 1978. Кузнецов Ю. Н. Математические модели в с / х. М.: Высшая школа, 1981 Карпенко А. ф. Практикум по математическому моделированию экономических агропромышленных процессов в сельском хозяйстве. М.: Финансы и статистика, 1985.

Tagged with: , , ,
Posted in Математические модели в расчетах на эвм
No Comments » for Двойственные задачи
9 Pings/Trackbacks for "Двойственные задачи"
  1. […] интервалы устойчивости двойственных оценок […]

  2. […] что означает создать двойственную задачу […]

  3. […] что означает создать двойственную задачу […]

  4. […] двойственные задачи […]

  5. […] какие виды двойственных задач бывают. […]

Добавить комментарий

Ваш e-mail не будет опубликован.

Можно использовать следующие HTML-теги и атрибуты: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Перечень предметов
  1. Бухучет в ресторанном хозяйстве
  2. Введение в специальность 4к.2с
  3. Высшая математика 3к.1с
  4. Делопроизводство
  5. Информационные технологии в области
  6. Информационные технологии в системах качества стандартизаціісертифікаціі
  7. История украинской культуры
  8. Математические модели в расчетах на эвм
  9. Методы контроля пищевых производств
  10. Микробиология молока и молочных продуктов 3к.1с
  11. Микропроцессорные системы управления технологическими процессами
  12. Научно-практические основы технологии молока и молочных продуктов
  13. Научно-практические основы технологии мяса и мясных продуктов
  14. Общая технология пищевых производств 4к.2с
  15. Общие технологии пищевых производств
  16. Организация обслуживания в предприятиях ресторанного хозяйства
  17. Основы научных исследований и техничнои творчества
  18. Основы охраны труда
  19. Основы пидприемницькои деятельности и агробизнеса
  20. Основы физиологии и гигиены питания 3к.1с
  21. Пищевые и диетические добавки
  22. Политология
  23. Получения доброкачественного молока 3к.1с
  24. Прикладная механика
  25. Прикладная механика 4к.2с
  26. Теоретические основы технологии пищевых производств
  27. Технологический семинар
  28. Технологическое оборудование для молочной промышленности
  29. Технологическое оборудование для мьяснои промышленности
  30. Технология продукции предприятий ресторанного хозяйства
  31. Технология хранения консервирования и переработки молока
  32. Технология хранения, консервирования и переработки мяса
  33. Технохимическому контроль
  34. Управление качеством продукции ресторанного хозяйства
  35. Физика
  36. Физическое воспитание 3к.1с
Возможно Вы искали: