22

РГУТИС Кафедра ИС Салугин А.Н. МУ к контрольной работе по МПС стр. из 22

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

Федеральное агентство по образованию

ГОУ ВПО Российский государственный университет туризма и сервиса

Волгоградский филиал

Кафедра «Информационные системы» методические указания к контрольной работе

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

«Технологические процессы в сервисе»

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

по полной и сокращенной программе

Волгоград-2011

УДК 681.3

МОДЕЛИРОВАНИЕ в сфере услуг: Методические указания к контрольной работе по курсу «Технологические процессы »/ Сост. А.Н. Салугин. - Волгоград: ГОУ ВПО РГУТИС ВФ, 2011 - 20с.

Утверждены и рекомендованы к печати на заседании кафедры ИС

Протокол №_1____ от “_28___”_августа___2011г

Зав. кафедрой А.А. Семиков

Цель работы: получение практических навыков использования линейного программирования (ЛП) для решения задач проектирования процессов оказания услуг. Формализация проблемы. Освоение программы ПОИСК РЕШЕНИЯ для реализации задачи ЛП по подбору кадров, расписанию и распределению ресурсов.

Методы линейного программирования. Поиск решения

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

Задачи оптимального планирования связанные с отысканием оптимума заданной целевой функции ( линейной формы ) при наличии ограничений в виде линейных уравнений или линейных неравенств относятся к задачам линейного программирования. Линейное программирование - наиболее разработанный и широко применяемый раздел математического программирования. Это объясняется следующим:

- математические модели очень большого числа задач автосервиса в линейны относительно искомых переменных;

- такие задачи наиболее изучены, для них разработаны специальные методы и соответствующие программы для их решения на ЭВМ;

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

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

Фирма производит две модели А и В изделий. При этом их производство ограничено наличием деталей и временем монтажа. Каждому изделию модели А требуется 3 детали, а для изделия В - 4 детали. Фирма может получить от своих поставщиков до 1700 деталей в неделю. Для изготовления изделия модели А требуется 12 минут рабочего времени, а для изделия В - 30 мин. В неделю можно использовать не более 160 часов рабочего времени оборудования, занятого в производстве. Задача фирмы состоит в том, чтобы определить в каком количестве следует изготовить А и В - изделия, если каждое изделие модели А приносит 20 тыс. рублей прибыли, а каждое изделие модели В - 40 тыс. Прибыль при этом должна быть максимальной.

Мы привели общую формулировку проблемы для фирмы. Но чтобы решить эту задачу математически, надо уметь переводить ее на язык линейного программирования.  Обозначим через x₁ и x₂ количество изделий типа А и В, соответственно, производимых в неделю.

Еженедельная прибыль будет:

(1)

Нам надо найти те значения x₁ и x₂, когда P-> max. Поскольку x₁ и x₂ выражают еженедельный объем выпускаемых изделий, то они не могут быть отрицательны, т.е.

(2)

Но существуют ограничения на количество получаемых деталей (поставщик не дает больше 1700 в неделю ), а также на время ( не более 1600 часов ). Эти ограничения запишутся в виде:

(3)

Следовательно, задача состоит в том, чтобы найти значения x1 и x2, удовлетворяющие условиям (2,3) максимизирующие функцию  (1). Эту задачу можно решить графически. Рисунок дает наглядное представление об области решений системы ограничений. Это будет ограниченная многогранником область с тремя угловыми точками А, В, С.

Исходную линию уровня целевой функции 2х₁+3х₂=0 будем передвигать в сторону, указанную стрелкой, приближаясь к области допустимых решений. Так как по условию ищется минимум функции P, ясно, что он будет достигнут, как только линия уровня коснется первой же точки построенной области. Такой точкой является точка В(2;2). Отсюда искомый минимум функции P=2х₁+3х₂ при тех же ограничениях (см. рис.1).

Г еометрические построения ограничений 2x₁+5x₂<=1600 и 3x₁+4x₂<=1700 и оси ОХ₁ и ОХ₂ определяют область возможных значений для неизвестных x₁ и x₂. Заштрихованная область ОАВС, содержащая точки, для которых соблюдены условия ограничений, называется допустимой. Внутри этой области бесконечное множество решений. Задача состоит в том,чтобы найти решение, максимизирующее функцию Р. Для решения этой задачи проведем через начало координат линию, на которой Р=0,т.е. 0=20x₁+40x₂. На этой линии прибыль равна нулю. Если эту линию передвигать параллельно самой себе по допустимой области, то прибыль Р будет возрастать. Линия уровня Р с максимальным значением Р, проходит через точку В. При этом Р=1400. Точка В с координатами x₁=300 и x₂=200 соответствует оптимальному решению задачи. Следовательно Р=2*300+4*200=1400.

Mы рассмотрели простую задачу с двумя переменными, позволяющую простую геометрическую интерпретацию. Оптимальное решение получено: необходимо получать 300 штук изделий типа А и 200-типа В. При этом будет получена оптимальная прибыль Р=1400 тыс.руб. Эта задача может быть расширена на три и более типов изделий. Могут быть введены такие и дополнительные ограничения (потребность рынка, возможность перевозок и т.д. ).

Общая постановка задачи

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

от n вещественных переменных x1, x2,..., xn удовлетворяющих условиям неотрицательности:

и m линейным ограничениям :

Приведем некоторые типичные задачи линейного программирования, которые встречаются в строительстве.

Задача использования ресурсов

Предприятие имеет m видов ресурсов, количество которых соответственно равно b_i(i=1,2,...,m) единиц, из которых производится n видов продукции. Предприятие может обеспечить выпуск каждого вида продукции в количестве не более D_j(j=1,2,....,n) единиц. Для производства единицы j-й продукции необходимо a_ij единиц i-го ресурса. при реализации единицы j-й продукции прибыль составляет C_j единиц. Необходимо составить план выпуска продукции, который обеспечивал бы по лучение максимальной прибыли при реализации всей выпущенной продукции. Если через x_j(j=1,2,...n) обозначить количество единиц j-й продукции, которое необходимо выпустить, то поставленная задача имеет следующую математическую модель.

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

при ограничениях:

i=1,2,...,m,

x_j=> 0, j=1,2,...,n.

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