09.06.2020
Задание 1: Задача о назначениях
Задача о назначениях — одна из фундаментальных задач комбинаторной оптимизации в области математической оптимизации или исследовании операций.
В наиболее общей форме задача формулируется следующим образом:
Имеется некоторое число работ и некоторое число исполнителей. Любой исполнитель может быть назначен на выполнение любой (но только одной) работы, но с неодинаковыми затратами. Нужно распределить работы так, чтобы выполнить работы с минимальными затратами.
Если число работ и исполнителей совпадает, то задача называется линейной задачей о назначениях.
Пример: Предположим, что таксомоторная компания имеет три свободные машины (исполнители), и три заказчика (работы), желающих получить такси как можно быстрее. Фирма заботится о времени доставки такси к заказчику, так что для каждой машины стоимость определяется временем, с какой машина доберётся до места ожидания, определённого заказчиком. Решением задачи о назначениях будет распределение машин по заказчикам такое, что суммарная стоимость (суммарное время ожидания) минимальна.
Задачу о назначениях можно сделать более гибкой. В вышеприведенном примере могут оказаться не три, а четыре свободных такси, но заказчика по-прежнему три. Можно назначить четвёртого фиктивного заказчика с нулевой стоимостью, распределение же машины на фиктивного заказчика означает — «ничего не делай».
Аналогичный приём можно использовать в случае, когда число заказов может превышать число доступных машин, и машина может быть назначена на выполнение нескольких работ, а также когда работа может быть назначена нескольким исполнителям (например, если заказчик — группа, не помещающаяся в одно такси). Можно также поставить задачу увеличения дохода, а не минимизацию цены.
Условие задачи 1:
| Исполнители | Стоимость выполнения | |||
| Работы | ||||
Условие задачи 2:
| Исполнители | Стоимость выполнения | |||
| Работы | ||||
Задние 2: Решение системы нелинейных уравнений
Решение нелинейного уравнения в Excel
https://www.matematicus.ru/excel/reshenie-nelinejnogo-uravneniya-v-excel
Разберём решение нелинейного уравнения в Excel вида:
y=4x3+2x–7
Ячейку A4 оставим пустой, а в ячейки B4 запишем формулу вида
=4*СТЕПЕНЬ(A4;3)+2*A4-7
Затем в Excel перейдём на вкладку Данные -> Поиск Решения
Открывается окно Параметры поиска решения. В поле оптимизировать целевую функцию выбираем ячейку B4, ставим Значения 0, ячейку переменной указываем A4, ставим галочку сделать переменные без ограничений неотрицательными, выбираем метод решения — поиск решения нелинейных задач методом ОПГ (обобщенного приведенного градиента) и жмем Найти решение.
Получаем решение искомой задачи
x=1,06744215530327
Решение системы нелинейных уравнений в Excel
Решением системы уравнений являются точки пересечения окружности (с радиусом 2 и центром (1; -1)) и прямой y=0,5-1,25x.
Данную систему заменим равносильным уравнение:
для которого будем искать решения с помощью надстройки Поиск решения. Локализуйте корни системы уравнений на интервале y, y Î[-3; 3] с шагом 0,5.
Этот интервал можно найти, построив исходные графики системы уравнений:
=-1+КОРЕНЬ(4-(A2-1)^2)
=-1-КОРЕНЬ(4-(A2-1)^2)
=(2-5*A2)/4
=((C46:C58-1)^2+(D45:P45+1)^2-4)^2+(5*C46:C58+4*D45:P45-2)^2
=((D61-1)^2+(E61+1)^2-4)^2+(5*D61+4*E61-2)^2
Задание 3: Транспортная задача
https://microexcel.ru/transportnaya-zadacha/
https://exceltable.com/otchety/reshenie-transportnoy-zadachi