Материал: 4 Бизнес-процесс в маткад

Омский государственный технический университет

Кафедра ИВТ

Дисциплина

«Вычислительные системы и сети»

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

Моделирование производственных процессов симплекс-методом

Омск, 2019

Введение

Система — это совокупность объектов, например людей или механизмов, функционирующих и взаимодействующих друг с другом для достижения определенной цели. Данное определение предложено Шмидтом и Тейлором [Schmidt and Taylor, 1970]. На практике понятие системы зависит от задач конкретного исследования. Так, совокупность предметов, которые составляют систему в одном исследовании, может являться лишь подмножеством в иной системе, при проведении другого исследования.

1. Составление математической модели бизнес-процесса

Рассмотрим следующую задачу.

Цех может производить в день до 50 изделий А и до 20 изделий Б. Суточный ресурс металла в цехе составляет 60 кг, при этом на изделие А расходуется 1 кг металла, а на изделие Б -2 кг. Составить план выпуска изделий, обеспечивающий цеху максимальную прибыль. Известно, что изделие А приносит в два раза больше прибыли, чем изделие Б.

Переведем условия задачи в математическую форму:

Также, исходя из физического смысла задачи:

Требуется найти максимум функции прибыли:

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

2. Решение задач симплекс-методом в системе Mathcad

   0. Для примера в приложении 2 приведена последовательность аналитического решения задачи минимизации.

   1. Mathcad – «система компьютерной алгебры». Программная среда для автоматизации математических вычислений. Выражения и переменные задаются в наглядной форме подобно текстовому редактору, могут быть легко перемещены и скомпонованы в пределах рабочего поля, при этом встроенный «решатель» позволяет проводить автоматическое решение широкого класса задач, как в символьном, так и в числовом виде: нахождение интегралов и производных, преобразования Фурье, решение систем уравнений и т.д. Ввод осуществляется в месте расположения курсора, курсор может перемещаться мышью или клавиатурой, к примеру, при редактировании выражений.

   0. Для решения задачи минимизации в системе Mathcad нужно лишь воспользоваться стандартной функцией Maximize/Minimize. Вначале рассмотрим более простую стандартную функцию Find для решения обычного уравнения.

   1. Для ввода данных необходимо пользоваться панелями инструментов программы (возведение в степень, вызов вычисления «:=» и др), функции вроде Given и Find печатаются с клавиатуры с соблюдением регистра. Наберем в новом документе Mathcad следующие выражения:

   2. 

   3. 

   4. 

   5. Последние две строки являются проверкой полученного решения.

   6. Решим систему уравнений с двумя неизвестными:

   7. 

   9. 

   10. 

   11. 

   12. Проверка найденного решения:

   13. 

       0. Решение ещё одной системы:

       1. 

       2. 

       4. 

       5. 

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

3. Задания к лабораторной работе

3.1 Ознакомьтесь с методами составления рассматриваемых математических моделей.

3.2 Проанализируйте решение задачи оптимизации симплекс-методом, изложенные в приложении, а также методы решения задач в Mathcad.

3.3 Выполните в программе Mathcad оптимизацию задачи из пункта 2. Сравните результаты.

3.4 Оформите отчёт по ЛР (п. 4).

4. Содержание отчёта по лабораторной работе

- титульный лист (см. приложение на последнем листе);

- описание решенных задач;

- скриншоты программ и результатов их выполнения;

- выводы.

Приложение 1. Титульный лист отчета по лабораторной работе

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

Федеральное государственное бюджетное образовательное учреждение высшего образования

«Омский государственный технический университет»

Кафедра «Информатика и вычислительная техника»

Отчёт по лабораторной работе № ____

по дисциплине

«____»

Омск, 201_

Приложение 2. Аналитическое решение задачи

Рассмотрим определение минимального значения целевой функции

F(X) =  - x₁ - 2x₂ + x₃

при следующих условиях.  -x₁ + 4x₂ - 2x₃≤6  x₁ + x₂ + 2x₃≥6  2x₁ - x₂ + 2x₃=4

Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).  -1x₁ + 4x₂-2x₃ + 1x₄ + 0x₅ = 6  1x₁ + 1x₂ + 2x₃ + 0x₄-1x₅ = 6  2x₁-1x₂ + 2x₃ + 0x₄ + 0x₅ = 4

Введем искусственные переменные x.  -1x₁ + 4x₂-2x₃ + 1x₄ + 0x₅ + 0x₆+ 0x₇ = 6  1x₁ + 1x₂ + 2x₃ + 0x₄-1x₅ + 1x₆+ 0x₇ = 6  (1) 2x₁-1x₂ + 2x₃ + 0x₄ + 0x₅ + 0x₆ + 1x₇= 4

Для постановки задачи на минимум целевую функцию запишем так:  F(X) = -1x₁-2x₂+x₃+Mx₆+Mx₇ => min  За использование искусственных переменных, вводимых в целевую функцию, накладывается так называемый штраф величиной М, очень большое положительное число, которое обычно не задается.  Полученный базис называется искусственным, а метод решения называется методом искусственного базиса.  Причем искусственные переменные не имеют отношения к содержанию поставленной задачи, однако они позволяют построить стартовую точку, а процесс оптимизации вынуждает эти переменные принимать нулевые значения и обеспечить допустимость оптимального решения.

Из уравнений (1) выражаем искусственные переменные:  x₆ = 6-x₁-x₂-2x₃+x₅  x₇ = 4-2x₁+x₂-2x₃  которые подставим в целевую функцию:  F(X) = -x₁-2x₂ + x₃ + M(6-x₁-x₂-2x₃+x₅) + M(4-2x₁+x₂-2x₃) => min  или  F(X) = (-1-3M)x₁+(-2)x₂+(1-4M)x₃+(1M)x₅+(10M) => min

Матрица коэффициентов A = a(ij) системы уравнений (1) имеет вид:

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

Решим систему уравнений относительно базисных переменных:

x₄, x₆, x₇

Полагая, что свободные переменные равны 0, получим первый опорный план:  X1 = (0,0,0,6,0,6,4)

Переходим к основному алгоритму симплекс-метода.

Дополним таблицу столбцом минимумов.