методы оптимальных решений

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

Введение 3
1. Теоретическое задание 4
1.1. Вопрос 1 4
1.2. Вопрос 2 6
1.3. Вопрос 3 9
2. Практическое задание 12
2.1. Исходная задача 12
2.2. Целочисленное ограничение 17
2.3. Двойственная задача 18
2.4. Устойчивость решения 19
Заключение 21
Литература 22

Цель курсовой работы – закрепить, систематизировать и комплексно обобщить знания по методам решения задач линейного программирования и развить навыки самостоятельной творческой работы; научиться практически применять полученные теоретические знания при решении конкретных задач; научиться пользоваться справочной литературой, стандартами, другими нормативно-техническими документами и средствами вычислительной техники

Заметим, что . Если значение с3  мало по сравнению с с2, то величина   близка к нулю: когда с3 значительно превосходит с2, то  близка к 1. Недопустимость дефицита равносильна предположению, что   или  .Используя основные формулы, выражения можно записать компактнее:Из сравнения формул следует, что оптимальные объемы партий для задач с дефицитом и без дефицита при одинаковых параметрах связаны соотношением,откуда вытекает, что оптимальный объем партии в задаче с дефицитом всегда больше (в раз), чем в задаче без дефицита. 1.3. Вопрос 3Приведите пример задачи, сводящейся к транспортной ОтветВ качестве примера задачи, сводящейся к транспортной, рассмотрим задачу о назначениях.Задача о назначениях.Рассмотрим ситуацию, когда требуется распределить m работ (или исполнителей) по n станкам. Работа i (i=1,...,m), выполняемая на станке j (j=1,...,n), связана с затратами cij. Задача состоит в таком распределении работ по станкам (одна работа выполняется на одном станке), которое соответствует минимизации суммарных затрат. Эту задачу можно рассматривать как частный случай транспортной задачи. Здесь работы представляют «исходные пункты», а станки – «пункты назначения». Предложение в каждом исходном пункте равно 1, т.е. ai = 1 для всех i. Аналогично спрос в каждом пункте назначения равен 1, т.е. bj = 1 для всех j. Стоимость «перевозки» (прикрепления) работы i к станку j равна cij. Если какую-либо работу нельзя выполнять на некотором станке, то соответствующая стоимость берется равной очень большому числу. Матрица стоимостей C определяется следующим образом:Прежде чем решать такую задачу необходимо ликвидировать дисбаланс, добавив фиктивные работы или станки в зависимости от начальных условий. Поэтому без потери общности можно положить m=n. Пусть xij=0, если j-я работа не выполняется на i-м станке, xij=1, если j-я работа выполняется на i-м станке. Таким образом, решение задачи может быть записано в виде двумерного массива X=(xij). Допустимое решение называется назначением. Допустимое решение строится путем выбора ровно одного элемента в каждой строке матрицы X=(xij) и ровно одного элемента в каждом столбце этой матрицы. Для заданного значения n существует n! допустимых решений. Теперь задача будет формулироваться следующим образом:Ограничения первой группы необходимы для того, чтобы каждая работа выполнялась ровно один раз. Ограничения второй группы гарантируют, что каждому станку будет приписана ровно одна работа.Венгерский алгоритм.Шаг 1. (Редукция строк и столбцов). Цель данного шага состоит в получении максимально возможного числа нулевых элементов в матрице стоимостей. Для этого из всех элементов каждой строки вычитают минимальный элемент соответствующей строки, а затем из всех элементов каждого столбца полученной матрицы вычитают минимальный элемент соответствующего столбца. В результате получают редуцированную матрицу стоимостей и переходят к поиску назначений. Шаг 2. (Определение назначений).а) Найти строки, содержащие ровно один невычеркнутый нулевой элемент. В каждой такой строке произвести назначение, соответствующее невычеркнутому нулевому элементу. В каждом столбце, в котором было произведено назначение, вычеркнуть все невычеркнутые ранее нулевые элементы. Строки рассматриваются в порядке возрастания их номеров.б) Найти столбцы, содержащие ровно один невычеркнутый нулевой элемент. В каждом таком столбце произвести назначение, соответствующее невычеркнутому нулевому элементу. В каждой строке, в которой было произведено назначение, вычеркнуть все невычеркнутые ранее нулевые элементы. Столбцы рассматриваются в порядке возрастания их номеров.в) Выполнять пункты а) и б) до тех пор, пока не будет вычеркнуто максимально возможное число нулевых элементов. Если построенное назначение полное, то оно является оптимальным. Если некоторые нули остались невычеркнутыми, то можно попытаться найти полное назначение.Если нельзя найти полного назначения, то необходима дальнейшая модификация матрицы стоимостей, т.е. перейти к шагу 3.Шаг 3. (Модификация редуцированной матрицы).Для редуцированной матрицы стоимостей:а) Вычислить число нулей в каждой невычеркнутой строке и каждом невычеркнутом столбце.б) Вычеркнуть строку или столбец с максимальным числом нулей.в) Выполнять пункты а) и б) до тех пор, пока не будут вычеркнуты все нули. г) Из всех невычеркнутых элементов вычесть минимальный невычеркнутый элемент и прибавить его к каждому элементу, расположенному на пересечении двух линий. Перейти к шагу 2. Замечания. 1) Если число линий, необходимое, для того чтобы вычеркнуть нулевые элементы, равно числу строк (столбцов), то существует полное назначение. 2) Если исходная задача является задачей максимизации, то все элементы матрицы стоимостей следует умножить на (-1) и сложить их с достаточно большим числом так, чтобы матрица не содержала бы отрицательных элементов. Затем задачу следует решать как задачу минимизации.2. Практическое заданиеНа звероферме могут выращиваться лисицы и песцы. Для обеспечения нормальных условий их выращивания используется три вида кормов (I, II и III). Количество корма каждого вида, которое должны ежедневно получать лисицы и песцы, приведено в таблице. В ней же указаны общее количество корма (ОКК) каждого вида, которое может быть использовано зверофермой, и прибыль от реализации одной шкурки лисицы и песца.Таблица 1 – Исходные данныеКормЛисицаПесецОКК (кг)I23183II41240III67450Прибыль на одну шкурку (р.)1612Определить, сколько лисиц и песцов следует выращивать на звероферме, чтобы прибыль от реализации их шкурок была максимальной.Дополнительное ограничение – количество лисиц не менее 62.Интервалы для расчета интервала устойчивости – ограничения изменяются: ОКК корма 2 – 50, корма 3 – 800.Решение2.1. Исходная задачаПусть х1 – количество выращиваемых лисиц, х2 – количество выращиваемых песцов. Целевая функция – это максимум прибыли:Z=16х1+12х2 → max (1)Ограничения на ресурсы: -27368532385002х1+3х2 ≤ 183 4х1+х2 ≤ 240 (2)6х1+7х2 ≤ 450 Ограничения на неотрицательность переменных хi:хi ≥ 0, () (3)Задача (1)–(3) – это математическая модель задачи. Решим задачу в Excel. На рабочем листе создадим схему решения (рис.1).Рис.1 – Лист «Выращивание животных» в ExcelПояснения:в 1-й строке таблицы находится заголовок;во 2-й – наименования продукции;в 3-й строке отведено место для оптимального решения, которое после вычислений появится в ячейках B3:С3 (в жирной рамке);в 4-й строке в ячейках B4:С4 заданы коэффициенты целевой функции, а ячейка D4, в рамке, зарезервирована для вычисления значения целевой функции;строки с 6-й по 8-ю содержат коэффициенты, знаки и правые части ограничений;в столбце Левая часть после вычислений появятся левые части ограничений;в столбце Разница – появится разность правых и левых частей;в ячейку D6 внесем формулу СУММПРОИЗВ(B$3:C$3;B6:C6) и скопируем ее на ячейки D7:D8;в ячейку G6 внесем формулу F6-D6 и скопируем ее на ячейки G7:G8;в целевую ячейку D4 внесем формулу СУММПРОИЗВ(B3:C3;B4:C4).Выполним ПОИСК РЕШЕНИЯ (рис.2).Рис.2 – Диалоговое окно «Поиск решения»Условия поиска:Целевая ячейка: D4Равная: максимумИзменяемые ячейки: B3:C3Ограничения: D6:D8≤F6:F8;B3:C3≥0.Результат поиска представлен на рис.3.Рис.3 – Результат выполнения «Поиск решения»Значение функции цели равно 1090,909; оптимальный план:Х*=(55,91; 16,36).Таким образом, по оптимальному плану звероферма должна выращивать 55,91 лисиц и 16,36 песцов. При этом максимальная прибыль от реализации шкурок будет равна 1090,909 р.В столбце Разница показаны остатки кормов:– значение разницы 22,09 для I корма означает, что остаток корма I вида равен 22,09 кг, т.е. этот корм недефицитен;– значение разницы 0 для II корма означает, что этот корм использован полностью, т.е. он дефицитен;– значение разницы 0 для III корма означает, что этот корм использован полностью, т.е. он дефицитен.Отчет по устойчивости:Рис.4 – Отчет по устойчивостиВ первой из таблиц отчета по устойчивости выводится следующая информация:в первых двух столбцах перечислены ячейки, в которых вычисляются значения переменных, и их имена;в столбце Результ. значение – найденное оптимальное решение (55,91; 16,36);в столбце Нормир. стоимость – двойственные оценки (0; 0). Такая оценка может быть отлична от нуля только для нулевой переменной и показывает, на какую величину в целевой функции следует изменить коэффициент этой переменной, чтобы в оптимальном плане она приняла положительное значение.