Вспомогательная задача линейного программирования формулируемая с помощью

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

=== Скачать файл ===

№6 Соотношения двойственности в ЗЛП.

Экономический смысл двойственной задачи линейного программирования Студентка группы дэф-202 Рыжинская Наталия Определение двойственной злп

Под двойственной задачей понимается вспомогательная задача линейного программирования, формулируемая с помощью определённых правил непосредственно из условий прямой задачи. Заинтересованность в определении оптимального решения прямой задачи путём решения двойственной к ней задачи обусловлена тем, что вычисления при решении ДЗ могут оказаться менее сложными. Трудоёмкость вычислений при решении ЗЛП в большей степени зависит от числа ограничений, а не от количества переменных. Целью курсового проекта является изучить литературу по выбранной теме и научиться применять на практике симплекс — метод для решения прямой и двойственной задачи линейного программирования, а также решить двойственную задачу линейного программирования с помощью программы MSExcel. В первой главе рассматриваются основные понятия и предложения теории двойственности ЗЛП, виды математических моделей двойственных задач и их экономическая интерпретация. С экономической точки зрения двойственную задачу можно интерпретировать так: А исходную задачу определим следующим, образом: Большинство задач линейного программирования изначально определяются как исходные или двойственные задачи. Сделав вывод можно говорить о паре двойственных задач линейного программирования. Каждой задаче линейного программирования можно определенным образом сопоставить некоторую другую задачу линейного программирования , называемую двойственной или сопряженной по отношению к исходной или прямой задаче. Дадим определение двойственной задачи по отношению к общей задаче линейного программирования , состоящей, как мы уже знаем, в нахождении максимального значения функции:. Сравнивая две сформулированные задачи, видим, что двойственная задача составляется согласно следующим правилам:. Целевая функция исходной задачи задается на максимум, а целевая функция двойственной на минимум. Число переменных в двойственной задаче равно числу ограничений в системе исходной задачи, а число ограничений в системе двойственной задачи — числу переменных в исходной задаче. Коэффициентами при неизвестных в целевой функции двойственной задачи являются свободные члены в системе исходной задачи, а правыми частями в соотношениях системы двойственной задачи — коэффициенты при неизвестных в целевой функции исходной задачи. Если же переменная x j может принимать как положительные, так и отрицательные значения, то 1 — соотношение в системе представляет собой уравнение. Аналогичные связи имеют место между ограничениями исходной задачи и переменными двойственной задачи. Если i — соотношение в системе исходной задачи является неравенством, то i -я переменная двойственной задачи. В противном случае переменная у j может принимать как положительные, так и отрицательные значения. Двойственные пары задач обычно подразделяют на симметричные и несимметричные. Таким образом, переменные обеих задач могут принимать только лишь неотрицательные значения. Двойственная задача тесно связана задачей линейного программирования. Задача первоначальная называется исходной. Решение двойственной задачи может быть получено из решения исходной и наоборот. Связующим фактом этих двух задач являются коэффициенты C j функции исходной задачи. Данные коэффициенты называются свободными членами системы ограничений двойственной задачи. Коэффициенты B i системы ограничений исходной задачи называются коэффициентами двойственной задачи. Транспонированная матрица коэффициентов системы ограничений исходной задачи является матрицей коэффициентов системы ограничений двойственной задачи. Рассмотрим задачу использования ресурсов. На изготовление 1 ед. Необходимо определить план выпуска продукции, обеспечивающий ее максимальный выпуск в стоимостном выражении. Определим ресурсы, которые потребуются для изготовления товара. Обозначим за единицу стоимости ресурсов единицу стоимости выпускаемого товара. Цена израсходованных ресурсов не должна превышать цены окончательного товара. Система ограничений исходной задачи в несимметричных двойственных задачах определяется как равенство. Двойственная же задача задается, как неравенство, причем переменные могут быть и отрицательными. Что бы проще понимать постановку задачи будем интерпретировать ее в матричной форме. Теорема двойственности устанавливает связь между оптимальными планами пары двойственных задач. Если линейная функция одной из задач не ограничена, то другая не имеет решения. Будем считать, что исходная задача имеет оптимальный план. План определен симплексным методом. Можно считать, что конечный базис состоит из т первых векторов A 1 , A 2 ,…, A m. Будем считать, что D является матрицей, составленной из компонент векторов конечного базиса A 1 , A 2. В этой таблице каждому вектору A j соответствует вектор X j. Для этого ограничения 1. Тогда на основании 1. Таким образом, значение линейной функции двойственной задачи от Y численно равно минимальному значению линейной функции исходной задачи. Для доказательства второй части теоремы допустим, что линейная функция исходной задачи не ограничена снизу. Это выражение лишено смысла, следовательно, двойственная задача не имеет решений. Аналогично предположим, что линейная функция двойственной задачи не ограничена сверху. Это выражение также лишено смысла, поэтому исходная задача не имеет решений. Доказанная теорема позволяет при решении одной из двойственных задач находить оптимальный план другой. Используя эту итерацию, найдем оптимальный план двойственной задачи. В последний базис входят векторы A 5, A 4, A 2 ; значит,. Обратная матрица D -1 образована из коэффициентов, стоящих в столбцах A 1 , A 3 , A 6 четвертой итерации:. Разновидностью двойственных задач линейного, программирования являются двойственные симметричные задачи, в которых система ограничений как исходной, так и двойственной задач задается неравенствами, причем на двойственные переменные налагается условие неотрицательности. Систему неравенств с помощью дополнительных переменных можно преобразовать в систему уравнений, поэтому всякую пару симметричных двойственных задач можно преобразовать в пару несимметричных, для которых теорема двойственности уже доказана. Используя симметричность, можно выбрать задачу, более удобную для решения. Объем задачи, решаемой с помощью ЭВМ, ограничен числом включаемых строк, поэтому задача, довольно громоздкая в исходной постановке, может быть упрощена в двойственной формулировке. При вычислениях без помощи машин использование двойственности упрощает вычисления. Очевидно, для того чтобы записать двойственную задачу, сначала необходимо систему ограничений исходной задачи привести к виду. Для этого второе неравенство следует умножить на Основываясь на рассмотренных несимметричных и симметричных двойственных задач отметим, что пары двойственных задач математических моделей могут быть представлены следующим образом:. Поэтому до того, как сформулировать двойственную задачу для данной исходной, необходимо систему ограничений исходной задачи преобразовать должным образом. Для получения решения исходной задачи можно перейти к двойственной. А используя оценки ее оптимального плана, можно определить оптимальное решение исходной задачи. Если рассмотреть первую симплексную таблицу с единичным дополнительным базисом, тогда переход к двойственной задаче не обязателен. Это связано с тем, что в столбцах определена исходная задача, а в строках — двойственная. С j являются оценками плана исходной задачи. Найдем решение двойственной задачи по симплексной таблице. В симплексной таблице прописана исходная задача. Также определим оптимальный план двойственной задачи. Также найдем и оптимальный план исходной задачи. Допустим нужно определить исходную задачу линейного программирования, которая поставлена в общем виде: Этот план не оптимальный. Потому что оценки оптимального плана двойственной задачи должны быть неотрицательными и выбранный базис X содержит отрицательную компоненту и не является планом исходной задачи, а с другой стороны. Данный вектор относится к отрицательной оценке, его необходимо включить в базис двойственной задачи. Просматриваем i-ю строку для выбора вектора, включаемого в базис исходной задачи. Поэтому нет решений исходной задачи. Также находим вектор, который соответствует minq 0j Z j —C j при решении исходной задачи на максимум, а также maxq 0j Z j —C j при значении исходной задачи на минимум. Найденный вектор включаем в базис исходной задачи. Направляющей строкой определяется вектор, который надо убрать из базиса исходной задачи. Данный подход к решению задачи не приводит к росту количества отрицательных компонент вектора X. Обычным симплексным методом определяется оптимальный план. Задачи линейного программирования можно решать двойственным симплексным методом. Системы ограничений в задачах при положительном базисе имеют свободные члены любого знака. Двойственный симплексный метод позволяет значительно уменьшить размеры симплексной таблицы и количество преобразований системы ограничений. Необходимо спланировать работу швейной мастерской на некоторый период. Установлен перечень выпускаемой продукции, известна рыночная цена каждого продукта. Для производства продукции используются ресурсы: Установлен полный перечень этих ресурсов и общее количество каждого ресурса, которое может быть израсходовано в плановом периоде. Известен расход каждого ресурса на единицу каждого продукта. Необходимо определить, сколько каждой продукции нужно производить, чтобы суммарная рыночная цена всей продукции выпуск, выручка была наибольшей. Исходные данные задачи запишем в виде матрицы. Каждая строка матрицы соответствует одному ресурсу, каждый столбец — одному продукту. Справа от каждой строки записана величина ограничения по ресурсу b 1 ,…, b i ,…, b m ; внизу каждого столбца - цена продуктов с 1 ,…, с j ,…, с m. В каждой клеточке матрицы записаны так называемые технологические коэффициенты a ij , показывающие расход i -го ресурса на производство единицы j -го продукта. D4 — технологические коэффициенты расход ресурсов при единичных интенсивностях технологических способов ;. Запишем формулы в ячейки G2: Установить курсор на G2. На панели инструментов выбрать значок формул f. В нем нужно указать, где располагаются операнды. G4 формулу скопировать из G2. Аналогичным образом записать формулу целевой функции в ячейку G6. Теперь нужно указать остальные условия решения задачи. Установить курсор на ячейку целевой функции G6. Появится окно, в котором нужно указать:. D8 0 — неотрицательности переменных;. F4 — плановый расход ресурсов меньше их запаса. Теперь электронная модель сформирована и можно решать задачу. Если электронная модель сформирована правильно, то будет получено сообщение, что задача решена. Результат решения находится на листе EXCEL и в трех отчетах: Основные результаты видны в таблице рис. По сравнению с условиями задачи, показанными на рис. Значения переменных в ячейках B8: Плановый расход ресурсов в ячейках G2: Кроме результатов в электронной таблице EXCEL готовит три отчета: Отчет по результатам изображен на рис 4. Эти величины в литературе имеют различные названия: Канторовичу, двойственные оценки по Д. Данцигу, оптимальные цены, теневые цены и другие. В дальнейшем будем называть их наиболее распространенным именем — двойственные оценки и обозначать — v i , где i — номер ограничения. Отчет по пределам показан на рис. Верхний предел равен соответственно 86, 0 и , так устанавливают ограничения по ресурсам. Целевой результат показывает значение целевой функции при соответствующих значениях переменных. В- бюджет, то есть количество денег, которое можно израсходовать на приобретение ресурсов для производства продукции, а s i — рыночная цена i -го ресурса. Тогда единственное ограничение по ресурсам будет выглядеть следующим образом:. Решим задачу на максимум продукции с ограничением по бюджету. За основу возьмем электронную модель на рис. I6 H6 — совокупные издержки не больше бюджета. Если ограничения по ресурсам в модели имеют смысл и не больше и не меньше , причем все величины не отрицательные, то в общем случае вывод о существовании или отсутствии допустимого плана сделать нельзя. Все зависит от конкретных значений величин и. Возможен случай, когда для некоторого k -го ресурса установлено такое ограничение , что оно не может быть выполнено из-за других ограничений. Тогда нет ни одного допустимого плана. В результате проделанной работы был рассмотрен теоретический материал, посвященный решению двойственных задач линейного программирования, и процесс их решения был автоматизирован, с помощью программы MSExcel. Результатом работы над курсовым проектом является программа для решения задач линейного программирования с помощью двойственного симплекс-метода. Все материалы в разделе 'Экономико-математическое моделирование'. Прямые и двойственные задачи линейного программирования, особенности и методика их решения. Основные положения теоремы двойственности. Виды математических моделей двойственных задач. Разработка программы планирования работы швейной мастерской в Excel. Введение Под двойственной задачей понимается вспомогательная задача линейного программирования, формулируемая с помощью определённых правил непосредственно из условий прямой задачи. Курсовой проект состоит из введения, двух глав и заключения. Во второй главе рассматривается решение двойственной задачи с помощью программы MSExcel. Двойственность в линейном программировании 1. Дадим определение двойственной задачи по отношению к общей задаче линейного программирования , состоящей, как мы уже знаем, в нахождении максимального значения функции: Ячейка Имя Результат Норир. Графическое представление частотных характеристик. Канторовиче и линейном программировании. Экономико-математические методы и прикладные модели. Математические модели и ценности человеческого выбора. Двойственность Познания по Учению Св. Григория Паламы Double Knowledge According to Gregory Palamas. Использование SQL в прикладном программировании. Первоначальные сведения о программировании на языке Pascal.

Массаж и гимнастика

История горного университета

Canon d1100 характеристики отзывы

О чем можно написать эссе

Впч 16 значение

Как с помощью заземления остановить электрический счетчик

Турция 4 звезды первая линия

Изменение исковых требований апк рф

Сколько стоит письмо из россии в беларусь

Электронный каталог преимущества

Схема консервного завода

При каком значении k векторы коллинеарны