Реферат Линейные и нелинейные модели в экономике
Работа добавлена на сайт bukvasha.net: 2015-10-28Поможем написать учебную работу
Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
от 25%
Подписываем
договор
МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ
Белорусский национальный технический университет
Факультет технологий управления и гуманитаризации
Кафедра менеджмента
курсовая работа
по дисциплине «Экономико-математические методы»
на тему:
«лИНЕЙНЫЕ И НЕЛИНЕЙНЫЕ МОДЕЛИ В ЭКОНОМИКЕ»
В - 10
Исполнитель: студентка гр.108116 Коваленко М.Н.
Руководитель:
Минск 2010
Оглавление
Введение. 3
Глава 1. Теоретическая часть. 3
1.1. Решение оптимизационной задачи линейного программирования. 3
1.2. Симплекс-метод. 3
1.3. Технология решения задач линейного программирования с помощью режима Поиска решений в среде EXCEL. 3
Первая теорема двойственности. 3
Вторая теорема двойственности. 3
Теорема об оценках. 3
1.5. Области допустимых решений для двойственных переменных. 3
Введение
Оптимизация - целенаправленная деятельность, заключающаяся в получении наилучших результатов при соответствующих условиях.
Поиски оптимальных решений привели к созданию специальных математических методов и уже в 18 веке были заложены математические основы оптимизации (вариационное исчисление, численные методы и др). Однако до второй половины 20 века методы оптимизации во многих областях науки и техники применялись очень редко, поскольку практическое использование математических методов оптимизации требовало огромной вычислительной работы, которую без ЭВМ реализовать было крайне трудно, а в ряде случаев - невозможно.
Для принятия оптимальных решений необходимо использовать научный метод. В науке управления научный метод подразумевает наличие определенной структуры процесса принятия решений и использование различных методов и моделей принятия решений.
Математическая модель — это математическое представление реальности.
Математическое моделирование — процесс построения и изучения математических моделей.
Все естественные и общественные науки, использующие математический аппарат, по сути занимаются математическим моделированием: заменяют реальный объект его математической моделью и затем изучают последнюю.
Проведение операционного исследования, построение и расчет математической модели позволяют проанализировать ситуацию и выбрать оптимальные решения по управлению ею или обосновать предложенные решения. Цель, которая преследуется в процессе исследования операций, заключается в том, чтобы выявить оптимальный способ действия при решении той или иной задачи организационного управления в условиях, когда имеют место ограничения технико-экономического или какого-либо другого характера.
За последние 30-40 лет методы моделирования экономики разрабатывались очень интенсивно. Они строились для теоретических целей экономического анализа и для практических целей планирования, управления и прогноза. Содержательно модели экономики объединяют такие основные процессы: производство, планирование, управление, финансы и т.д. Однако в соответствующих моделях всегда упор делается на какой-нибудь один процесс (например, процесс планирования), тогда как все остальные представляются в упрощенном виде.
В зависимости от своей постановки любая из задач оптимизации может решаться различными методами, и наоборот – любой метод может применяться для решения многих задач. Методы оптимизации могут быть скалярными (оптимизация проводится по одному критерию), векторными (оптимизация проводится по многим критериям), поисковыми (включают методы регулярного и методы случайного поиска), аналитическими (методы дифференциального исчисления, методы вариационного исчисления и др.), вычислительными (основаны на математическом программировании, которое может быть линейным, нелинейным, дискретным, динамическим, стохастическим, эвристическим и т.д.), теоретико-вероятностными, теоретико-игровыми и др. Подвергаться оптимизации могут задачи как с ограничениями, так и без них.
Нелинейные модели - это модели, в которых либо целевая функция, либо какое-нибудь из ограничений (либо все ограничения) нелинейные по управляющим переменным. Для нелинейных моделей нет единого метода расчета. В зависимости от вида нелинейности, свойств функции и ограничений можно предложить различные способы решения. Однако может случится и так, что для поставленной нелинейной задачи вообще не существует метода расчета. В этом случае задачу следует упростить, либо сведя ее к известным линейным моделям, либо просто линеаризовав модель.
В линейных моделях целевая функция и ограничения линейны по управляющим переменным. Построение и расчет линейных моделей являются наиболее развитым разделом математического моделирования, поэтому часто к ним стараются свести и другие задачи либо на этапе постановки, либо в процессе решения. К классическим задачам линейного программирования относятся задачи на составление оптимального плана перевозок (транспортная задача), задачи о загрузке оборудования, о смесях, о раскрое материалов, об ассортименте продукции, о размещении производства и управлении производственными запасами, задачи о питании, о рациональном использовании сырья и материалов и др. Для линейных моделей любого вида и достаточно большой размерности известны следующие стандартные методы решения:
1. Графический метод;
2. Симплекс-метод;
3. Двухэтапный метод. Он позволяет получить сначала стартовую точку, т.е. начальное допустимое решение, а затем оптимальное решение. В ограничения вводятся искусственные переменные необходимые для получения стартовой точки;
4. Метод больших штрафов.
Глава 1. Теоретическая часть
1.1. Решение оптимизационной задачи линейного программирования
Линейное программирование - один из первых и наиболее подробно изученных разделов математического программирования. Именно линейное программирование явилось тем разделом, с которого начала развиваться сама дисциплина «математическое программирование». Термин «программирование» в названии дисциплины ничего общего с термином «программирование (т.е. составление программ) для ЭВМ» не имеет, так как дисциплина «линейное программирование» возникла еще до того времени, когда ЭВМ стали широко применяться при решении математических, инженерных, экономических и др. задач. Термин «линейное программирование» возник в результате неточного перевода английского «linear programming». Одно из значений слова «programming» - составление планов, планирование. Следовательно, правильным переводом «linear programming» было бы не «линейное программирование», а «линейное планирование», что более точно отражает содержание дисциплины. Однако, термин линейное программирование, нелинейное программирование и т.д. в нашей литературе стали общепринятыми.
Можно сказать, что линейное программирование применимо для построения математических моделей тех процессов, в основу которых может быть положена гипотеза линейного представления реального мира: экономических задач, задач управления и планирования, оптимального размещения оборудования и пр.
Задачами линейного программирования называются задачи, в которых линейны как целевая функция, так и ограничения в виде равенств и неравенств. Кратко задачу линейного программирования можно сформулировать следующим образом: найти вектор значений переменных, доставляющих экстремум линейной целевой функции при m ограничениях в виде линейных равенств или неравенств.
Первые постановки задач линейного программирования были сформулированы известным советским математиком Л.В.Канторовичем, которому за эти работы была присуждена Нобелевская премия по экономике.
Значительное развитие теория и алгоритмический аппарат линейного программирования получили с изобретением и распространением ЭВМ и формулировкой американским математиком Дж. Данцингом симплекс-метода.
В настоящее время линейное программирование является одним из наиболее употребительных аппаратов математической теории оптимального принятия решения. Для решения задач линейного программирования разработано сложное программное обеспечение, дающее возможность эффективно и надежно решать практические задачи больших объемов. Эти программы и системы снабжены развитыми системами подготовки исходных данных, средствами их анализа и представления полученных результатов.
Искусство математического моделирования состоит в том, чтобы учесть как можно больше факторов по возможности простыми средствами. Именно в силу этого процесс моделирования часто носит итеративный характер. На первой стадии строится относительно простая модель и проводится ее исследование, позволяющее понять, какие из существенных свойств изучаемого объекта не улавливаются данной формальной схемой. Затем происходит уточнение, усложнение модели.
В большинстве случаев первой степенью приближения к реальности является модель, в которой все зависимости между переменными, характеризующими состояние объекта, предполагаются линейными. Здесь имеется полная аналогия с тем, как весьма важна и зачастую исчерпывающая информация о поведении произвольной функции получается на основе изучения ее производной — происходит замена этой функции в окрестности каждой точки линейной зависимостью. Значительное количество экономических, технических и других процессов достаточно хорошо и полно описывается линейными моделями.
Современные методы линейного программирования достаточно надежно решают задачи общего вида с несколькими тысячами ограничений и десятками тысяч переменных. Для решения сверхбольших задач используются уже, как правило, специализированные методы.
Различают три основные формы задач линейного программирование в зависимости от наличия ограничений разного типа.
Стандартная задача ЛП
или, в матричной записи,
где
Стандартная задача важна ввиду наличия большого числа прикладных моделей, сводящихся наиболее естественным образом к этому классу задач ЛП.
Каноническая задача ЛП
или, в матричной записи,
Основные вычислительные схемы решения задач ЛП разработаны именно для канонической задачи.
Общая задача ЛП
В этой задачи часть ограничений носит характер неравенств, а часть является уравнениями. Кроме того, не на все переменные наложено условие неотрицательности:
Здесь
Все три перечисленные задачи эквивалентны в том смысле, что каждую из них можно простыми преобразованиями привести к любой из двух остальных.
При изучении задач ЛП сложилась определенная терминалогия. Линейная форма
1.2. Симплекс-метод
Симплекс – метод – это алгебраический метод решения задач линейного программирования. В процессе вычислений производиться последовательный обход вершин многогранника решений (ОДР.) с проверкой в каждой вершине условий оптимальности. При этом каждый переход в смежную вершину сопровождается улучшением целевой функции.
Вычислительные процедуры симплекс - метода.
При графическом методе решения ЗЛП оптимальному решению соответствует всегда одна из угловых (экстремальных) точек пространства решений. Это результат положен в основу построения симплекс-метода. Симплекс-метод не обладает наглядностью геометрического представления пространства решений.
Симплекс-метод реализует упорядоченный процесс, при котором, начиная с некоторой исходной допустимой угловой точки, осуществляются последовательные переходы от одной допустимой экстремальной точки к другой, пока не будет найдена точка оптимального решения.
Обозначим:
Каждая вершина многогранника решений имеет
Ненулевые переменные называются базисными, нулевые переменные – небазисными.
Дополним систему равенств равенством целевой функции, при этом будем считать, что
Для получения решения составляется начальный допустимый базис, в котором базисные переменные должны быть представлены в виде единичных орт. Это означает, что уравнения, представляющие данную вершину должны включать каждую базисную переменную только в одной строке с коэффициентом, равным 1.
При выборе начального допустимого базиса для составления симплекс-таблицы на первом шаге СТ(0) исходные
При составлении симплекс-таблицы придерживаются следующих правил:
-в крайнем левом столбце располагаются базисные переменные и
-в крайнем правом столбце располагаются правые части ограничений;
-в первой строке располагаются переменные в определённом порядке:
сначала
| | | | | | | | ПЧ |
| | 1 | - | - | 0 | 0 | 0 | 0 |
| | 0 | | | 1 | 0 | 0 | |
| | 0 | | | 0 | 1 | 0 | |
| | 0 | | | 0 | 0 | 1 | |
Рисунок 1.1 Пример симплекс-таблицы
Оптимальность любой из вершин определяется коэффициентами при небазисных переменных в
Для задачи максимизации данная вершина является оптимальной, если все коэффициенты при небазисных переменных в
Для задачи минимизации данная вершина является оптимальной, если все коэффициенты при небазисных переменных в
Если в задаче максимизации (минимизации) у одной небазисной переменной в
Исключаемой переменой будет та базисная переменная, которая первой обратится в "0" при переходе в смежную вершину после ввода включаемой переменной.
Столбец включаемой переменной будем называть разрешающим столцом.
Строку исключаемой переменной будем называть разрешающей строкой.
Пересечение разрешающего столбца и строки определяют разрешающий элемент (РЭ).
Чтобы определить исключаемую переменную необходимо:
-разделить правые части всех базисных переменных (кроме
-выбрать из полученных отношений наименьшее.
Делить на "0" и отрицательную величину нельзя, т. к. это приводит к отсутствию пересекающейся вершины или к вершине вне ОДР.
Для перехода в смежную вершину необходимо сформировать матрицу перехода B(0), которая определит связь между СТ(0) и СТ(1): СТ(1) = В(0) СТ(0).
Для произвольной квадратной матрице размерности n, имеющей в качестве (n - 1) столбца единичные орты, расположенные в соответствии с единичными ортами единичной матрицы, и одного произвольного столбца с ненулевым элементом на главной диагонали, обратная матрица находится по следующему правилу:
Рисунок 1.2 Транспонированная матрица
Каждый элемент j – столбца делится на РЭ и меняет знак на противоположный, кроме разрешающего элемента.
Искусственный начальный базис. М – метод.
Если исходное ограничение записано в виде равенства "=" или имеет знак "
Переменные R определяют начальный допустимый базис с точки зрения возможного дальнейшего перехода в одну из вершин ОДР. За использование искусственных переменных в целевой функции вводится штраф М. В задаче максимизации М отрицательное (М<<0), в задаче минимизации М положительное (М>>0).
Свойство М: При сложении (вычитании) с любой конечной величиной
При составлении начальной симплекс-таблицы все переменные начального допустимого базиса (дополнительные и искусственные) должны располагаться в последних m столбцах перед правой частью.
Алгоритм получения оптимального решения:
1. Переход от неравенств к равенствам с учётом правил перехода - введение остаточных, избыточных, искусственных переменных и коэффициентов штрафа;
2. Определение числа базисных и небазисных переменных;
3. Получение
4. Заполнение СТ(0). Перенесение коэффициентов
5. Исследование
определение разрешающего столбца (по знаку и величине коэффициентов небазисных переменных
определение включаемой переменной из небазисных переменных;
6. Определение разрешающей строки по условию допустимости:
определение минимального отношения при делении правых частей ограничений на положительные коэффициенты разрешающего столбца;
определение исключаемой переменной из начального базиса;
7. Определение разрешающего элемента РЭ;
8. Получение B (0). Замена в матрице начального базиса коэффициентов исключаемой переменной на коэффициенты включаемой переменной; вычисление B (0) по соответствующему правилу;
9. Определение элементов СТ(1) = В(0) СТ(0);
10. Исследование
Если условие не выполнено, то вычисления продолжаются и необходимо повторить пункты 5-10.
Если условие оптимальности выполнено, то решение ЗЛП симплекс-методом закончено, необходимо выделить оптимальные значения переменных и оптимальное значение целевой функции.
1.3. Технология решения задач линейного программирования с помощью режима Поиска решений в среде EXCEL.
Поиск решения - это надстройка EXCEL, которая позволяет решать оптимизационные задачи. Ecли, в меню Сервис отсутствует команда Поиск решения, значит, необходимо загрузить эту надстройку. Выберите команду СервисÞ
Надстройки и активизируйте надстройку Поиск решения. Если же этой надстройки нет в диалоговом окне Надстройки, то вам необходимо обратиться к панели управления Windows, щелкнуть на пиктограмме Установка и удаление программ и с помощью программы установки Excel (или Office) установить надстройку Поиск решения.
После выбора команд Сервис Þ Поиск решения появится диалоговое окно Поиск решения.
В диалоговом окне Поиск решения есть три основных параметра:
• Установить целевую ячейку
• Изменяя ячейки
• Ограничения
Сначала нужно заполнить поле Установить целевую ячейку. Во всех задачах для средства Поиск решения оптимизируется результат в одной из ячеек рабочего листа. Целевая ячейка связана с другими ячейками этого рабочего листа с помощью формул. Средство Поиск решения использует формулы, которые дают результат в целевой ячейке, для проверки возможных решений. Можно выбрать поиск наименьшего или наибольшего значения для целевой ячейки илиже установить конкретное значение.
Второй важный параметр средства Поиск решения — это параметр Изменяя ячейки. Изменяемые ячейки — это те ячейки, значения в которых будут изменяться для того, чтобы оптимизировать результат в целевой ячейке. Для поиска решения можно указать до 200 изменяемых ячеек. К изменяемым ячейкам предъявляется два основных требования. Они не должны содержать формул, и изменение их значений должно отражаться на изменении результата в целевой ячейке. Другими словами, целевая ячейка зависима от изменяемых ячеек.
Третий параметр, который нужно вводить, для Поиска решения – это ограничения.
Для решения задачи необходимо:
1) Указать адреса ячеек, в которые будет помещен результат решения (изменяемые ячейки).
2) Ввести исходные данные.
3) Ввести зависимость для целевой функции
4) Ввести зависимости для ограничений.
Запустить Поиск решений.
5) Назначение целевой функции (установить целевую ячейку).
6) Ввод ограничений.
7) Ввод параметров для решения ЗЛП.
Рассмотрим технологию решения задачи линейного программирования в Excel.
Решить ЗЛП:
Перейдем к решению задачи в Excel.
1. В ячейки А3:В3 введем значения коэффициентов целевой функции (18 и 12).
2. В ячейки А10:В12 введем значения коэффициентов ограничений (технологическую матрицу).
3. В ячейки В15:В17 введем значения правых частей ограничений (запасы).
4. Отведем под переменные
Рисунок 1.2 Ввод исходных данных для задачи планирования производства
Выполним расчеты:
5. В ячейку С3 введем формулу: =СУММПРОИЗВ(А3:В3;А7:В7), которая представляет целевую функцию.
6. В ячейку А15 введем формулу: = СУММПРОИЗВ($A$7:$B$7;А10:В10), которая представляет левую часть первого ограничения.
7. С помощью автозаполнения скопируем формулу, введенную в ячейку А15, в ячейки А16, А17.
Рабочий лист Excel примет вид, показанный на рис. 2 и на рис. 3 (значения ячеек, в которые вносились формулы, будут пока равны нулю, так как неизвестны
Рисунок 1.3 Рабочий лист Excel после внесения формул
Рисунок 1.4 Расчеты для решения задачи планирования производства
8. Для дальнейшего решения задачи необходимо вызвать команду меню Сервис / Поиск решения. (Если эта команда отсутствует, то нужно зайти в меню Сервис/Надстройки и установить флажок возле Поиска решения).
9. Диалоговое окно Поиск решения заполним, как показано на рисунке 1.5
Рисунок 1.5 Заполненное окно Поиск решения
- Установить целевую ячейку С3, равной максимальному значению
- Изменяя ячейки А7:В7
- Ограничения: нажать кнопку Добавить и в открывшееся окно ввести диапазоны (можно их выделить, они сами впишутся в окно Добавить):
А15:А17 <= В15:В17
А7:В7 >= 0
- После ввода последнего (второго) ограничения в окне Добавить нужно нажать кнопку ОК.
10. Далее следует нажать кнопку Выполнить, после чего будет получено решение
Рисунок 1.6 Полученное решение задачи планирования производства
Ответ задачи: Функция
1.4.
Постановка и решение двойственной задачи линейного программирования в экономике
Двойственная задача (ДЗ) – это вспомогательная задача линейного программирования, формулируемая с помощью определённых правил непосредственно из условий прямой задачи. Заинтересованность в определении оптимального решения прямой задачи путём решения двойственной к ней задачи обусловлена тем, что вычисления при решении ДЗ могут оказаться менее сложными, чем при ПЗ. Трудоёмкость вычислений при решении ЗЛП в большей степени зависит от числа ограничений, а не от количества переменных. Для перехода к ДЗ необходимо, чтобы прямая задача была записана в стандартной канонической форме. При представлении ПЗ в стандартной форме в состав переменных
С каждой задачей линейного программирования тесно связана другая линейная задача, называемая двойственной; первоначальная задача называется исходной или прямой.
Связь исходной и двойственной задач заключается, в частности, в том, что решение одной из них может быть получено непосредственно из решения другой.
Переменные двойственной задачи yi называют объективно обусловленными оценками, или двойственными оценками, или «ценами» ресурсов, или теневыми ценами.
Каждая из задач двойственной пары фактически является самостоятельной задачей линейного программирования и может быть решена независимо от другой.
Двойственная задача по отношению к исходной составляется согласно следующим правилам:
1) целевая функция исходной задачи формулируется на максимум, а целевая функция двойственной задачи— на минимум, при этом в задаче на максимум все неравенства в функциональных ограничениях имеют вид £, в задаче на минимум — вид ³;
2) матрица А, составленная из коэффициентов при неизвестных в системе ограничений исходной задачи и аналогичная матрица Ат в двойственной задаче получаются друг из друга транспонированием;
3) число переменных в двойственной задаче равно числу функциональных ограничений исходной задачи, а число ограничений в системе двойственной задачи — числу переменных в исходной задаче;
4) коэффициентами при неизвестных в целевой функции двойственной задачи являются свободные члены в системе ограничений исходной задачи, а правыми частями в ограничениях двойственной задачи — коэффициенты при неизвестных в целевой функции исходной задачи;
5) каждому ограничению одной задачи соответствует переменная другой задачи: номер переменной совпадает с номером ограничения; при этом ограничению, записанному в виде неравенства £, соответствует переменная, связанная условием неотрицательности. Если функциональное ограничение исходной задачи является равенством, то соответствующая переменная двойственнвой; задачи может принимать как положительные, так и отрицательные значения
Модель исходной (прямой) задачи в общем виде может быть записана следующим образом:
Модель двойственной задачи имеет вид:
Две приведенные задачи образуют пару симметричных двойственных задач.
Основные утверждения о взаимно двойственных задачах содержатся в двух следующих теоремах.
Первая теорема двойственности.
Для взаимно двойственных задач имеет место один из взаимоисключающих случаев:
1. В прямой и двойственной задачах имеются оптимальные решения, при этом значения целевых функций на оптимальных решениях совпадают: f(x) = g(y).
2. В прямой задаче допустимое множество не пусто, а целевая функция на этом множестве не ограниченна сверху. При этом у двойственной задачи будет пустое допустимое множество.
3. В двойственной задаче допустимое множество не пусто, а целевая функция на этом множестве не ограничена снизу. При этом у прямой задачи допустимое множество оказывается пустым.
4.Обе из рассматриваемых задач имеют пустые допустимые множества.
Экономический смысл первой теоремы двойственности следующий. План производства Х и набор оценок ресурсов У оказываются оптимальными тогда и только тогда, когда прибыль от реализации продукции, определенная, при известных заранее ценах продукции равна затратам на ресурсы по «внутренним» (определяемым только из решения задачи) ценам ресурсов yi. Для всех же других планов Х и У обеих задач прибыль от продукции всегда меньше (или равна) стоимости затраченных ресурсов:
f(X) < g(Y}, т. е. ценность всей выпущенной продукции не превосходит суммарной оценки имеющихся ресурсов. Значит величина g(Y) - f(X) характеризует производственные потери в зависимости от рассматриваемой производственной программы и выбранных Оценок ресурсов.
Из первой теоремы двойственности следует, что при оптимальной
производственной программе и векторе оценок ресурсов производственные потери равны нулю.
Вторая теорема двойственности
(теорема о дополняющей нежесткости)
Пусть X=(x1,x2,...xn) - допустимое решение прямой задачи, а Y= (y1,y2,...ym) - допустимое решение двойственной задачи. Для того чтобы они были оптимальными решениями соответственно прямой и двойственной задач необходимо и достаточно, чтобы выполнялись следующие соотношения:
Условия (*) и (**) позволяют, зная оптимальное решение одной из взаимно двойственных задач, найти оптимальное решение другой задачи.
Из второй теоремы двойственности в данном случае следуют такие требования на оптимальную производственную программу X=(X1,X2,...,Xn) и оптимальный вектор оценок Y=(Y1,Y2,...,Ym):
Условия (4) можно интерпретировать так: если оценка yi единицы ресурса i-го вида положительна, то при оптимальной производственной программе этот ресурс используется полностью, если же ресурс используется не полностью, то его оценка равна нулю. Из условия (5) следует, что если j-й вид продукции вошел в оптимальный план, то он в оптимальных оценках неубыточен, если же j-й вид продукции убыточен, то он не войдет в план, не будет выпускаться.
Теорема об оценках.
Значения переменных Yi в оптимальном решении двойственной задачи представляют собой оценки влияния свободных членов bi системы ограничений-неравенств прямой задачи на величину
Решая ЗЛП симплексным методом, мы одновременно решаем двойственную ЗЛП. Переменные двойственной задачи yi называют объективно обусловленными оценками.
Рассмотрим экономическую интерпретацию двойственной задачи на примере задачи оптимального использования ресурсов.
1.5. Области допустимых решений для двойственных переменных
Вид ограничений прямой задачи, а также дополнительные и искусственные переменные, образующие начальный допустимый базис, определяют ОДР для соответствующих двойственных переменных.
1. Рассмотрим ограничение (2) прямой задачи:
2. Рассмотрим ограничение (3) прямой задачи:
При введении искусственных переменных в целевую функцию вводятся коэффициенты штрафа М, поэтому для задачи максимизации получим:
2.
Т. о., при решении задачи максимизации ограничениям прямой задачи, имеющим знак равенства, соответствуют двойственные переменные, не ограниченные в знаке
3. Рассмотрим ограничение (4) прямой задачи:
В целевой функции избыточные переменные имеют коэффициенты, равные нулю (
3. Т. о., при решении задачи максимизации ограничениям прямой задачи, имеющим знак
4. Если в прямой задаче есть переменная, неограниченная в знаке, то в двойственной задаче получатся два ограничения, имеющие одинаковые коэффициенты при двойственных переменных, но разные знаки ограничений. Для удобства решения эти ограничения сворачивают в одно со знаком равенства (тем самым число ограничений двойственной задачи сводится к числу исходных переменных прямой задачи).
По аналогии можно записать условия двойственной задачи при решении задачи минимизации. Для удобства пользования некоторые соотношения при переходе от прямой задаче к двойственной приведены в таблице.
| Прямая задача | Двойственная задача | |||
| Целевая функция | Ограничения | Целевая функция | Ограничения | Переменные |
| Максимизация | | Минимизация | | |
| = | | |||
| | | |||
| Минимизация | | Максимизация | | |
| = | | |||
| | | |||
Таблица 1.1 Переход от прямой задачи к двойственной
В двойственной задаче переменные могут быть неотрицательными (
если переменная
если
Такие подстановки следует использовать во всех ограничениях, содержащих эти переменные, а также в выражении для целевой функции.
После приведения ДЗ к стандартному виду используется симплекс - метод. Алгоритм получения решения тот же, что и для прямой задачи.
