Затраты сырья для производства красок

Сырье	Краска типа А, кг	Краска типа В, кг	Месячный запас, т

 

В табл. 5.1 указано, сколько и какого сырья необходимо для производства одной тонный краски типа А и одной тонны краски типа Б, а также величины месячных запасов этого сырья. Величина запасов указана из расчета потребностей прошлых производственных планов.

Методика выполнения. Безусловно, чем больше будет произведено продукции, тем лучше. Поэтому первая цель – произвести как можно больше краски типов А и Б. Однако имеется ограничение по производственным мощностям – 500 т.

Вторая цель заключается в получении максимальной прибыли от производства и реализации продукции. Факторами, влияющими на достижение данной цели, будут величины удельной прибыли по каждому виду продукции – 2000 руб. и 2500 руб. Прибыль предприятия в реальной экономике зависит от множества факторов и не является величиной постоянной даже на протяжении короткого промежутка времени. Поэтому ее трудно оценить на длительный период и можно оценить только будущую удельную прибыль с некоторой степенью точности. Для достижения второй цели выгодно производить только краску типа Б и совсем не производить краску типа А. Но есть два ограничения, определенные договорами поставки и трудностью реализации большого количества краски типа Б. при таких ограничениях понятно, что нужно производить 350 т краски типа А и 150 т краски Б. Таким образом будут учтены ограничения по производственным мощностям и маркетинговые ограничения.

 

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

После анализа проблемы получаем следующую информацию:

 

Постановка проблемы	Разработать производственный план, который бы максимизировал прибыль с учетом всех видов ограничений.
Цель	Максимизировать прибыль.
Решение	Количество тонн краски типов А и Б, производимых в месяц.
Факторы, от которых зависит решение	Значения удельной прибыли каждого типа краски, предельное число производимой краски, предельные числа производимых красок типов А и Б (маркетинговые ограничения), количества сырья (необходимого для производства одной тонны краски), значения запасов сырья (всего 14 факторов).
Факторы, влияющие на прибыль	Все перечисленные, кроме значений количества сырья, необходимого для производства одной тонны краски.
Ограничения	На предельное общее количество производимой краски, на предельные количества производимых красок типов А и Б в отдельности, на предельные количества используемого сырья (всего 6 ограничений).

 

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

Математическая модель должна содержать три основных компонента.

Переменные –необходимо вычислить (переменные решения из формальной модели).

Целевая функция –это цель, записанная математически в виде функции от переменных. Обязательно указывается, что необходимо сделать с этой функцией: найти максимум, минимум или конкретное заданное значение.

Ограничения –записанные математически ограничения из формальной модели.

Обозначим через х₁ и х₂ переменные, которые определяют месячные объемы производства краски (в тоннах) типов А и Б соответственно. Зная прибыль от продажи одной тонны краски, получаем суммарную прибыль Z при производстве х₁ тонн краски типа А и х₂ тонн краски типа Б, руб.:

 

Z = 2000 х₁ + 2500 х₂.

 

Это целевая функция, которую необходимо максимизировать.

Далее рассмотрим ограничения. Суммарный объем производства не должен превышать 500 т: х₁ + х₂ ≤ 500. Маркетинговые ограничения записываем как х₁ ≥ 200; х₂ ≤ 150.

Ограничения на сырье записываются по каждому виду сырья с учетом расхода по каждому виду продукции. Для производства х₁ тонн краски типа А и х₂ тонн краски типа Б расходуется 0,05 х₁ + 0,1 х₂ тонн сырья 1. Поскольку эта величина не должна превышать величины запаса – 50 т, получаем ограничение 0,05 х₁ + 0,1 х₂ ≤ 50. Подобным образом получаем два других ограничения по сырью 2 и сырью 3: 0,07 х₁ + 0,08 х₂ ≤ 30; 0,04 х₁ + 0,07 х₂ ≤ 25. Еще одно неявное ограничение состоит в том, что переменные х₁ и х₂ должны быть неотрицательными (объем производства не может быть отрицательным числом). Это ограничение называется условием неотрицательности переменных и записывается так: х₁ ≥ 0; х₂ ≥ 0. Однако уже есть условие х₁ ≥ 200, поэтому ограничение х₁ ≥ 0 исключаем из списка ограничений.

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

Максимизировать Z = 2000 х₁ + 2500 х₂.

При выполнении ограничений:

х₁ + х₂ ≤ 500; х₁ ≥ 200; х₂ ≤ 150;

0,05 х₁ + 0,1 х₂ ≤ 50; 0,07 х₁ + 0,08 х₂ ≤ 30; 0,04 х₁ + 0,07 х₂ ≤ 25;

х₂ ≥ 0.

Строим табличную модель на листе Excel (рис. 5.1).

Диапазон D10:D16 представляет собой вычисляемые ячейки. Формулы, по которым выполняются все вычисления на данном рабочем листе, показаны на рис. 5.2.

Все ячейки должны иметь заголовки. В каждой строке ограничений за ячейками, содержащими коэффициенты данного ограничения, следует ячейка, в которую записывается вычисленное значение функции ограничения (значение левой части ограничения). За ней следует ячейка, в которой стоит соответствующий знак неравенства или равенства ограничения, а затем ячейка, содержащая значение правой части ограничения.

Значения переменных вносят изначально произвольные. Целевая функция вычисляется в ячейке D7. В диапазоне В10:С16 записаны коэффициенты функций ограничений, в диапазоне F10:F16 – значения правых частей ограничений, в диапазоне D10:D16 вычисляются значения левых частей ограничений.

 

 

Рис. 5.1. Табличная модель

 

 

Рис. 5.2. Формулы табличной модели

 

Для вычислений используем функцию СУММПРОИЗВ. Абсолютные ссылки делаем на ячейки, содержащие значения переменных. Такое расположение данных позволяет скопировать формулу, введенную в строку 10. Кроме того, соблюдение такого принципа построения табличных моделей позволяет легко изменять ограничения путем изменения значений соответствующих коэффициентов.

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

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

 

Рис. 5.3. Параметры для решения

 

В поле Установить целевую ячейку вводится адрес ячейки, содержащей значение целевой функции. Для данной модели это D7. Параметры области Равной необходимо установить максимальному значению,поскольку необходимо максимизировать значение. Поле Изменяя ячейки позволяет указать ячейки, в которых содержатся переменные модели: В4:С4.

Далее необходимо указать ограничения. Нажать кнопку Добавить и сделать ссылку на диапазон D10:D14. Знак неравенства был установлен <=, переносим его в ограничения. В поле Ограничение вводим диапазон F10:F14.

Далее необходимо ввести второю группу ограничений: в поле Ссылка на ячейку вводим D15:D16, знак >=, в поле ограничение F15:F16. Возвращаемся в диалоговое окно Поиск решения.

Далее настраиваем параметры (кнопка Параметры, рис. 5.4).

 

 

Рис. 5.4. Диалоговое окно Параметры поиска решения

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

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

 

 

Рис. 5.5. Успешное завершение решения задачи оптимизации

 

При этом можно выбрать отчет о решении (рис. 5.6, 5.7).

В нашем примере получено следующее решение: надо производить 257,14 т краски типа А и 150 т краски типа Б, при этом будет получена прибыль в размере 889 285,71 руб.

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

Более существен для анализа чувствительности отчет по устой­чивости.

 

 

Рис. 5.6. Отчет по результатам

 

 

Рис. 5.7. Отчет по устойчивости

 

Первая табли­ца Изменяемые ячейки этого отчета дает информацию о значениях изменяемых ячеек:

§адреса изменяемых ячеек;

§их имена; если имен нет, то это поле остается пустым;

§значения переменных в этих ячейках, найденные средством Поиск решения;

§нормированная стоимость – это значение, равное нулю, если значение соответствующей переменной находится в границах своего возможного изменения, но не достигает этих границ (учитываются границы, которые задаются явно в виде неравенств типа х ≥ 0 и/или х ≤ 100). Если переменная равна значению одной из своих явно заданных границ (например, равна нулю при заданном усло­вии неотрицательности), то значение нормированной стоимости показывает, насколько изменится значение целевой функции, если значение этой переменной увеличится на единицу;

§ целевой коэффициент – коэффициент, стоящий при данной изменяе­мой переменной в формуле целевой функции;

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

В таблице Ограничения приведена информация об ограничениях:

§ адреса ячеек, на значения которых наложены ограничения;

§ их имена (созданные заранее или составленные из заголовков строк и столбцов, на пересечении которых находятся изменяе­мые ячейки); если имен нет, то это поле остается пустым;

§ значения в этих ячейках, найденные средством Поиск решения;

§ теневая цена показывает, насколько изменится значение целе­вой функции, если на единицу изменится значение правой ча­сти данного ограничения; теневая цена отлична от нуля только тогда, когда данное ограничение в оптимальном решении явля­ется связанным (и решение не вырождено);

§ значения правых частей ограничений;

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

Проведем анализ чувствительности. Во-первых, переменные решения нулевых значений не принимают. Рассмотрим ограничения. Первое ограничение, задающее предельный объем производства, лимитирующим (связанным) не является (на это прямо указывает отчет по результатам и нулевое значение теневой цены для этого ограничения в отчете по устойчивости). Отсюда следует вывод, что такой производственный план задействует мощности завода не в полной мере. Это большой «минус» данного плана.

Проанализируем, что сдерживает объемы производства. Лимитиру­ющими являются второе маркетинговое ограничение и ограничение по сырью 2 (на это указывает отчет по результатам и ненулевые зна­чения теневых цен для этих ограничений в отчете по устойчивости). Влиять на маркетинговое ограничение трудно, поскольку отдел маркетинга ставит свои условия, для изменений нужны веские обоснования, а их, конечно, нет. Чтобы полностью загрузить мощности производства, надо запланиро­вать еще почти 93 т краски, а такое увеличение производства краски типа Б нецелесообразно, так как даже объем в 150 т трудно продать.

Другое лимитирующее ограничение определяется наличием на складе запаса сырья 2. Разберемся с этим параметром. Взглянем на теневую цену этого ограничения, она равна 28 571,43. Это означает, что изменение на одну единицу величины правой части данного огра­ничения (т. е. изменение величины запаса сырья 2 на 1 т) при­ведет к изменению на 28 571,43 руб. величины прибыли (значения целевой функции). Очевидно, что в данном случае при увеличении значения правой части ограничения значения целевой функции будет возрастать, а при уменьшении – убывать. Насколько нужно уве­личить запас сырья 2, чтобы полностью загрузить все производствен­ные мощности, отчет по устойчивости ответа не дает.

Посмотрим на число в столбце Допустимое увеличение для этого ограничения. Оно равно 6,5. Это значит, что с увеличением значения правой части ограничения до величины 36,5 остается прежнее решение — значения переменных и целевой функции, ко­нечно, будут изменяться, но лимитирующими и нелимитирующими останутся прежние ограничения. Если же значение правой части ограничения будет равно или превысит величину 36,5, то в качестве лимитирующего в игру вступит другое ограничение, которое на дан­ный момент не является лимитирующим.

Чтобы узнать, что же получится при изменении правой части пятого ограничения до величины 36,5, надо опять запускать Поиск решения. Итак, вносим в ячейку F13 значение 36,5 и выбираем коман­ду Сервис → Поиск решения. В диалоговом окне Поиск решения ничего менять не надо (средство Поиск решения сохраняет все установки сво­его предыдущего использования), можно сразу щелкнуть на кнопке Выполнить.

В этом решении х₁ = 350, x₂ = 150 и z = 1 075 000. Новым лимитирующим ограничением стало первое ограничение, задающее предельный объем производства. Нам повезло, что изменение только одного параметра модели (значения правой части ограничения по сырью 2) уже привело к решению (про­изводственному плану), где производственные мощности завода за­действованы полностью. В общем случае, если действительно есть не­обходимость задействовать все мощности производства, скорее всего, пришлось бы проверять другие лимитирующие ограничения и про­бовать изменять их правые части.

Оптимальным про­изводственным планом будет производство 350 т краски типа А и 150 т краски типа Б. Однако чтобы выполнить такой план, надо увеличить месячные запасы сырья 2 на 6,5 т, а месячные за­пасы сырья 1 и сырья 3 можно уменьшить на 17,5 и 0,5 т соответ­ственно. Это уже не совсем очевидный результат. Но и этот резуль­тат можно было получить другим способом, поскольку нетрудно подсчитать необходимые запасы сырья для производства 350 т краски типа А и 150 т краски типа Б. Затем надо подсчитать, на сколько увеличится (и уве­личится ли) себестоимость краски, если докупить дополнительные объемы сырья 2, так как возрастут расходы на хра­нение сырья. Это может повлиять на удельную прибыль краски, т. е. могут измениться значения коэффициентов при переменных в фор­муле целевой функции. А если это произойдет, то все вычисления надо начинать сначала. Кроме того, надо вспомнить, что значения этих коэффициентов известны нам только приближенно.

 

Рекомендуемая литература: [7, 14, 16, 18, 20, 21, 22].

 

Лабораторная работа № 6
Модели транспортного типа

Цель: приобрести навыки в использовании настройки Поиск решения с условием максимизации или минимизации целевой функции.

 

Под термином «транспортные задачи» понимается широкий круг задач не только транспортного характера. Общим для них является, как правило, распределение ресурсов, находящихся у n производителей (поставщиков), по mпотребителям этих ресурсов.

На автомобильном транспорте наиболее часто встречаются следующие задачи, относящиеся к транспортным:

· прикрепление потребителей ресурса к производителям;

· привязка пунктов отправления к пунктам назначения;

· взаимная привязка грузопотоков прямого и обратного направлений;

· отдельные задачи оптимальной загрузки промышленного оборудования;

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

Рассмотрим экономико-математическую модель прикрепления пунктов отправления к пунктам назначения.

Имеются n пунктов отправления груза O₁, O₂,..., O_m, где ожидают отправления запасы грузов объемом a₁, a₂,..., a_n соответственно. Известна потребность в грузах b₁, b₂,...,b_m по каждому из m пунктов назначения H₁, H₂,..., H_m. Задана также матрица стоимостей с_ij, (i = 1,2,...,n, j = 1,2,...,m) доставки груза из пункта O_i в пункт H_j. Необходимо рассчитать оптимальный план перевозок, т. е. определить, сколько груза x_ij должно быть отправлено из каждого пункта отправления (от поставщика) в каждый пункт назначения (до потребителя) с минимальными суммарными транспортными издержками.

В общем виде исходные данные представлены в табл. 6.1.

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

Таблица 6.1

Транспортная таблица

Пункты наз-начения Пункты отправления	H1	H2	…	Hm	Запасы (предложения в пунктах отправления)
O1	С11 Х11	С12 Х12	…	С1m Х1m	a1
O2	С21 Х21	С22 Х22	…	С2m Х2m	a2
….	…	…	…		…
Om	Сn1 Хn1	Сn2 Хn2	…	Сnm Хnm	an
Заказы (спрос на грузы в пунктах назначения)	b1	b2	…	bm	…

 

Если такого равенства нет (потребности выше запасов или наоборот), задачу называют открытой.

В зависимости от того, совпадают или нет суммарные объемы грузов в пунктах отправления и пунктах назначения, различают три типа транспортных задач.

· Если сумма Σa_i грузов в пунктах отправления равна сумме Σb_j ожидаемых грузов в пунктах назначения, то такая транспортная задача называется сбалансированной.

· Если Σa_i < Σb_j, то это несбалансированная задача с дефицитом.

· Если Σa_i > Σb_j, то это несбалансированная задача с избытком.

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

Все j-е пункты (потребители) должны быть обеспечены грузами в плановом объеме.

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

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

Ø потребности по пунктам назначения превышают запасы пунктов отправления, то вводится фиктивный поставщик с недостающим объемом отправления;

Ø запасы поставщиков превышают потребности потребителей, то вводится фиктивный потребитель с необходимым объемом потребления.

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

В соответствии с транспортной таблицей удельные стоимости перевозок и переменные решения удобно записать в виде матрицы стоимостей С и матрицы решений Х:

 

 

Целевая функция, которую следует минимизировать, записывается так:

Z = C₁₁X₁₁ + C₁₂X₁₂ + … + C_1mX_1m + C₂₁X₂₁ + C₁₂X₁₂ + … +
+ C_2mX_2m + … + C_n1X_n1 + C_n2X_n2 +…+ C_nmX_nm.

Ограничения для сбалансированной задачи приведены ниже.

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

х₁₁ + х₁₂ + … + х_1m = а₁;

х₂₁ + х₂₂ + … + х_2m = а₂;

_{………………………………..}

Х_n1 + х_n2 + … + х_nm = а_n.

2. Сумма грузов, полученных в любом пункте назначения, должна равняться объему грузов, заказан­ных в этом пункте назначения:

х₁₁ + х₂₁ + … + х_n1 = b₁;

х₁₂ + х₂₂ + … + х_n2 = b₂;

_{………………………………..}

Х_1m + х_2m + … + х_nm = b_m.

В соответствии с транспортной таблицей левые части ограничений первой группы – это суммы элементов матрицы X по строкам, кото­рые равны соответствующим значениям правого столбца этой табли­цы. Аналогично левые части ограничений второй группы – суммы элементов матрицы X по столбцам, которые равны числам нижней строки таблицы.

Ограничения для задачи с дефицитом приведены ниже.

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

х₁₁ + х₁₂ + … + х_1m = а₁;

х₂₁ + х₂₂ + … + х_2m = а₂;

_{………………………………..}

Х_n1 + х_n2 + … + х_nm = а_n.

2. Сумма грузов, полученных в любом пункте назначения, меньше объема грузов, заказан­ных в этом пункте назначения:

х₁₁ + х₂₁ + … + х_n1 ≤ b₁;

х₁₂ + х₂₂ + … + х_n2 ≤ b₂;

_{………………………………..}

Х_1m + х_2m + … + х_nm ≤ b_m.

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

1. Запас грузов в пункте отправления больше суммы грузов, отправленных из любого пункта отправления:

х₁₁ + х₁₂ + … + х_1m ≤ а₁;

х₂₁ + х₂₂ + … + х_2m ≤ а₂;

_{………………………………..}

Х_n1 + х_n2 + … + х_nm ≤ а_n.

2. Сумма грузов, полученных в любом пункте назначения, равна объему грузов, заказан­ных в этом пункте назначения:

х₁₁ + х₂₁ + … + х_n1 = b₁;

х₁₂ + х₂₂ + … + х_n2 = b₂;

_{………………………………..}

Х_1m + х_2m + … + х_nm = b_m.

Транспортным задачам присущи следующие особенности:

· распределению подлежат однородные ресурсы;

· условия задачи описываются только уравнениями;

· все переменные выражаются в одинаковых единицах измерения;

· во всех уравнениях коэффициенты при неизвестных равны единице;

· каждая неизвестная встречается только в двух уравнениях системы ограничений.

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

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

Решение задачи методом потенциалов включает следующие этапы:

· разработку начального плана (опорного решения);

· расчет потенциалов;

· проверку плана на оптимальность;

· поиск максимального звена неоптимальности;

· составление контура перераспределения ресурсов;

· определение минимального элемента в контуре перераспределения и перераспределение ресурсов по контуру;

· получение нового плана.

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

Для транспортной задачи существует несколько методов отыскания начального плана (опорного решения):

Ø метод северо-западного угла;

Ø метод минимальной стоимости;

Ø метод двойного предпочтения и т. д.

Решение с помощью транспортной таблицы. Одним из способов решения транспортных задач является решение с помощью таблицы.

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

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

Задание 1. Компания «Прибой» хранит свою готовую продукцию на трех складах (первом, втором и третьем), расположенных в разных частях города. На этих складах хранится продукция в количе­ствах 1000, 3000 и 2500 шт. соответственно. Продукцию необходимо доставить четырем оптовым покупателям П1, П2, ПЗ, П4, заявки кото­рых составляют 1300, 800, 2700 и 1700 шт. соответственно. Склады оптовых покупателей также расположены в разных частях города. Стоимость (в рублях) доставки одной штуки продукции со складов компании на склады покупателей показана в табл. 6.2.

 

Таблица 6.2

Транспортные расходы

№ склада компании	Оптовый покупатель
П1	П2	ПЗ	П4

 

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

– в случае превышения объема запасов – фиктивного потребителя; стоимость перевозок единицы продукции этому фиктивному потребителю полагается равной стоимости складирования, а объемы перевозок этому потребителю равны объемам складирования излишков продукции у поставщиков;

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

Решение. Для решения данной задачи построим ее математическую модель. Неизвестными здесь являются объемы перевозок. Пусть x_ij – объем перевозок от i-го поставщика j-му потребителю. Функцией цели являются суммарные транспортные расходы. Кроме того, неизвестные должны удовлетворять следующим ограничениям:

– неотрицательности объема перевозок;

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

В соответствии с введенными переменными целевая функция запишет­ся следующим образом:

 

Z = C₁₁X₁₁ + C₁₂X₁₂ + … + C_1mX_1m + C₂₁X₂₁ + C₁₂X₁₂ + … + C_2mX_2m +
+ … + C_n1X_n1 + C_n2X_n2 + … + C_nmX_nm.

 

Данную целевую функцию следует минимизировать.

Ограничения для складов компании имеют следующий вид:

х₁₁ + х₁₂ + х₁₂ + х₁₄ = 1000;

х₂₁ + х₂₂ + х₂₃ + х₂₄ = 800;

х₃₁ + х₃₂ + х₃₃ + х₃₄ = 2500.

Записываем ограничения для складов покупателей

х₁₁ + х₂₁ + х₃₁ = 1300;

х₁₂ + х₂₂ + х₃₂ = 800;

х₁₃ + х₂₃ + х₃₃ = 2700;

х₁₄ + х₂₄ + х₃₄ = 1700.

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

1. Создадим исходную таблицу. Матрица стоимостей располагается в диапазоне В5:Е7, а матрица перевозок – в диапазоне В11:Е13 (рис. 6.1). Матрица перево­зок содержит переменные решения, они пока равны 1.

Матрицу перевозок обрамляют столбец и строка с заголовка­ми Всего, где подсчитываются суммы переменных соответственно по строкам и столбцам матрицы перевозок. Это значения левых частей ограничений. Правые части ограничений содержатся в столбце Имеется на складе (ограничения для складов компании) и в строке Необходимо (ограничения для складов покупателей).

В табличной модели есть еще она таблица (матрица) (рис. 6.2), показыва­ющая стоимость каждой перевозки (ячейки В19:Е21) и суммарные стоимости перевозок от каждого склада компании (ячейки Р19:Р21) и до каждого склада покупателей (диапазон В22:Е22).

 

 

Рис. 6.1. Матрица стоимостей и матрица перевозок

 

 

Рис. 6.2. Матрица затрат на перевозку

 

Значения в ячейках В19:Е21 вычисляются как произведения удельных стои­мостей перевозок и количеств перевезенных грузов по каждому маршруту. Например, в ячейке В19 записана формула =В5×В11. Эта формула скопирована во все остальные ячейки диапазона В19:Е21. Суммарные стоимости перевозок для складов вычисляются как сум­мы значений этой таблицы или по строкам (для складов компании), или по столбцам (для складов покупателей). Например, в ячейке F20 записана формула =СУММ(В20:Е20), а в ячейке С22 формула =СУММ(С19:С21). Матрица в режиме формул приведена на рис. 6.3.

С помощью этой матрицы удобно вычислять целевую функцию – она равна сумме всех значений диапазона В19:Е21 либо суммам значений диапазонов F19:F21 и В22:Е22. На рис. 6.3 значе­ние целевой функции в ячейке F22 вычисляется по формуле =СУММ(F19:F21). Если бы не было этой таблицы, то целе­вую функцию надо было бы вычислять по формуле

=СУММПРОИЗВ(В5:Е7;В11:Е13).

Запускаем средство Поиск решения. В одноимен­ном диалоговом окне задаем адрес целевой ячейки F22, устанавли­ваем переключатель минимальному значению, указываем адрес диа­пазона изменяемых ячеек В11:Е13, задаем ограничения. После этих манипуляций диалоговое окно должно выглядеть так, как показано на рис. 6.4.

 

 

Рис. 6.3. Матрицы в режиме формул

 

 

Рис. 6.4. Диалоговое окно Поиск решений

 

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

В соответствии с полученным решением со склада № 1 компании надо перевезти весь имеющийся там груз (в объеме 1000 шт.) на склад покупателя ПЗ (ячейка D11), при этом затраты на транспорти­ровку составят 60 тыс. руб. (ячейка D19). Со склада № 2 следует 800, 1700 и 500 шт. продукции отправить на склады покупателей П2, ПЗ и П4 соответственно (ячейки С12:Е12), затраты на перевозку соста­вят 24,170 и 20 тыс. руб. (ячейки С20:Е20). Со склада № 3 1300 шт. продукции отправятся на склад покупателя П1 (ячейка В13) при за­тратах 91 тыс. руб. (ячейка В21) и 1200 шт. поедут на склад покупа­теля П4 (ячейка Е13) при затратах 144 тыс. руб. (ячейка Е21). Общая стоимость всех перевозок составит 509 тыс. руб. (значение целевой функции в ячейке F22).

 

Рис. 6.5. Решение сбалансированной транспортной задачи

 

Рекомендуемая литература: [14, 16, 17].

Лабораторная работа № 7
Задача о назначениях

Цель: приобрести навыки в использовании настройки Поиск решения для эффективного использования трудовых ресурсов.

 

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

При решении задач о назначениях полезна табл. 7.1, подобная транспортной таблице.

В этой таблице коэффициенты с_ij равны стоимости назначения ра­ботника i на выполнение работы j. Эта стоимость может выражаться в денежном эквиваленте, длительности времени выполнения работы или может быть каким-либо другим показателем эффективности на­значения именно этого работника на данный процесс. Переменные x_ij – это переменные будущего решения задачи. Они определяются так: x_ij = 1, если работник i назначается на выполнение работы j, и x_ij = 0, если работник i не назначается на выполнение работы j. Здесь двоичные переменные, которые могут принимать только два значения: 0 или 1.

Таблица 7.1

Таблица для задачи о назначениях

Работы Работники			…	n	Сумма xij по строкам
	С11 Х11	С12 Х12	…	С1n Х1n
	С21 Х21	С22 Х22	…	С2n Х2n
…	…	…	…		…
n	Сn1 Хn1	Сn2 Хn2	…	Сnm Хnm
Сумма xij по столбцам			…		…

 

Если количества работников и работ равны, то такая задача о на­значениях называется сбалансированной, в противном случае задача будет несбалансированной.

Сбалансированной также будет задача, если на некоторые процес­сы требуются несколько работников, но при этом общие количества требуемых и имеющихся работников совпадают. Назовем такую зада­чу задачей о назначениях для коллективной работы. В данном случае «транспортная» таблица будет иметь вид, представленный в табл. 7.2.

Чтобы задача была сбалансированной, требуется выполнение равенства

 

k₁+ k₂+…+ k_m= n.

Целевая функция тоже одинакова для всех моделей и записы­вается так же, как и в транспортной задаче:

 

Z = C₁₁X₁₁ + C₁₂X₁₂ + … + C_1mX_1n + C₂₁X₂₁ + C₁₂X₁₂ + … + C_2nX_2n +
+ …+ C_n1X_n1 + C_n2X_n2 +…+ C_nnX_nn.

Таблица 7.2

Таблица для задачи о назначениях для коллективной работы

Работы Работники			…	m	Сумма xij по строкам
	С11 Х11	С12 Х12	…	С1n Х1n
	С21 Х21	С22 Х22	…	С2n Х2n
…	…	…	…		…
n	Сn1 Хn1	Сn2 Хn2	…	Сnm Хnm
Сумма xij по столбцам	k1	k2	…	km	…

Эту целевую функцию следует минимизировать, если коэффици­енты c_ij выражают стоимости назначения работника i на выполнение работы j.

Ограничения для сбалансированной задачи (без условия коллек­тивной работы) следуют непосредственно из табл. 7.1: все суммы пе­ременных по строкам и столбцам этой таблицы равны 1.

Имеем n ограничений в виде равенств для каждого работника (суммы по строкам):

х₁₁ + х₁₂ + … + х_1n = 1;

х₂₁ + х₂₂ + … + х_2n = 1;

_{………………………………..}

Х_n1 + х_n2 + … + х_nm = 1.

Аналогично имеем m ограничений в виде равенств для каждой работы (суммы по столбцам):

х₁₁ + х₂₁ + … + х_m1 = 1;

х₁₂ + х₂₂ + … + х_m2 = 1;

_{………………………………..}

Х_1m + х_2m + … + х_nm = 1.

Таким образом, математическая модель для сбалансированной задачи о назначениях при равном количестве работников и работ построена: имеется n₂ переменных х_ij, целевая функция, которую необходимо минимизировать, и 2n ограничений в виде равенств, а также условия двоичности для переменных.

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

Отсюда имеем n ограничений в виде равенств для каждого ра­ботника (суммы по строкам):

х₁₁ + х₁₂ + … + х_1n = 1;

х₂₁ + х₂₂ + … + х_2n = 1;

_{………………………………..}

Х_n1 + х_n2 + … + х_nn = 1.

Аналогично имеем от ограничений в виде равенств для каждой работы (суммы по столбцам):

х₁₁ + х₂₁ + … + х_n1 = k₁;

х₁₂ + х₂₂ + … + х_n2 = k₂;

_{………………………………..}

Х_1m + х_2m + … + х_nm = k_m.

Задание 1. Строительной фирме «Спец­строй» необходимо выполнить бетонные ра­боты на 4 строящихся объектах. В фирме имеется 4 бри­гады бетонщиков, которые могут выполнить эту работу. Бригадиры каждой бригады побывали на объектах, оценили объемы работ и рассчитали сроки, за которые они могут выполнить работы. Сроки (в рабочих днях) выполнения работ каждой бригадой приведе­ны в табл. 7.3.

Таблица 7.3

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

№ бригады	Объект
1-й	2-й	3-й	4-й

 

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

Методика выполнения. Поскольку количества бригад и объектов одинако­вы, следовательно, имеем сбалансированную задачу о назначениях.

Составляем математическую модель сбалансированной задачи. Определяем 16 двоичных переменных х_ij (i и j изменяются от 1 до 4), которые будут равны 1, если бригада i назначается на объект j,и 0, если бригада i не назначается на объект j. Если принять за стоимо­сти назначений c_ij сроки выполнения работ каждой бригадой, которые приведены в табл. 7.3, то целевую функцию можно записать так:

 

Z = 30x₁₁ + 40x₁₂ + 50x₁₃ + 60x₁₄ + 36x₂₁ + 41x₂₂ + 52x₂₃ + 58x₂₄ +
+ 28x₃₁ + 44x₃₂ + 49x₃₃ + 57x₃₄ + 35x₄₁ + 39x₄₂ + 49x₄₃ + 63x₄₄.

 

Определим ограничения. Задача сбалансированная, по­этому имеем 8 простых ограничений в виде равенств:

х₁₁ + х₁₂ + х₁₂ + х₁₄ = 1;

х₂₁ + х₂₂ + х₂₃ + х₂₄ = 1;

х₃₁ + х₃₂ + х₃₃ + х₃₄ = 1;

х₄₁ + х₄₂ + х₄₃ + х₄₄ = 1;

х₁₁ + х₂₁ + х₃₁ + х₄₁ = 1;

х₁₂ + х₂₂ + х₃₂ + х₄₂ = 1;

х₁₃ + х₂₃ + х₃₃ + х₄₃ = 1;

х₁₄ + х₂₄ + х₃₄ + х₄₄ = 1.

Далее на основе записанной математической модели создаем на рабочем листе Ехсеl табличную модель (рис. 7.1).

Значение целевой функции в ячейке F17 вычисляется по формуле СУММПРОИЗВ(В4:Е7;В11:Е14). В диапазонах F11:F14 и В15:Е15 по-преж­нему вычисляются суммы значений пере­менных соответственно по строкам и столбцам матрицы решения.

 

 

Рис. 7.1. Табличная модель
для сбалансированной задачи о назначениях

 

Запускаем средство Поиск решения. В одноименном диалоговом окне задаем адрес целевой ячейки F17, устанавливаем переключатель минимальному значению, указываем адрес диапазона изменяемых яче­ек В11:Е14, задаем ограничения. Как задавать ограничения двоичности, налагаемые на переменные решения, показано на рис. 7.2.

 

Рис. 7.2.Задание условия двоичности
для переменных решения

 

После всех установок диалоговое окно Поиск решения должно выглядеть так, как показано на рис. 7.3.

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

Найденное решение показывает, что первую бригаду надо отпра­вить на
2-й объект, вторую бригаду – на 4-й объект, третью бригаду – на 1-й объ­ект и четвертую – на 3-й объект. Общая продолжительность всех работ составит 175 рабочих дней.

 

 

Рис. 7.3. Диалоговое окно Поиск решения для решения
сба­лансированной задачи о назначениях

 

 

Рис. 7.4. Решение сбалансированной задачи о назначениях

 

 

Рекомендуемая литература: [14, 16, 17].

 

ПРИЛОЖЕНИЕ 1

Основные приемы создания
и оформления новой презентации

Поставленная задача	Требуемые действия
Создать презентацию без помощи мастера и применения шаблона	В окне диалога PowerPoint в группе полей выбора Создание презентации выберите Новая презентация
Выбрать разметку слайда	В окне диалога Создать слайд выберите требуемый вариант разметки. После выбора Новая презентация появляется окно диалога Разметка слайда. Для изменения разметки имеющегося слайда выполните команду Формат/Разметка слайда или воспользуйтесь пиктограммой, размещенной в панели Форматирование
Применить шаблон дизайна	В меню Формат выберите команду Оформление слайда или воспользуйтесь пиктограммой, размещенной в панели Форматирование
Вставить новый слайд	Откройте тот слайд, после которого вы хотите вставить новый, и выполните команду Вставка/Создать слайд (Ctrl + M) или воспользуйтесь пиктограммой, размещенной в панели Форматирование
Ввести текст или добавить объект в метки-заполнители	Чтобы добавить текст в метку-заполнитель, щелкните мышью, а чтобы добавить заданный объект, щелкните дважды. Метку-заполнитель любого объекта можно преобразовать в метку-заполнитель текста, набрав текст
Ввести текст в произвольное место слайда	Выберите на панели Рисование инструмент Надпись и установите текстовый курсор в нужное место или меню Вставка/Надпись
Удалить текст вместе с меткой-заполнителем	Щелкните по тексту, затем щелкните непосредственно по рамке метки-заполнителя и нажмите клавишу Delete
Выровнять набранный текст относительно рамки метки-заполнителя	Воспользуйтесь командой Формат/Выравнивание или кнопками панели инструментов Форматирование
Выбрать цвет и тип линии для рамки метки-заполнителя, подобрать заливку	Выделите метку-заполнитель (или установите курсор в текст, введенный в метку-заполнитель) и выполните команду Формат/ … В появившемся диалоговом окне установите цвет заливки, тип линии и ее цвет. Также можно воспользоваться кнопками панели Рисование: – заливка; – цвет линии; – тип линии
Активизировать панель Автофигуры	Выберите команду Вставка/Рисунок/Автофигуры или воспользуйтесь кнопкой панели Рисование
Нарисовать объект	Активизируйте панель Рисование, выберите соответствующий инструмент (линия, овал, прямоугольник и т. д.) и «растяните» фигуру на слайде, протаскивая курсор

Окончание прил. 1

Поставленная задача	Требуемые действия
Изменить цвет объекта	Выделите объект и выполните команду Формат/ или воспользуйтесь кнопкой панели Рисование: – цвет линии
Настроить тень (объем) объекта	Выделите объект и воспользуйтесь кнопкой панели Рисование: – Стиль тени. – Объем
Повернуть объект на какой-либо угол	Выделите объект и воспользуйтесь кнопкой панели Рисование Действия/Повернуть/отразить/Свободное вращение, а затем переместите мышью угол объекта в направлении вращения
Сгруппировать объекты	Выделите все объекты, подлежащие группировке, и выполните команду Группировка/Группировать контекстного меню выделенных объектов
Выполнить художественную надпись	Воспользуйтесь кнопкой панели Рисование: – Добавить объект WordArt
Вставить звук	Выберите команду меню Вставка/Фильмы и звук/Звук из коллекции картинок; Звук из файла
Настроить анимацию	В режиме слайдов щелкните объект, который хотите анимировать. В меню Показ слайдов выберите команду или соответствующую команду контекстного меню выбранного объекта. Выберите нужные элементы панели Настройка анимации
Способ представления документа (т. е. презентации.ppt) в окне приложения PowerPoint	Документ Power Point может отображаться в окне приложения тремя способами: в виде слайдов, в режиме структуры, в режиме сортировщика слайдов. Для изменения способа представления достаточно выбрать соответствующую команду в меню Вид или щелкнуть по одной из трех кнопок в левой части горизонтальной полосы прокрутки: – показ слайдов (с текущего слайда); – обычный режим; – режим сортировщика слайдов
Провести демонстрацию	Выполните команду Вид/Показ слайдов (F5) или воспользуйтесь кнопкой
Перейти к следующему слайду в процессе демонстрации	Воспользуйтесь щелчком мыши, клавишами Enter, Пробел; Page Down, Page Up или клавиши навигации курсора (­¯®): переход вперед/назад по галерее слайдов; Home – переход к самому первому слайду; End – переход к самому последнему слайду
Провести демонстрацию, не запуская PowerPoint	Найдите свой файл, выделите и вызовите контекстное меню нажатием правой кнопки мыши. В контекстном меню выберите команду Показать

 

ПРИЛОЖЕНИЕ 2

Основные приемы создания
и оформления презентации по шаблону

Поставленная задача	Требуемые действия
Создать презентацию на основе готового шаблона	· В меню Файл выберите команду Создать; в группе полей выбора Создание с помощью шаблона откройте презентацию с соответствующей темой из группы Общие шаблоны. · Измените заголовок шаблона и предлагаемое содержание в соответствии с вашими требованиями. В режиме слайдов измените по желанию цветовую схему, добавьте или измените элементы образца
Создать собственный шаблон	· Подготовьте презентацию, которую вы хотите в дальнейшем использовать как шаблон. · В меню Файл выберите команду Сохранить как; раскройте список Тип файла и выберите Шаблон презентации (*.pot); введите имя для нового шаблона и нажмите кнопку Сохранить
Установить способ перехода слайда	· Находясь в режиме слайдов выберите команду Показ слайдов/Смена слайдов. · В списке Применить к выделенным слайдам выберите нужный эффект
Установить время перехода слайдов	· В окне диалога Смена слайдов в группе полей выбора Смена слайда выберите автоматически после и задайте время. · Перед выполнением демонстрации выберите команду Показ слайдов/Настройка презентации, в группе полей выбора Смена слайдов установите по времени
Изменить порядок слайдов	Перейдите в режим Сортировщика слайдов и переместите мышью слайды, разместив их в требуемом порядке
Вставить рисунок	· Выполните команду Вставка/Рисунок/Из файлаили щелкните на панели Рисование PowerPoint. · В открывшемся файлере выберите нужный файл
Вставить графику из коллекции картинок	· Выполните команду Вставка/Рисунок/Картинкиили щелкните . · Выберите команду Коллекция картинок. · В открывшемся файлере выберите нужное изображение. · Запомните в Clipbord: команда Копировать. · Перейдите к слайду и вставьте изображение из буфера обмена
Вставить символ Microsoft Office	Для набора символов Microsoft Office удобно воспользоваться Таблицей символов. · По кнопке Пуск на панели задач Windows выберите Программы. · Далее перейдите в раздел Стандартные/Служебные /Таблица символов. · Выберите нужный шрифт и символ, нажмите Копировать. · Перейдите к слайду и вставить символ из буфера обмена. · Окно Таблица символов можно закрыть