 |
Переход от исходной задачи линейного программирования к канонической. Экономический смысл дополнительных переменных.
|
|
|
|
История развития методов оптимизации в экономике.
Задача линейного программирования основывается на задачах поиска экстремума функций при наличие ограничений типа неравенств.
В 1820 Фурье и затем в 1947 Данциг предложили использовать Симплексный метод для решения задач линейного программирования. Который по сейм день является основным.
Присутствие в названии дисциплины термина «Программирование» связанно с тем. Что исследование линейных задач было в сфере экономики, на английском языке слово programming означает планирование, составление программ или планов. Термин Линейное программирование был предложен Данцигом в 1949 году для изучения теоретических и алгоритмических задач, связанных с оптимизацией линейных функций при линейных ограничениях.
Поэтому наименование Математическое программирование связанно с выбором оптимальной программы действий.
Одними из первых, исследовавших в общей форме задачи линейного программирования были Джон Фон Нейман и советский академик Канторович, который сформулировал ряд задач линейного программирования, и предложивший в 1939 году метод их решения (метод разрешающих множителей).
В 1931 году Эгервари рассмотрел задачу линейного программирования имеющую название «проблема выбора» метод получил название «Венгерский метод».
В 1949 Канторович и Гавурин разработали метод потенциалов, который применяется для решения транспортных задач.
Основные понятия и обозначения в линейном программировании.
1. Критерий оптимальности - показатель, количественно отражающий цель решения.
2. Ограничение – условие, которое накладывается на переменную или группу переменных, отражающее логику и взаимосвязь моделей.
|
|
|
Система ограничений должна быть совместна и неопределенна, в т.ч. условие неотрицательности переменных.
3. Целевая функция (функционал) – математическое выражение, для которого требуется найти экстремум.
4. Если условие экономической задачи представлено в виде математической записи, содержащей целевую функцию, систему ограничений в виде равенств и неравенств, условие неотрицательности переменных, причем некоторые переменные – произвольные по знаку, то такая запись называется исходной формой записи задачи линейного программирования.
5. Каноническая форма – характеризуется тем, что содержит целевую функцию, все ограничения равенства и все переменные неотрицательные.
6. Однородная форма записи – содержит целевую функцию, все ограничения имеют тип <= и все переменные неотрицательные.
7. Возможное решение – совокупность значений n-переменных, которые удовлетворяют только системе ограничений.
8. Допустимое решение – совокупность значений n-переменных, которые удовлетворяют системе ограничений, и при этом выполняется условие неотрицательности переменных.
9. Оптимальное решение – такое допустимое решение, при котором целевая функция принимает наибольшее/ наименьшее значение.
10. Базисные переменные – переменные, коэффициенты которой образуют единичный вектор-столбец.
11. Свободные переменные – все переменные, за исключением базисных.
12. Решение называется базисным, если система ограничений приведет к единичному базису, а все свободные переменные = 0.
Число базисных решений не превышает числа сочетаний из С (где n – число переменных, m – число линейно-независимых ограничений).
13. Опорное решение – базисное решение, в котором базисные переменные неотрицательные (допустимое базисное решение). Исходное опорное решение записывается в 1ую симпликсную таблицу.
Любое опорное решение системы условий задачи является вершиной в области допустимых решений, и наоборот.
|
|
|
Число опорных решений не превышает число базисных решений (т.к. частный случай).
14. Вырожденное решение – опорное решение, в котором хотя бы 1 из базисных переменных = 0.
Классификация задач математического программирования.
Математическое программирование – раздел, который занимается изучением методов решения задач управления, планирования на нахождение min/ max значений функции (экстремумов).
По характеру взаимосвязей между переменными и математическим аппаратом, который будет использоваться, задачи подразделяются на:
1. Линейные – все функциональные свойства системы ограничений и целевые функции носят линейный характер.
2. Нелинейные – если имеется нелинейность хотя бы в 1 связи, то это задачи нелинейного программирования.
Задачи линейного программирования:
1. Общая задача линейного программирования, которая решается симпликсным методом.
2. Транспортная задача, которая решается различными методами.
3. Видоизмененные задачи, которые определенным способами сводятся к решению симпликсным методом:
1) Задача параметрического программирования – такая задача, в которой или в целевой функции, или в правой части ограничений, или и там, и там, имеется параметр, который изменяется в определенных переделах.
2. Целочисленное программирование – на переменных накладывается условие целочисленности.
3. Дробно-линейное программирование – целевая функция представлена дробно-линейным выражением.
Задачи нелинейного программировая:
1. Общая задача нелинейного программирования.
2. Задача выпуклого программирования – задачи min-ции выпуклой вниз гладкой функции/ max-ции выпуклой вверх гладкой функции при ограничениях, заданных нелинейными/ линейными неравенствами, определяющими выпуклое множество.
1) Общая задача выпуклого программирования – целевая функция выпуклая и система ограничений также состоит из выпуклой функции.
2) Специальная задача – выпуклая целевая функция и линейная система ограничений.
3) Задача квадратического программирования – квадратическая целевая функция и линейная система ограничений.
3. Динамическое программирование – задачи, у которых целевая функция обладает свойством аддитивности (т.е. когда она представлена в виде суммы слагаемых функции, зависящих от ограниченного числа переменных/ зависящих только от одной переменной).
|
|
|
Z = f1(x1) + f2(x2) + … + fn(xn)
Специальные задачи исследования операций:
1. Теория игр.
2. Методы сетевого планирования и управления.
3. Система массового обслуживания.
4. Методы управления запасами и др.
Переход от исходной задачи линейного программирования к канонической. Экономический смысл дополнительных переменных.
Каноническая форма - характеризуется тем, что содержит целевую функцию, все ограничения равенства и все переменные неотрицательные.
Правила перехода от исходной формы к канонической:
1. Проверить, все ли переменные неотрицательны:
А) Если в исходной форме есть произвольные переменные xj, то их необходимо заменить разностью 2х неотрицательных переменных во всех ограничениях и целевой функции.
Б) Если в исходной форме все переменные неотрицательные, то начать запись канонической формы с п. 2.
2. Ограничение равенства с неотрицательными переменными оставить без изменения.
3.
А) В левую часть каждого ограничения типа <= вводится 1 новая неотрицательная дополнительная переменная с коэффициентом +1.
Б) В ограничение типа >= вводится 1 новая неотрицательная дополнительная переменная с коэффициентом -1.
Ограничение неравенства заменяется на =.
4. В целевую функцию дополнительные переменные вводятся с нулевым коэффициентом.
Экономический смысл:
Дополнительные переменные с коэффициентом +1 – недоиспользованные ресурсы.
Дополнительные переменные с коэффициентом -1 – излишне использованные ресурсы.
|
|
|
