Практическая работа № 5

Решение оптимизационных задач АСОИиУ с использованием универсальных математических систем в виде пакетов MATLAB, Maple, Mathematica, Mathcad и других

Цель работы. Получить практические навыки в постановке и решении оптимизационных задач АСОИиУ с помощью универсальных математических систем в виде пакетов MATLAB, Maple, Mathematica, Mathcad и других.

Общие сведения

В настоящее время аналитические методы решения большинства оптимизационных задач, возникающих на производстве (транспортные задачи, задачи распределения оборудования, задачи упорядочения и т.д.) уступают дорогу компьютерному анализу и в будущем они будут все чаще заменяться интерактивными и мощными процедурами машинного решения и анализа с помощью универсальных математических систем в виде пакетов MATLAB, Maple, Mathematica, Mathcad и других.

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

Рассмотрим решение задачи о рациональном использовании ресурсов с применением пакета Mathcad. Рыболовное судно располагает четырьмя видами сырья (рыба, масло, специи, томат) в количестве . Предполагается выпуск консервов трех видов. На производство одной партии каждого - го вида консервов затрачивается сырья вида. Доход от выпуска одной партии консервов каждого вида составляет руб. Одновременно на судне может храниться не более продукции каждого вида. Определить такой план выпуска продукции, чтобы доход от ее реализации был максимальным.

Рассматриваемая задача является оптимизационной, так как результат ее решения должен быть наилучшим среди множества допустимых. Сформулируем математическую модель задачи. Обозначим искомые количества партий продукции каждого вида . Тогда цель решения задачи – получение максимального дохода – может быть записана математически в виде целевой функции:

Где - доход от выпуска всей продукии - го вида.

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

,

Возможность хранения не более продукции каждого вида выражается отношением

,

Подставив в целевую функцию значения и записав ограничения для каждого вида сырья, мы получаем математическую модель решаемой задачи. Для 0 – варианта она представляется так:

Дальнейшие расчеты производим в среде Mathcad.

Вводим исходные данные задачи в матричной форме.

ORIGIN:=1

 

Вводим линейную целевую функцию.

Зададим начальные значения переменным задачи.

Вводим ограничения задачи в матричной форме.

Given

Определяем оптимальное решение задачи с помощью встроенной функции Maximize (в случае поиска максимума функции) или Minimize (в случае поиска минимума функции).

В итоге получаем:

Таким образом, максимальный доход от выпуска продукции в заданных условиях может составить 5664,3 руб. для этого необходимо выпустить 19.3 партии консервов 2-го вида, 98.2 партии консервов 3-го вида. Продукцию 1-го вида выпускать не следует.

Рассмотрим пример решения транспортной задачи в среде MathCad.

На складах A1, A2, A3 хранится a1=100, a2=200, a3=120 единиц одного того же груза соответственно. Требуется доставить его трем потребителям B1, B2, B3, заказы которых составляют b1=200, b2=110, b3=80 единиц груза. Стоимость перевозки Ci,j единицы груза с i – склада j – ому потребителю указаны в транспортной таблице:

	b1=200	b2=110	b3=80
a1=100	4	2	6
a2=200	7	5	3
a3=120	1	7	6

Найти минимальную стоимость перевозок.

Для этого, сверх имеющихся n пунктов назначения b₁, b₂, b₃, введём ещё один, фиктивный, пункт назначения b₄, которому припишем фиктивную заявку, равную избытку запасов над заявками. А стоимость перевозок из всех пунктов отправления в фиктивный пункт назначения b₄ будем считать равным нулю. Введением фиктивного пункта назначения с его заявкой мы сравняли баланс транспортной задачи и теперь его можно решать как обычную транспортную задачу с правильным балансом (количество перевезенного груза обозначим символами x1….xn соответственно)

	b1 = 200	b2 = 110	b3 = 80	b4 = 30
a1 = 100	4 x1	2 x2	6 x3	0 x4
a2 = 200	7 x5	5 x6	3 x7	0 x8
a3 = 120	1 x9	7 x10	6 x11	0 x12

Дальнейшие расчеты производим в среде MathCad.

Задаем начальные значения X.

З адаем общую стоимость перевозок:

З адаем условия:

И спользуя встроенную функцию Mimimize, находим значения x₁…x₁₂ при которых F(x) будет минимальным.

Н аходим минимальную стоимость перевозки:

Р езультаты заносим в транспортную таблицу:

	b1=200	b2=110	b3=80
a1=100	4	2 x2 =100	6
a2=200	7 x5 = 80	5 x6 = 10	3 x7 = 80
a3=120	1 x9 =120	7	6

Минимальная стоимость перевозок: F = 1170.

Варианты заданий

Линейное программирование

Транспортная задача

Вариант 1	b1=300	b2=410	b3=80
a1=100	14	2	6
a2=200	6	8	5
a3=120	9	7	6

Вариант 2	b1=210	b2=180	b3=180
a1=100	9	8	9
a2=200	17	51	3
a3=120	11	8	6

Вариант 3	b1=187	b2=112	B3=100
a1=100	44	9	6
a2=200	71	15	17
a3=120	17	11	13

Вариант 4	b1=214	b2=114	b3=380
a1=100	57	25	65
a2=200	71	11	34
a3=120	19	7	61

Вариант 5	b1=250	b2=110	b3=80
a1=100	14	21	12
a2=200	15	15	9
a3=120	9	7	16

Вариант 6	b1=209	b2=190	b3=120
a1=100	15	2	9
a2=200	19	9	11
a3=120	7	7	6

Вариант 7	b1=210	b2=210	b3=90
a1=100	4	2	7
a2=200	11	9	3
a3=120	1	7	6

Вариант 8	b1=130	b2=140	b3=180
a1=100	19	21	11
a2=200	16	47	31
a3=120	11	71	19

Вариант 9	b1=300	b2=210	b3=80
a1=100	4	21	6
a2=200	48	52	31
a3=120	12	7	6

Вариант 10	b1=230	b2=120	b3=112
a1=100	45	2	7
a2=200	78	12	8
a3=120	9	7	6

Вариант 11	b1=280	b2=150	B3=180
a1=100	21	2	6
a2=200	3	2	14
a3=120	9	7	19

Вариант 12	b1=302	b2=167	B3=140
a1=100	3	2	14
a2=200	9	11	13
a3=120	1	7	6

Вариант 13	b1=190	b2=119	b3=214
a1=100	21	2	8
a2=200	17	19	8
a3=120	11	17	6

Порядок выполнения работы

1. Получить вариант задания у преподавателя.

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

3. Построить математическую модель транспортной задачи.

4. Выполнить необходимые расчеты с использованием любого из пакетов MATLAB, Maple, Mathematica, Mathcad и других.

5. Подготовить отчет по работе.

Содержание отчета

1. Название и цель работы.

2. Номер варианта.

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

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

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

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

7. Протокол машинного решения задачи о рациональном использовании ресурсов.

8. Протокол машинного решения транспортной задачи.

9. Выводы

Контрольные вопросы

1. Что означает сформулировать задачу линейного программирования?

2. Геометрическое представление и решение задачи линейного программирования.

3. Перечислите широко известные оптимизационные задачи, возникающие на производстве.

4. Перечислите известные вам методы решения транспортной задачи.

5. Является ли транспортная задача частным типом задачи линейного программирования, обоснуйте ваш ответ.

6. В чем заключается универсальность пакетов MATLAB, Maple, Mathematica, Mathcad и других?

7. Какие преимущества имеет применение универсальных пакетов MATLAB, Maple, Mathematica, Mathcad и других при решении оптимизационных задач АСОИиУ в отличии от использования аналитических методов?