Размещено на http://www.Allbest.Ru/

Воронеж, 2023

Министерство образования и науки Российской Федерации

Автономная некоммерческая образовательная организация высшего образования

Воронежский институт высоких технологий

Факультет техносферной безопасности

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

Выполнил: Луковских М.И.

Студент 2 курса группы ТБз-218



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

Отчет по лабораторной работе должен содержать

1. Постановку задачи

2. Математическую оптимизационную модель

3. Краткое описание основных этапов решения в среде Excel

4. Результат решения задачи (итоговую таблицу в Excel)

5. Отчеты по результатам, устойчивости, пределам

6. Построенные диаграммы

7. Результаты параметрического анализа с соответствующими выводами

8. Решение задачи вручную с использованием симплекс-метода и графического метода

Выводы

Для производства двух видов изделий A и B используются три типа технологического оборудования. Для производства одного изделия A оборудование первого типа используется в течение 3 часов, оборудование второго типа - 1 часов, оборудование третьего типа - 1 часов. Для производства одного изделия B оборудование первого типа используется в течение 1 часов, оборудование второго типа - 2 часов, оборудование третьего типа - 1 часов. На изготовление всех изделий предприятие может использовать оборудование первого типа не более чем 46 часов, оборудование второго типа - не более 34 часов, оборудование третьего типа - не более 20 часов. Прибыль от реализации одного готового изделия A составляет 5 денежных единиц, а изделия В - 2 денежных единиц. Составить план производства изделий A и B, обеспечивающий максимальную прибыль от их реализации.



Вариант	a1	a2	a3	b1	b2	b3	t1	t2	t3	a	b
7	3	1	1	1	2	1	46	34	20	5	2

Методические указания для выполнения работы

Решение задач в среде Excel начинается с ввода условий задачи. Ввод условий задачи состоит из следующих основных шагов:

- создание формы для ввода условий задачи;

- ввод исходных данных;

- ввод зависимостей из математической модели;

- назначение целевой функции;

- ввод ограничений и граничных условий.

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

Таблица 1

Ресурсы	Виды продукции	Запасы ресурсов
	А	В
Тип 1	3	1	46
Тип 2	1	2	34
Тип 3	1	1	20
Прибыль	5	2

Математическая модель для решения данной задачи:

Форма для ввода условий данной задачи может иметь следующий вид:

Рис. 1

Весь текст на рис. 1 (и в дальнейшем) является комментарием и на решение задачи не влияет.

Далее необходимо ввести в сформированную форму исходные данные (коэффициенты в целевой функции и ограничениях, а также направление оптимизации целевой функции и знаки ограничений (рис. 2)

Рис. 2

При этом ячейки B2:C2 являются изменяемыми и в них будут заноситься значения переменных.

Ввод функциональных зависимостей для целевой функции и ограничений осуществляется с использованием Мастера функций. Для этого необходимо активизировать требуемую ячейку (F3) и вызвать Мастер функций.

В левой части появившегося диалогового окна нужно выбрать категорию функции Математическая, а в правом окне выделить функцию СУММПРОИЗВ и нажать клавишу ОК. Затем на экране отобразится диалоговое окно второго шага (рис.8), где требуется ввести как первый (B$2:C$2), так и второй массивы (B2:C2). При вводе первого массива используются абсолютные ссылки на ячейки, при вводе второго - относительные, что в дальнейшем будет удобно при копировании формул. Во все окна адреса ячеек удобно вводить не с клавиатуры, а протаскивая мышь по соответствующим ячейкам.

Рис. 3

Зависимости для левых частей ограничений вводятся аналогично.

Окончательная таблица с исходными данными представлена на рис. 4.

Рис. 4

После окончания ввода исходных данных осуществляется вызов программы Поиск решения. Для этого необходимо выбрать в меню пункт Данные, а в нем - Поиск решения, в результате чего на экране появится окно поиска решения (рис. 5).

Рис. 5

Решение задачи производится сразу же после ввода данных, когда на экране находится диалоговое окно Поиск решения. Перед началом решения необходимо установить параметры решения, для чего в окне поиска решения выбрать команду параметры. Диалоговое окно параметров поиска решения представлено на рис. 7.

С помощью команд, находящихся в этом диалоговом окне, можно вводить условия для решения задач оптимизации всех классов. Рассмотрим наиболее важные команды, применяемые при решении конкретных задач.



Рис. 7

Максимальное время

Служит для назначения времени в секундах, выделяемого на поиск решения задачи. В поле можно ввести время, не превышающее 32767 с (более 9 часов!). Значение 100, используемое по умолчанию, подходит для большинства задач.

Предельное число итераций

Служит для назначения числа итераций. Используемое по умолчанию число 100 подходит для решения большинства задач

Относительная погрешность

Используется для задания точности, с которой определяется соответствие ячейки целевому значению или приближение к указанным границам. Поле должно содержать число из интервала от 0 (нуля) до 1. Низкая точность соответствует введенному числу, содержащему меньшее количество десятичных знаков, чем число, используемое по умолчанию ѕ например, 0,0001. Высокая точность увеличит время, которое требуется для того, чтобы сошелся процесс оптимизации.

Допустимое отклонение

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

Сходимость

Когда относительное изменение значения в целевой ячейке за последние пять итераций становится меньше числа, указанного в поле Сходимость, поиск прекращается. Сходимость применяется только к нелинейным задачам, условием служит дробь из интервала от 0 (нуля) до 1. Лучшую сходимость характеризует большее количество десятичных знаков. Лучшая сходимость требует больше времени на поиск оптимального решения.

Линейная модель

Используется для решения линейной задачи оптимизации или линейной аппроксимации нелинейной задачи.

Показывать результаты итераций

Используется для приостановки поиска решения для просмотра результатов отдельных итераций.

Автоматическое масштабирование

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

Значения не отрицательны

Позволяет установить нулевую нижнюю границу для тех влияющих ячеек, для которых она не была указана в поле Ограничение диалогового окна Добавить ограничение.

Остальные команды будут рассмотрены позже при изучении соответствующих классов задач.

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

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

Результирующие значения всех переменных записываются в ячейки B2- C2 исходной задачи. Соответствующее значение целевой функции заносится в ячейку F3, а значения левых частей ограничений - в ячейки D7-D9. Таблица с результатами решения задачи представлена на рис. 8.

Рис. 8

Рис. 8 показывает, что в оптимальном решении

Прод. А = 13; Прод. В = 7

При этом максимальная прибыль будет составлять 79, а количество использованных ресурсов равно:

Тип 1 = D7 = 46, тип 2 = D8 = 27, тип 3 =D9 = 20

Таково оптимальное решение рассматриваемой задачи производственного планирования. Однако решение задачи находится не всегда. Если условия задачи несовместны, на экране появится надпись - Поиск не может найти подходящего решения. Если целевая функция не ограничена, то в окне результатов поиска решения появится сообщение: Значения целевой функции не сходятся.

Кроме этого, из окна Результаты поиска решения возможно создание отчётов трех типов: по результатам, устойчивости и пределам, каждый из которых записывается на отдельном листе. Отчеты используются при анализе полученного оптимального решения.

Рис. 9

Отчет по результатам (рис. 9) состоит из трех таблиц.

В таблице 1 (целевая ячейка) приведены сведения о целевой функции, в столбце "Исходно" - указывается значение целевой функции до вычислений, "Результат" - указывается значение целевой функции после вычислений.

Таблица 2 (изменяемые ячейки) содержит сведения о значениях искомых переменных, до и после решения задачи.

Таблица 3 (ограничения) показывает результаты оптимального решения для ограничений и для граничных условий. Здесь в графе "Формула" приведены зависимости, которые были введены в диалоговом окне "Поиск решения"); в графе "Разница" показано количество неиспользованного ресурса. Если ресурс используется полностью, то в графе "Состояние" указывается связанное; при неполном использовании ресурса в этой графе указывается не связан.

Отчет по устойчивости (рис. 10) состоит из двух таблиц.

В таблице 1 (изменяемые ячейки) приводятся следующие значения для переменных:

- результат решения задачи;

- редуцированная стоимость, т.е. дополнительные двойственные переменные v_j, которые показывают, насколько изменяется целевая функция при принудительном включении единицы этой продукции в оптимальное решение;

- коэффициенты целевой функции;

-предельные значения приращения коэффициентов ?c_j целевой функции при которых сохраняется набор переменных, входящих в оптимальное решение.

В таблице 2 (ограничения) приводятся аналогичные значения для ограничений:

- величины использованных ресурсов;

- теневые цены, т.е. двойственные оценки y_i, которые показывают, как изменится целевая функция при изменении ресурсов на единицу;

- значения приращения ресурсов ?b_i, при которых сохраняется оптимальный набор переменных, входящих в оптимальное решение.

Рис. 10

Отчет по пределам (рис. 11) показывает, в каких пределах может изменяться выпуск продукции, вошедшей в оптимальное решение, при сохранении структуры оптимального решения:

- рассматриваются значения x_j в оптимальном решении;

- рассматриваются нижние пределы изменения значений x_j.

Кроме этого, в отчете указаны значения целевой функции при выпуске данного типа продукции на нижнем пределе. Далее приводятся верхние пределы изменения x_j и значения целевой функции при выпуске продукции, вошедшей в оптимальное решение на верхних пределах.

Рис. 11



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

Рис. 15

Параметрический анализ

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

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

Вариант	1	2	3
Тип 1	46	56	76
Тип 3	20	30	40

производственный транспортный задача еxcel



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

Для представления результатов решения вызывается пункт меню Данные, Анализ “Что-Если” и в появившемся диалоговом окне Диспетчер сценариев (рис. 18) выбирается пункт Отчет.

Посмотрим результаты с изменениями

Симплекс метод

Математическая модель для решения данной задачи:

Каноническая форма

Решение иллюстрируется симплекс-таблицей:

xБ	cБ	B	-5	-2	0	0	0
			x1	x2	x3	x4	x5
x3	0	46	3	1	1	0	0
x4	0	34	1	2	0	1	0
x5	0	20	1	1	0	0	1
0	5	2	0	0	0
x1	-5	46/3	1	1/3	1/3	0	0
x4	0	56/3	0	5/3	-1/3	1	0
x5	0	14/3	0	2/3	-1/3	0	1
-230/3	0	1/3	-5/3	0	0
x1	-5	13	1	0	Ѕ	0	-1/2
x4	0	7	0	0	Ѕ	1	-5/2
x2	-2	7	0	1	-1/2	0	3/2
-79	0	0	-3/2	0	-1/2

Оптимальный план: x₁^* = 13; x₂^* = 7 F^* = 79

Решение геометрически

Запишем уравнения граничных прямых и построим их на плоскости x₁0x₂.



3x₁+x₂=46, (1)

x₁+2x₂=34, (2)

x₁+x₂=20, (3)

x₁ ? 0, (4)

x₂ ? 0, (5)

Выделив область решения каждого неравенства системы ограничений, получим многоугольник допустимых решений ЗЛП.

Построим основную прямую L = 0, то есть F = 5x₁+2x₂ = 0, проходящую через начало координат O(0,0) перпендикулярно вектору c(5;2).

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

Перемещая прямую L = 0 в направлении вектора c(5;2), находим максимальную точку D, в которой пересекаются прямые L1 и L3:

3x₁+x₂=46

x₁+x₂=20

Решив систему уравнений, получим: x₁ = 13, x₂ = 7

Откуда найдем максимальное значение целевой функции:

F(x) = 5*13 + 2*7 = 79

Вывод: таким образом, нужно изготовить изделие А в количестве 13 шт., а изделие В - 7 шт. При этом максимальная прибыль составит 79.



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

Решение транспортных задач средствами Excel

1. Решить транспортную задачу

Пункты отправления	Пункты назначения	Запасы
	B1	B2	B3	B4
А1	9	4	4	3	120
A2	6	2	3	11	250
А3	3	5	8	2	280
Потребности	240	80	150	180

2. Решить задачу при следующих дополнительных условиях: Из пункта А3 в пункт В1 должно быть перевезено не более 20 единиц груза, из пункта А1 в пункт В4 перевозка груза запрещена, а из пункта А2 в пункт В3 необходимо перевезти не менее 45 единиц груза.

3. Решить задачу из п. 1, если запас пункта отправления A2 составит 150 единиц, а потребность пункта назначения B4 200 единиц (открытая модель).

Решение:

120+250+280 = 650

240+80+150+180 = 650

р Модель закрытая

Математическая задача

При ограничениях

Вобьем данные в эксель

Вобьем формулы

С помощью данные, поиск решения



Результат

Таким образом, из А1 надо отправить в В4 120, из А2 в В1 20, в В2 80, в В3 150. Из А3 в В1 220, в В4 60. Минимальные затраты 1870.

Решить задачу при следующих дополнительных условиях: Из пункта А3 в пункт В1 должно быть перевезено не более 20 единиц груза, из пункта А1 в пункт В4 перевозка груза запрещена, а из пункта А2 в пункт В3 необходимо перевезти не менее 45 единиц груза.

Добавим ограничения

Результат

Вывод: затраты увеличились.

Решить задачу из п. 1, если запас пункта отправления A2 составит 150 единиц, а потребность пункта назначения B4 200 единиц (открытая модель).

Математическая задача

При ограничениях

Результат:

Вывод: затраты уменьшились.

Метод потенциалов:

Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.

	B1 v1=9	B2 v2=5	B3 v3=6	B4 v4=8	Запасы
A1 u1=0	9 120-	4	4	3 +	120
A2 u2=-3	6 20	2 80	3 150	11	250
A3 u3=-6	3 100+	5	8	2 180-	280
Потребности	240	80	150	180

Значение целевой функции для этого опорного плана равно:

F(x) = 9*120 + 6*20 + 2*80 + 3*150 + 3*100 + 2*180 = 2470

Улучшение опорного плана.

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0.

u₁ + v₁ = 9; 0 + v₁ = 9; v₁ = 9

u₂ + v₁ = 6; 9 + u₂ = 6; u₂ = -3

u₂ + v₂ = 2; -3 + v₂ = 2; v₂ = 5

u₂ + v₃ = 3; -3 + v₃ = 3; v₃ = 6

u₃ + v₁ = 3; 9 + u₃ = 3; u₃ = -6

u₃ + v₄ = 2; -6 + v₄ = 2; v₄ = 8

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_j > c_ij

(1;2): 0 + 5 > 4; ?₁₂ = 0 + 5 - 4 = 1 > 0

(1;3): 0 + 6 > 4; ?₁₃ = 0 + 6 - 4 = 2 > 0

(1;4): 0 + 8 > 3; ?₁₄ = 0 + 8 - 3 = 5 > 0

Max (1,2,5) = 5

Выбираем максимальную оценку свободной клетки (1;4): 3

Для этого в перспективную клетку (1;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

Цикл приведен в таблице (1,4 > 1,1 > 3,1 > 3,4).

Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 1) = 120. Прибавляем 120 к объемам грузов, стоящих в плюсовых клетках и вычитаем 120 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план.

	B1 v1=4	B2 v2=0	B3 v3=1	B4 v4=3	Запасы
A1 u1=0	9	4	4	3 120	120
A2 u2=2	6 20	2 80	3 150	11	250
A3 u3=-1	3 220	5	8	2 60	280
Потребности	240	80	150	180

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0.

u₁ + v₄ = 3; 0 + v₄ = 3; v₄ = 3

u₃ + v₄ = 2; 3 + u₃ = 2; u₃ = -1

u₃ + v₁ = 3; -1 + v₁ = 3; v₁ = 4

u₂ + v₁ = 6; 4 + u₂ = 6; u₂ = 2

u₂ + v₂ = 2; 2 + v₂ = 2; v₂ = 0

u₂ + v₃ = 3; 2 + v₃ = 3; v₃ = 1

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию u_i + v_j ? c_ij.

Минимальные затраты составят:

F(x) = 3*120 + 6*20 + 2*80 + 3*150 + 3*220 + 2*60 = 1870

Анализ оптимального плана

Из 1-го склада необходимо весь груз направить в 4-й магазин.

Из 2-го склада необходимо груз направить в 1-й магазин (20 ед.), в 2-й магазин (80 ед.), в 3-й магазин (150 ед.)

Из 3-го склада необходимо груз направить в 1-й магазин (220 ед.), в 4-й магазин (60 ед.)

Размещено на allbest.ru