Теория расписаний

7. В торговом зале необходимо выставить для продажи товары Т1 и Т2. Рабочее время продавцов не превышает 340 часов, а площадь торгового зала, которую можно занять, не превышает 120 м². Каждая реализованная единица товара приносит прибыль соответственно в 50 и 80 ден. ед. Нормы затрат ресурсов на единицу проданного товара составляют:

Найти оптимальную структуру товарооборота (чем меньше единиц товара, тем лучше), обеспечивающую прибыль не менее 30 000 ден. ед.

Содержание

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

2. Теория расписаний......................................................................................7

Задача..............................................................................................................11

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

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

Транспортная задача формулируется следующим образом. Не которая фирма объединяет n предприятий П₁,..., П_n, производящих некоторую продукцию. Для производства этой продукции предприятиям необходимо определенное сырье в количестве b₁, …, b_n единиц соответственно в заданную единицу времени t (например, в день). Сырье может быть доставлено из m точек (сырьевых баз) Б₁,..., Б_m. Возможности сырьевых баз ограничены заданными величинами d₁, …, d_m единиц соответственно в заданную единицу времени t. Стоимость доставки единицы сырья (включая стоимость самого сырья) из точки Б, на предприятие П, задана и равна P_ij. Требуется составить оптимальный план перевозок, т. е. такой план, при котором потребности предприятий были бы обеспечены при минимальных затратах на доставку.

Исходные данные оформляются в таблице.

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

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

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

и, кроме того, имеются ограничения на возможности сырьевых баз:

Естественно, по смыслу задачи все х_ij должны быть неотрицательными.

Таким образом, получим следующую математическую модель

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

1. Диагональный метод, или метод северо-западного угла.

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

Заполнение таблицы начинается с ее северо-западного угла, т. е. клетки с неизвестным. Первая база может полностью удовлетворить потребность первого заказчика. Полагая, вписываем это значение в клетку и исключаем из рассмотрения первый столбец. На базе остается измененный запас. В оставшейся новой таблице с тремя строками и четырьмя столбцами; северо-западным углом будет клетка для неизвестного. Первая база с запасом может полностью удовлетворить потребность второго заказчика. Полагаем, вписываем это значение в клетку и исключаем из рассмотрения второй столбец. На базе остается новый остаток (запас). В оставшейся новой таблице с тремя строками и тремя столбцами северо-западным углом будет клетка для неизвестного. Теперь третий заказчик может принять весь запас с базы. Полагаем, вписываем это значение в клетку и исключаем из рассмотрения первую строку. У заказчика из осталась еще не удовлетворенной потребность.

Теперь переходим к заполнению клетки для неизвестного и т.д.

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

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

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

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

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

2. Теория расписаний

Теория расписаний (ТР) является частью исследования операций. ТР исследует задачи, в которых необходимо упорядочить или, другими словами, определить последовательность выполнения совокупности работ, использования каких-либо средств и т.д.

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

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

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

1) Подлежащие выполнению работы определены и известны полностью. Предполагается, что все заданные работы должны быть выполнены.

2) Однозначно определены устройства, выделяемые для выполнения заданных работ.

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

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

1) индексом принадлежности к определенной работе,

2) индексом принадлежности к определенной машине,

3) числом, представляющим собой длительность операции.

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

Для каждой работы задается последовательность составляющих ее операций (определяемая технологическим процессом). Такое частичное упорядочение операций осуществляется заданием отношения порядка. Если операция X должна быть осуществима раньше, чем Y, то говорят, что X предшествует Y. Это записывается в виде: X<Y или Y>X. Отношение порядка транзитивно: если X<Y, Y<Z, то X<Z. Будем говорить, что операция X непосредственно предшествует операции Y и записывать X<<Y или Y>>X, если X<Y и нет операции Z, такой, что X <Z<Y.

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

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

· - равно длительности операции;

· число - значение , относящееся к X, не меньше, чем для двух операций X и Y относящихся к одной работе и таких, что ;

· каждый из интервалов расположен целиком внутри одного из отрезков времени доступности соответствующей машины.

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

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

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

2) Работы представляют собой строго упорядоченные последовательности операций. Для заданной операции X существует не более одной операции Y такой, что , и одной операции Z такой, что .

…

3) Каждая операция выполняется только одной машиной.

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

5) Отсутствуют прерывания операций. Для каждой операции задан единственный интервал , причем длительность операции равна .

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

7) В каждый момент времени машина может выполнять не более одной операции.

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

Задача

В торговом зале необходимо выставить для продажи товары Т1 и Т2. Рабочее время продавцов не превышает 340 часов, а площадь торгового зала, которую можно занять, не превышает 120 м². Каждая реализованная единица товара приносит прибыль соответственно в 50 и 80 ден. ед. Нормы затрат ресурсов на единицу проданного товара составляют:

Найти оптимальную структуру товарооборота, обеспечивающую прибыль не менее 30 000 ден. ед.

1. Переменные:

Т1- количество товара Т1

Т2 – количество товара Т2

2. Функция цели:

f(x) = Т1 + Т2 => min

3. Ограничения:

Рабочее время: 0,4Т1+0,6Т2 ≤ 340

Площадь: 0,2Т1+0,1Т2 ≤ 120

Прибыль: 50Т1+80Т2 ≥ 30000

Т1≥0, Т2≥0

Т1 и Т2 – целые

Вывод: для того, чтобы обеспечить оптимальную структуру товарооборота, необходимо выставить 375 товаров Т2. Прибыль составит 30000 ден. ед.

Графический метод.

0,4Т1+0,6Т2 = 340

Т1=0 Т2=567

Т1=850 Т2=0

0,2Т1+0,1Т2 = 120

Т1=0 Т2=1200

Т1=600 Т2=0

50Т1+80Т2 = 30000

Т1=0 Т2=375

Т1=600 Т2=0

50Т1+80Т2 = 30000

Т1 = 0

Т2= 30000/80 = 375

Поиск по сайту: