Материал: YasinskyyI.S.AVT-172.Variant8

Лабораторная работа №5

Решение задач линейного программирования «Задача о назначениях»

Цель работы: Получить навыки в решении задач линейного программирования «Задачи о назначениях»

Задание для лабораторной работы

Вариант 1

Необходимо составить план выполнения работ так, чтобы все работы были выполнены, каждый рабочий был загружен только на одной работе, а суммарная стоимость выполнения всех работ была минимальной

Четверо рабочих могут выполнить пять видов работ. Стоимость c_ij выполнения i-м рабочим j-ой работы приведена в таблице.

Таблица 5.1 – Исходные данные

Выполнение

Составляем математическую модель задачи.

Предположим, что имеется n различных работ, каждую которых может выполнить любой из m привлеченных исполнителей. Стоимость (либо эффективность) выполнения i-й работы j-м исполнителем известна и равна cij. Необходимо распределить исполнителей по работам (назначить одного исполнителя на каждую работу) так, чтобы минимизировать суммарные затраты, связанные с выполнением (либо достичь максимальной эффективности) всего комплекса работ.

Введем переменные xij, принимающие значение 1 в случае, когда i-ю ра- боту выполняет j-й исполнитель и значение 0 во всех остальных случаях, i,j = 1, n.

Целевая функция

Ограничения имеют вид

а) что каждый работник назначается только на одну работу

б) один работник выполняет только одну работу

Заполняем таблицу Excel исходными данными (рисунок 5.1).

Блок ячеек G20:K24 содержит оптимальное решение, значение этих ячеек будет получено в результате решения задачи.

Блок ячеек G26:K26 содержит значения затрат времени на выполнение операций каждого рабочего для каждой операции.

Рисунок 5.1 – Внесение исходных данных

Для вычисления целевой функции в ячейке G28 используем функцию =СУММПРОИЗВ(G20:K24; G9:K13) (рисунок 5.2).

Рисунок 5.2 – Ввод целевой функции

Вводим ограничения (рисунок 5.3): по виду работ (каждый работник назначается только на одну работу) в ячейки G26 (=СУММ(G20:G24)) и растягиваем до ячейки K26 и по выполнению (один работник выполняет только одну работу) в ячейки M20 (=СУММ(G20:K20)) и растягиваем до ячейки M24.

Рисунок 5.3 – Ввод ограничений

На вкладке Данные в группе Анализ выберем команду Поиск решения. На экране отобразится ДО Параметры поиска решения, в котором установим следующие параметры (рисунок 5.4):

 в поле Оптимизировать целевую функцию указываем адрес ячейки со значением целевой функции – G28;

 переключатель До устанавливаем на минимум целевой функции;

 в поле Изменяя ячейки переменных указываем адреса ячеек со значениями искомых переменных G20:K24;

 в области В соответствии с ограничениями с помощью кнопки Добавить размещаем все ограничения задачи;

 нажимаем кнопку Найти решение.

Рисунок 5.4 – Заполнение ДО Поиск решения

Результат выполнения Поиска решений представлен на рисунке 5.5.

Рисунок 5.5 – Результаты расчета

Вывод

Таким образом, чтобы суммарные затраты на выполнение операций были наименьшими, следует назначить:

 рабочего 1 на выполнение операции 3;

 рабочего 2 на выполнение операции 2;

 рабочего 3 на выполнение операции 5;

 рабочего 4 на выполнение операции 1;

 рабочего 5 на выполнение фиктивной операции 4;

Рабочий 5, назначен на выполнение фиктивной операций, фактически не работает. Суммарное стоимость за выполнение всех операций составит 7 ден. ед.

Лабораторная работа №6

Линейная оптимизация с помощью EXCEL. Закрытая модель транспортной задачи.

Цель работы: Получить навыки в решении задач линейной оптимизации с помощью EXCEL закрытых моделей транспортных задач.

Задание для лабораторной работы

Вариант 8

Таблица 6.1 – Исходные данные

Выполнение

Составляем математическую модель задачи.

Целевая функция

Систему ограничений получаем из следующих условий задачи:

а) все грузы должны быть перевезены, т.е.

б) все потребности должны быть удовлетворены, т.е.

в) условие не отрицательности

Оптимальным решением задачи является матрица размерностью 4 × 4 удовлетворяющая системе ограничений и доставляющая минимум целевой функции.

Заполняем таблицу Excel исходными данными (рисунок 6.1).

Блок ячеек E18:H22 содержит оптимальное решение, значение этих ячеек будет получено в результате решения задачи.

Блок ячеек E6:H10 содержит значения по издержкам перевозок из одного пункта в другой.

Блок ячеек I6:I10 содержит значения по имеющимся предложениям (объемам производства)

Блок ячеек E11:H11 содержит значения по спросу (объемам поставок).

Рисунок 6.1 – Подготовка таблицы

Для вычисления целевой функции в ячейке E27 используем функцию = СУММПРОИЗВ(E6:H10;E18:H22) (рисунок 6.2).

Рисунок 6.2 – Ввод целевой функции

Вводим ограничения (рисунок 6.3):

по продавцам (все грузы должны быть перевезены) в ячейку I18 =(СУММ(E18:H18)) и растягиваем формулу до ячейки I22.

по покупателям (все потребности должны быть удовлетворены) в ячейку E23 (==СУММ(E18:E22)) и растягиваем формулу до ячейки H23.

Рисунок 6.3 – Ввод ограничений

На вкладке Данные в группе Анализ выберем команду Поиск решения. На экране отобразится ДО Параметры поиска решения, в котором установим следующие параметры (рисунок 6.4):

 в поле Оптимизировать целевую функцию указываем адрес ячейки со значением целевой функции – E27;

 переключатель До устанавливаем на минимум целевой функции;

 в поле Изменяя ячейки переменных указываем адреса ячеек со значениями искомых переменных E18:H229;

 в области В соответствии с ограничениями с помощью кнопки Добавить размещаем ссылки на все ограничения задачи;

• проверяем, чтобы обязательно была поставлена галочка напротив опции “Сделать переменные без ограничений неотрицательными”, а также, чтобы в качестве метода решения стояло значение “Поиск решения симплекс методом”. 

 нажимаем кнопку Найти решение.

Рисунок 6.4 – Заполнение ДО Поиск решения

Результат выполнения Поиска решений представлен на рисунке 6.5.

Рисунок 6.5 – Результаты расчета

Вывод

Таким образом, для получения минимальных издержек по доставке грузов получен план доставок 5 наименований товаров по 4 покупателям.