Автор работы: Пользователь скрыл имя, 21 Октября 2014 в 10:48, контрольная работа
Актуальность выбранной темы исследования заключается в том, что содержание двойственности состоит в сопоставлении исходной задаче C другой задачи С*, формируемой по определенным правилам и называемой двойственной. Эти задачи связаны математически содержательными соотношениями, позволяющими, например, получить оценки критериальной эффективности всех параметров, формирующих задачу C, свести решение оптимизационной задачи к решению некоторой системы неравенств, сформировать в изящной форме условия оптимальности, оценить скорость сходимости итерационных процессов для задачи C.
Введение 3
1 Экономическая интерпретация двойственной задачи 4
2 Третья теорема двойственности об оценках 9
3 Пример использования объективно обусловленных оценок для принятия оптимальных решений 12
Заключение 16
Список использованной литературы 17
Как следует из решения, первый и второй ресурсы потребляются полностью. Их двойственные оценки положительны. Приращение первого ограниченного ресурса на единицу ведет к увеличению целевой функции на 12, второго – на 60,
третий ресурс избыточен:
Его двойственная оценка равна нулю:
Поэтому дальнейшее его увеличение не окажет влияния на значение целевой функции.
Возникает вопрос: что же показывают значения дополнительных двойственных оценок
Оптимальный план исходной задачи:
(8)
Говорит о том, что первую технологию целесообразно использовать в течение 60 часов, третью – 12 часов. Вторая технология вообще не должна внедряться. Она заведомо убыточная. Если ее все же использовать, то она в течение каждого часа работы будет снижать достигнутый уровень выпуска на ден. единиц. Значения . Это свидетельствует о том, что первая и третья технологии не являются убыточными. В самом деле, из второго ограничения двойственной задачи следует:
(9)
Стоимость ресурсов, используемых в единицу времени при работе по второму технологическому способу, составит:
(10)
В единицу же времени этот способ может дать продукции на 250 ден. единиц.
Поэтому убыток в единицу времени при работе этим способом составит
3 ПРИМЕР ИСПОЛЬЗОВАНИЯ ОБЪЕКТИВН
Предположим для определенности, что необходимо составить самый дешевый рацион питания цыплят, содержащий необходимое количество определенных питательных веществ (для простоты, тиамина Т и ниацина Н).
Пищевая ценность рациона (в калориях) должна быть не менее заданной. Пусть для простоты смесь для цыплят изготавливается из двух продуктов – К и С. Известно содержание тиамина и ниацина в этих продуктах, а. также питательная ценность К и С (в калориях). Сколько К и С надо взять для одной порции куриного корма, чтобы цыплята получили необходимую им дозу веществ Н и Т и калорий (или больше), а стоимость порции была минимальна? Исходные данные для расчетов приведены в таблице 2.
Таблица 2 – Исходные данные для задачи [5, с. 111]
Содержание в 1 унции К |
Содержание в 1 унции С |
Потребность | |
Вещество Т |
0,10 мг |
0,25 мг |
1,00 мг |
Вещество Н |
1,00 мг |
0,25 мг |
5,00 мг |
Калории |
110,00 |
120,00 |
400,00 |
Стоимость 1 унции, в центах |
3,8 |
4,2 |
Задача линейного программирования имеет вид:
3,8 К + 4,2 С → min ,
0,10 К + 0,25 С ≥ 1,00 ,
1,00 К + 0,25 С ≥ 5,00 ,
110,00 К + 120,00 С ≥ 400,00 ,
К ≥ 0 ,
С ≥ 0 .
Ее графическое решение представим на рисунке 1.
Рисунок 1 – Графическое решение задачи [5, с. 112].
На рисунке 1 ради облегчения восприятия четыре прямые обозначены номерами (1) – (4). Прямая (1) – это прямая 1,00 К + 0,25 С = 5,00 (ограничение по веществу Н). Она проходит, как и показано на рисунке, через точки (5,0) на оси абсцисс и (0,20) на оси ординат. Обратите внимание, что допустимые значения параметров (К, С) лежат выше прямой (1) или на ней, в отличие от ранее рассмотренных случаев в предыдущей производственной задаче линейного программирования.
Прямая (2) – это прямая 110,00 К + 120,00 С = 400,00 (ограничение по калориям). Обратим внимание, что в области неотрицательных С она расположена всюду ниже прямой (1). Действительно, это верно при К=0, прямая (1) проходит через точку (0,20), а прямая (2) – через расположенную ниже точку (0, 400/120). Точка пересечения двух прямых находится при решении системы уравнений:
1,00 К + 0,25 С = 5,00 ,
110,00 К + 120,00 С = 400,00 .
Из первого уравнения К = 5 – 0,25 С.
Подставим во второе: 110 (5- 0,25 С) + 120 С = 400, откуда 550 – 27,5 С + 120 С = 400. Следовательно, 150 = - 92,5 С, т.е. решение достигается при отрицательном С. Это и означает, что при всех положительных С прямая (2) лежит ниже прямой (1). Значит, если выполнено ограничения по Н, то обязательно выполнено и ограничение по калориям. Мы столкнулись с новым явлением – некоторые ограничения с математической точки зрения могут оказаться лишними. С экономической точки зрения они необходимы, отражают существенные черты постановки задачи, но в данном случае внутренняя структура задачи оказалась такова, что ограничение по калориям не участвует в формировании допустимой области параметров и нахождении решения.
Прямая (4) – это прямая 0,1 К + 0,25 С = 1 (ограничение по веществу Т). Она проходит, как и показано на рисунке, через точки (10,0) на оси абсцисс и (0,4) на оси ординат. Обратите внимание, что допустимые значения параметров (К, С) лежат выше прямой (4) или на ней, как и для прямой (1).
Следовательно, область допустимых значений параметров (К, С) является неограниченной сверху. Из всей плоскости она выделяется осями координат (лежит в первом квадранте) и прямыми (1) и (4) (лежит выше этих прямых, а также включает граничные отрезки). Область допустимых значений параметров, т.е. точек (К, С), можно назвать «неограниченным многоугольником». Минимум целевой функции 3,8 К + 4,2 С может достигаться только в вершинах этого «многоугольника». Вершин всего три. Это пересечения с осями абсцисс (10,0) и ординат (0,20) прямых (1) и (4) (в каждом случае из двух пересечений берется то, которое удовлетворяет обоим ограничениям). Третья вершина – это точка А пересечения прямых (1) и (4), координаты которой находятся при решении системы уравнений:
0,10 К + 0,25 С = 1,00 ,
1,00 К + 0,25 С = 5,00 .
Из второго уравнения К = 5 – 0,25 С, из первого 0,10 (5 – 0,25 С) + 0,25 С = 0,5 – 0,025 С + 0,25 С = 0,5 + 0,225 С = 1, откуда С = 0,5/0,225 = 20/9 и К = 5 – 5/9 = 40/9. Итак, А = (40/9; 20/9).
Прямая (3) на рисунке 1 – это прямая, соответствующая целевой функции 3,8 К + 4,2 С . Она проходит между прямыми (1) и (4), задающими ограничения, и минимум достигается в точке А, через которую и проходит прямая (3). Следовательно, минимум равен 3,8х40/9 + 4,2х20/9 = 236/9. Задача об оптимизации смеси полностью решена.
ЗАКЛЮЧЕНИЕ
Как показал проведенный анализ, двойственность – это принцип, заключающийся в том, что для каждой задачи линейного программирования можно сформулировать двойственную задачу.
Каждой задаче линейного программирования можно определенным образом сопоставить некоторую другую задачу линейного программирования, называемую двойственной или сопряженной по отношению к исходной или прямой. Связь исходной и двойственной задач заключается главным образом в том, что решение одной из них может быть получено непосредственно из решения другой.
Смысл теоремы двойственности заключается в том, что двойственные оценки показывают приращение целевой функции, вызванные малыми изменениями свободного члена соответствующего ограничения задачи линейного программирования.
Решение двойственных задач помогает найти наиболее подходящий вариант при выборе оптимальных решений.
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ