Лабораторная работа по теории управления (Вариант 2)

ЛАБОРАТОРНАЯ РАБОТА №1 РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОЙ ОПТИМИЗАЦИИ СРЕДСТВАМИ EXCEL Лабораторные задания. 1. Выбрать задачу в соответствии с вариантом, составить ее математическую модель и решить с использованием средств EXCEL. Сформировать отчеты по устойчивости, результатам и пределам. Для визуализации результатов решения построить диаграммы. Проанализировать полученные результаты. 2. Провести параметрический анализ решая задачу при пяти различных значениях ресурса оборудования третьего типа. Значение ресурса необходимо менять как в большую, так и в меньшую сторону. 3. Решить задачу вручную с использованием симплекс-метода и графического метода. 4. Сравнить результаты, полученные при выполнении заданий 1 и 2. Отчет по лабораторной работе должен содержать : 1. Постановка задачи. Для производства двух видов изделий A и B используются три типа технологического оборудования. Для производства одного изделия A оборудование первого типа используется в течение a1=1 часов, оборудование второго типа – a2=3 часов, оборудование третьего типа – a3=3 часов. Для производства одного изделия B оборудование первого типа используется в течение b1=2 часов, оборудование второго типа – b2=3 часов, оборудование третьего типа – b3=1 часов. На изготовление всех изделий предприятие может использовать оборудование первого типа не более чем t1=32 часов, оборудование второго типа – не более t2=60 часов, оборудование третьего типа – не более t3=50 часов. Прибыль от реализации одного готового изделия A составляет =4 денежных единиц, а изделия В — =2 денежных единиц. Составить план производства изделий A и B, обеспечивающий максимальную прибыль от их реализации 2. Математическая оптимизационная модель: х1 – количество продукции А, х2 – количество продукции В F=4×1+2×2max x1+2×232 3×1+3×260 3×1+x250 x1≥0, x2≥0 3. Краткое описание основных этапов решения в среде EXCEL. Форма для ввода условий данной задачи может иметь следующий вид: Далее необходимо ввести в сформированную форму исходные данные (коэффициенты в целевой функции и ограничениях, а также направление оптимизации целевой функции и знаки ограничений. При этом ячейки B3:С3 являются изменяемыми и в них будут заноситься значения переменных. Ввод функциональных зависимостей для целевой функции и ограничений: Рис. 2 После окончания ввода исходных данных осуществляется вызов программы Поиск решения. Для этого необходимо выбрать в меню пункт Данные, а в нем – Поиск решения, в результате чего на экране появится окно поиска решения (рис.3). Рис.3 В окне Оптимизировать целевую функцию требуется ввести имя ячейки, в которую введена зависимость для целевой функции (в данном случае Е6). В качестве направления оптимизации выбирается максимизация. В окне Изменяя ячейки вводятся адреса ячеек, соответствующих варьируемым переменным задачи ($B3:$С3). Далее необходимо ввести ограничения. Для добавления ограничений выбирается пункт Добавить, после чего появляется окно добавления ограничений Вводятся граничные условия для переменных $D$9:$D$11 $F$9:$F$11 Решение задачи производится сразу же после ввода данных, когда на экране находится диалоговое окно Поиск решения. Перед началом решения необходимо установить параметры решения, для чего в окне поиска решения выбрать команду параметры. 4. Результат решения задачи представлен на рис. 4. Рис. 4 Следует производить 15 ед продукции А и 5 ед продукции В. Полностью израсходован ресурс оборудования 2го и 3го типа 5. Отчеты по результатам, устойчивости, пределам. Рис 5 Отчет о результатах показывает, что производится 15 ед продукции А и 5 ед продукции В, целевая функция (прибыль) — 70 д.ед., остаток времени работы оборудования первого типа – 7 часов. Рис. 6 Отчет об устойчивости показывает пределы изменения запасов времени оборудования и цены продукции, при которых сохранится структура оптимального плана. Так, в план производства будет входить только продукция А и В, если ее цена продукции будет выше 2 д.ед., запас первого типа оборудования можно уменьшить на 7 час. Рис. 7 Отчет по пределам (рис.7) показывает, в каких пределах может изменяться выпуск продукции, вошедшей в оптимальное решение, при сохранении структуры оптимального решения 6. Построенные диаграммы. Рис. 8 7. Параметрический анализ. Параметрический анализ будем выполнять для рассматриваемой задачи производственного планирования, решая её при различных значениях имеющегося ресурса оборудования 3го типа. Составим таблицу вариантов: Для выполнения параметрических расчетов в таблице с результатами решения задачи (рис.4) необходимо удалить результат решения, находящийся в ячейках B3:С3. Далее решить задачу для первого варианта по описанной выше схеме, предварительно введя в ячейку F11 значение 60. После решения задачи в диалоговом окне Результаты поиска решения выбирается команда Сохранить сценарий. При этом на экране появится диалоговое окно Сохранение сценария (рис. 9). В появившемся диалоговом окне необходимо ввести имя сценария “Ресурс=60” и подтвердить ввод выбором кнопки OK. Рис. 9 Результат решения задачи для данного варианта представлен на рис. 10 Рис. 10 Далее необходимо аналогично решить задачу для всех оставшихся вариантов, последовательно вводя в ячейку F11 значения 55, 45, 40, 35. При этом нужно сохранять каждый сценарий и вводить его имя, соответствующее текущему значению сырья. Для представления результатов решения вызывается пункт меню Данные, Анализ “Что-Если” и в появившемся диалоговом окне Диспетчер сценариев (рис. 11) выбирается пункт Отчет. Рис. 11 При выборе в диалоговом окне Отчет по сценарию типа отчета Структура создается итоговый сценарий, который размещается на отдельном листе с названием “Структура сценария”. Для удобства дальнейшей работы полученный сценарий можно отредактировать и представить следующем виде: Рис. 12 Для наглядного представления результатов построим гистограммы: Рис. 13 8. Решим задачу графическим методом. Строим прямые: x1+2×2=32 (1) 3×1+3×2=60 (2) 3×1+x2=50 (3) Рис. 14 Строим вектор целевой функции (4;2). Строим линию уровня, перпендикулярно целевой функции и сдвигаем эту линию до последней точки пересечения с областью допустимых решений – это точка А. Найдем координаты точки А: 3×1+3×2=60 3×1+x2=50 х2=5 х1=15 F=415+25=70 д.ед. Решение задачи с использованием симплекс-метода. Введем дополнительные переменные, заменив неравенства равенствами. Канонический вид задачи: F=4×1+2×2max x1+2×2+х3= 32 3×1+3×2+х4= 60 3×1+x2+х5= 50 xi≥0, i=1..5 Составим симплексную таблицу Исходное опорное решение: X1 = (0,0,0, 32; 60;50), F1 = 0 В оценочной строке 2 отрицательные оценки: –4, –2. Выбираем в качестве разрешающего столбец, соответствующий x1, т.к. оценка этого столбца (–4) наименьшая отрицательная оценка. Разрешающая строка выбирается по этот минимум достигается для 1-й строки. Итак, в базис вводим x1, выводим из базиса x5. В результате первого шага получаем второе опорное решение Х2 =(50/3;0; 46/3;10$0) F2 =19. В оценочной строке одна отрицательная оценка: 2/3. Выбираем в качестве разрешающего столбец, соответствующий x2, Разрешающая строка выбирается по этот минимум достигается для 2-й строки. Итак, в базис вводим x2, выводим из базиса x4. В результате первого шага получаем второе опорное решение Х3 =(15;5; 7; 0;0) F3 =70 Дальнейшее увеличение F невозможно, т.к. все оценки стали неотрицательными. 9. Выводы. Решение задачи показало, что следует производить 15 единиц продукции А и 5 единиц продукции В, тога прибыль составит 70 единиц. Решение всеми способами совпадает, что говорит о правильности вычислений.

ЛАБОРАТОРНАЯ РАБОТА №2 РЕШЕНИЕ ТРАНСПОРТНЫХ ЗАДАЧ СРЕДСТВАМИ EXCEL

Лабораторное задание. 1. В соответствии с вариантом решить с использованием средств EXCEL все предлагаемые задачи (пункты 1,2,3). Сформировать отчеты, построить диаграммы. Проанализировать полученные результаты. При решении задачи из пункта 3 открытую модель необходимо предварительно преобразовать к закрытому виду. 2. Решить транспортную задачу из пункта 1 вручную с использованием метода потенциалов. 3. Сравнить результаты, полученные при выполнении лабораторных заданий 1 и 2, сделать выводы. Задачи: 1. Решить транспортную задачу 2. Решить задачу при следующих дополнительных условиях: Из пункта А2 в пункт В3 должно быть перевезено не более 50 единиц груза, из пункта А1 в пункт В4 перевозка груза запрещена, а из пункта А3 в пункт В3 необходимо перевезти не менее 30 единиц груза. 3. Решить задачу из п. 1, если запас пункта отправления A3 составит 150 единиц, а потребность пункта назначения B1 200 единиц (открытая модель). Решение Задача 1 Математическая модель: xij≥0, i=1..3, j=1…4 Таблица EXCEL с введенными условиями данной задачи представлена на рис. 15 Рис. 15 В ячейки G3-G5 занесены запасы всех пунктов отправления, в ячейки B6-E6 — потребности пунктов назначения. Значения тарифов на перевозку записаны в ячейках B10-E12. Ячейки B3-E5 соответствуют переменным задачи и в них после решения будут занесены значения перевозимых грузов. Ячейки F3-F5, B7-E7 соответствуют левым частям ограничений. Зависимость для целевой функции заносится в ячейку G6. Рис. 16 Для решения задачи вызывается программа Поиск решения. В появившемся диалоговом окне назначается целевая функция (ячейка G6), определяется направление поиска (минимизация), вводятся адреса искомых переменных (ячейки B3-E5). Результаты решения задачи представлены на рис. 17. Рис. 17 Стоимость перевозки 2550, от первого поставщика груз вывозится в размере 10 ед третьему потребителю и 100 ед 4му потребителю. От второго поставщика груз вывозится в размере 200 ед второму потребителю и 80 ед третьему. От третьего поставщика груз вывозится в размере 120 ед первому потребителю и 140 ед третьему Задача 2. Математическая модель такая же, как в задаче 1, но добавляются условия: х2350, х14=0, х33≥30 Изменения ограничений в Поиске решения представлено на рис. 18. На самом листе изменения не вносятся. Рис. 18 Выполняем Поиск решения: Рис. 19 Как видно, произошло перераспределение груза, из-за дополнительных ограничений стоимость перевозок выросла до 2780 д.ед. Задача 3. Решим задачу из п. 1, если запас пункта отправления A3 составит 150 единиц, а потребность пункта назначения B1 200 единиц (открытая модель). В этом случае запасы: 110+280+150=540 Потребности: 200+200+230+100=730 Разность 730-540=190 Вводим дополнительного поставщика с запасами 190 и нулевыми тарифами Рис. 20 Решаем задачу: Рис. 21 Как видно, стоимость перевозок значительно сократилась, при этом третий покупатель не получит часть груза – из 230 единиц ему будет доставлено только 40.

2. Решим транспортную задачу из пункта 1 вручную с использованием метода потенциалов.

Найдем первый план методом минимального элемента. Заполнение начинаем с клетки х22, так как ей соответствует минимальный тариф с14=2. Для данной клетки запасы равны А1=110, потребности В4=100, x14= min(110,00)=100. Потребности 4го потребителя удовлетворены, исключаем 4-й столбец из рассмотрения. Следующий минимальный тариф с22=2: х22= min(А2,В2)=(280,200)=200. Потребности 2-го потребителя удовлетворены, исключаем 2-й столбец из рассмотрения Следующий минимальный тариф с13=3: х13= min(А1-100,В3)=(10,230)=10. И т.д. Получаем план: Вычислим значение целевой функции на этом опорном решении F(X1) = 310 +2100+2200 + 980+3120+6140= 2550. Решим транспортную задачу методом потенциалов. Для проверки оптимальности опорного решения необходимо найти потенциалы занятых клеток по формуле vi+uj=cij. Записываем систему уравнений для нахождения потенциалов: u1 +v3 =3 u1 +v4 =2 u2 +v2 =2 u2 +v3 =9 u3 +v1 =3 u3 +v3 =6 Система состоит из 6 уравнений и имеет 7 переменных. Система неопределенная. Одному из потенциалов задаем значение про¬извольно: пусть u1=0. Остальные потенциалы находятся однозначно: v3=3-u1=3 v4=2-u1=2 u2=9-v3=9-3=6 v2=2-u2=2-6=-4 u3=6-v3=6-3=3 v1=3-u3=3-3=0 Проверяем опорное решение X1 на оптимальность. С этой целью вычисляем оценки ij для всех незаполненных клеток таблицы: 11=u1+v1 -c11=0+0-12=-12 12=u1+v2 –c12=0-4-9=-9 21= u2+v1 –c21=6+0-7=-1 24= u2+v4 –c24=6+2-11=-3 32= u3 +v2 -c32=3-4-5=-6 34= u3 +v4 -c34=3+2-7=-2 Среди оценок нет положительных, план оптимальный 3. Таким образом, решение ручным способом и с помощью MS Excel совпадают: , стоимость перевозок 2550 д. ед.

ЛАБОРАТОРНАЯ РАБОТА №3 РЕШЕНИЕ ЗАДАЧ ДИСКРЕТНОЙ ОПТИМИЗАЦИИ СРЕДСТВАМИ EXCEL

Цель работы: Получение практических навыков формирования математических моделей прикладных задач дискретной оптимизации и их решения средствами EXCEL. Лабораторные задания. 1. Выбрать задачу в соответствии с вариантом, составить ее математическую модель и решить с использованием средств EXCEL. Сформировать отчеты по результатам, построить диаграммы. 2. В соответствии с заданием провести параметрический анализ и определить, как влияет на результаты изменение условий задачи. Задача Решение 1. Постановка задачи . Для организации вычислительной лаборатории могут быть использованы четыре типа ЭВМ. Объем оперативной памяти первой ЭВМ 64, второй — 128, третьей – 256, четвертой — 128. Стоимость первой ЭВМ 12 тыс.руб, второй — 15 тыс. руб, третьей — 18 тыс. руб, четвертой — 16 тыс. руб. Потребляемая мощность первой ЭВМ 230 Вт, второй — 230 Вт, третьей — 300 Вт, четвертой — 360 Вт. Первая ЭВМ занимает площадь 1,5 кв.м., вторая 2 кв.м., третья 2 кв.м., четвертая 2,5 кв.м. Необходимо определить, сколько ЭВМ и какого типа надо выбрать, чтобы обеспечить максимальный объем оперативной памяти при ограниченных стоимостных ресурсах 110 тыс. руб, энергетических ресурсах 2000 Вт и ограниченной площади 23 кв.м. 2. Математическая оптимизационная модель. Пусть ЭВМ первого типа используется х1 шт., второго типа х2 шт, третьего типа х3 шт., 4го типа х4 шт. Задача имеет вид: F=64×1+128×2+256×3+128×4max 12×1+15×2+18×3+16×4110 230×1+230×2+300×3+360×42000 1.5×1+2×2+2×3+2.5×423 xi≥0, xi — целые 3. Описание основных этапов решения в среде EXCEL. Вводим данные на лист: Рис. 22 Вводим данные в Поиск решения: Рис. 23 4. Результат решения задачи. Рис. 23 Как видно, при заданных условиях выгодно использовать только ЭВМ 3 в количестве 6 шт. 5. Отчет по результатам. Рис. 24 При закупке ЭВМ осталось неизрасходованными 2 тыс. руб., 200 кВт мощности и 11 м2 площади 6. Построенные диаграммы. Рис. 25 7. Результаты параметрического анализа. Пусть стоимостные ресурсы уменьшатся до 70 тыс. руб. Новое решение примет вид: Рис. 25 Количество ЭВМ3 сократилось до 3 шт, будет приобретена одна ЭВМ4, объем суммарной памяти уменьшился с 1536 до 896 Пусть площадь лаборатории увеличится до 30 кв.м. Решение при этом не изменится, так как в оптимальном решении было задействовано только 12 м2 площади Пусть энергетические ресурсы уменьшатся до 1500 Вт. Новое решение примет вид: Рис. 26 Количество ЭВМ3 сократилось до 5 шт, объем суммарной памяти уменьшился с 1536 до 1280 9. Выводы. В данном случае используется только один тип ЭВМ с максимальной оперативной памятью – ЭВМ №3. При заданных условиях ее необходимо закупить в размере 6 ед. Если энергетические ресурсы сократятся до 1500, то ЭВМ №3 будет закупаться в размере 5 шт. Если финансовые ресурсы сократятся до 70 тыс. шт., то количество ЭВМ3 сократилось до 3 шт, будет приобретена одна ЭВМ4, объем суммарной памяти уменьшился с 1536 до 896