Технология решения задач линейной оптимизации

Размещено на http://www.allbest.ru/

Тема: Технология решения задач линейной оптимизации

Цель: освоение специального инструментария MS Excel для решения оптимизационных задач.

Краткие теоретические сведения.

Типы задач оптимизации:

o Задачи о перевозках: например, минимизация расходов по доставке товаров с нескольких фабрик в несколько магазинов с учетом спроса;

o Задачи распределения рабочих мест: например, минимизация расходов на содержание штата с соблюдением требований, определенных законодательством;

o Управление ассортиментом товаров: извлечение максимальной прибыли с помощью варьирования ассортиментным набором товаров (при соблюдении требований клиентов). Аналогичная задача возникает при продаже товаров с разной структурой затрат, рентабельностью и показателями спроса.

o Замена или смешивание материалов: например. Манипуляция материалами с целью снижения себестоимости, поддержания необходимого уровня качества и соблюдения требований потребителей.

o Задачи линейной алгебры: решение линейных уравнений.

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

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

В технологическом процессе решения линейной оптимизационной задачи с помощью Excel выделяются три типовых этапа:

1. подготовительный (подготовка табличной модели до обращения к диалоговому окну оптимизатора, ввод данных и формул);

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

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

Задачи, решаемые с помощью оптимизатора, имеют три характерных признака:

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

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

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

Элементы диалогового окна Поиск решения

оптимизация экстраполяция переменная excel



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

Рассмотрим элементы диалогового окна Поиск решения. Для этого зайдем в Сервис, Поиск решения. Средство поиска решений является одной из надстроек Excel. Если в меню Сервис отсутствует команда Поиск решения, то для установки необходимо выполнить команду Сервис, Надстройки, Поиск решения.

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

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

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

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

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

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

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

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

Рассмотрим элементы этого окна:

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

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

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

Флажок Линейная модель служит для поиска решения линейной задачи оптимизации или линейной аппроксимации нелинейной задачи. В случае нелинейной задачи этот флажок должен быть сброшен, в случае линейной задачи - установлен, т.к. в противном случае возможно получение неверного результата.

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

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

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

Группа Оценки служит для выбора метода экстраполяции

Группа Разности служит для выбора метода численного дифференцирования

Группа Метод поиска служит для выбора алгоритма оптимизации

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

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

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

1. Линейная оптимизационная задача

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

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

Ресурсы	Нормы затрат ресурсов на одно изделие	Общее количество ресурсов
	стол	шкаф
Древесина: 1 вида	0,2	0,1	40
2 вида	0,1	0,3	60
Трудоемкость (человеко-часов)	1,2	1,5	371,4
Прибыль от реализации одного изделия (руб.)	6	8

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

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

1. Для определения каких величин строится модель?

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

3. Каким ограничениям должны удовлетворять неизвестные?

В нашем случае мебельной фабрике необходимо спланировать объем производства столов и шкафов так, чтобы максимизировать прибыль. Поэтому переменными являются: x1 - количество столов, х2 - количество шкафов.

Суммарная прибыль от производства столов и шкафов равна z = 6*x1 + 8*x2. Целью фабрики является определение среди всех допустимых значений х1 и х2 таких, которые максимизируют суммарную прибыль, т.е. целевую функцию z.

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

Нормы затрат древесины на столы и шкафы не может превосходить максимально возможный запас данного исходного продукта, следовательно:

Кроме того, ограничение на трудоемкость не превышает количества затрачиваемых ресурсов

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

Максимизировать

при следующих ограничениях:

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

Решим данную задачу с помощью команды Сервис, Поиск решения (Tools, Solver). Средство поиска решений является одной из надстроек Excel. Если в меню Сервис(Tools) отсутствует команда Поиск решения (Solver), то для ее установки необходимо выполнить команду Сервис, Надстройки, Поиск решения (Tools, Add-ins, Solver).

Отведем ячейки А3 и В3 под значения переменных х1 и х2 (рис. 1).

Рис. 3. Диапазоны, отведенные под переменные, целевую функцию и ограничения

В ячейку С4 введем функцию цели: =6*А3+8*В3, в ячейки А7:А9 введем левые части ограничений:

=0,2*А1+0,1*В3

=0,1*А3+0,3*В3

=1,2*А3+1,5*В3,

а в ячейки В7:В9 - правые части ограничений.

Теперь выберем команду Сервис, Поиск решения (Tools, Solver) и заполним открывшееся диалоговое окно Поиск решения (Solver), как показано на рис. 2.



Рис. 4. Диалоговое окно Поиск решения задачи о максимизации прибыли на фабрике

Не забудьте в диалоговом окне Параметры поиска решения (Solver Options) установить флажок Линейная модель (Assume Linear Model). После нажатия кнопки Выполнить (Solve) открывается окно Результаты поиска решения (Solver Results), которое сообщает, что решение найдено (рис. 3).

Рис. 5. Диалоговое окно Результаты поиска решения

Результаты расчета задачи представлены на рис. 4, из которого видно, что оптимальным является производство 102 столов и 166 шкафов. Этот объем производства принесет фабрике 1940 руб. прибыли.



Рис. 6. Результаты расчета с помощью средства поиска решений для задачи максимизации выпуска столов и шкафов

Задания для самостоятельного решения

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

Тип оборудования	Затраты времени (станко-часов) на обработку одного изделия	Общий фонд полезного рабочего времени
	А	В
Фрезерное	10	8	168
Токарное	5	10	180
Шлифовальное	6	12	144
Прибыль от реализации одного изделия (руб.)	14	18

Найти план выпуска изделий вида А и В, обеспечивающий максимальную прибыль от их реализации.

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

Найти оптимальное соотношение количества кормов и численности поголовья лис и песцов.

Вид корма	Количество единиц корма, которое ежедневно должны получать	Общее количество корма
	А	В
Вид 1	2	3	180
Вид 2	4	1	240
Вид 3	6	7	426
Прибыль от реализации одной шкурки (руб.)	16	12

3) Для изготовления различных изделий А, В и С предприятие использует три различных видов сырья. Нормы расхода сырья на производство одного изделия каждого вида, цена одного изделия А, В и С, а также общее количество сырья каждого вида, которое может быть использовано предприятием, приведены в таблице:

Вид сырья	Норма затрат сырья (кг) на одно изделие	Общее количество сырья (кг)
	А	В	С
Вид 1	18	15	12	360
Вид 2	6	4	8	192
Вид 3	5	3	3	180
Цена одного изделия (руб.)	9	10	16

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

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

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

Артикул ткани	Норма расхода ткани (м) на одно изделие вида	Общее количество ткани (м)
	Вид 1	Вид 2	Вид 3	Вид 4
Артикул 1	1	-	2	1	180
Артикул 2	-	1	3	2	210
Артикул 3	4	2	-	4	800
Цена одного изделия (руб.)	9	6	4	7

5) Фабрика "GRM pie" выпускает два вида каш для завтрака -- "Crunchy" и "Chewy". Используемые для производства обоих продуктов ингредиенты в основном одинаковы и, как правило, не являются дефицитными. Основным ограничением, накладываемым на объем выпуска, является наличие фонда рабочего времени в каждом из трех цехов фабрики.

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

Цех	Необходимый фонд рабочего времени, чел.-ч/г	Общий фонд рабочего времени, чел.-ч. в месяц
	"Crunchy"	"Chewy"
А. Производство В. Добавка приправ С. Упаковка	10 3 2	4 2 5	1000 360 600

Доход от производства 1 т "Crunchy" составляет 150 ф. ст., а от производства "Chewy" -- 75 ф. ст. На настоящий момент нет никаких ограничений на возможные объемы продаж. Имеется возможность продать всю произведенную продукцию.

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

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

Мистера Петерса проконсультировали, что наилучшим вариантом вложения инвестиций был бы инвестиционный фонд, и в настоящее время он рассматривает возможность помещения инвестиций в один из таких фондов, состоящий из инвестиций трех типов -- А, В и С. Сумма единовременного пособия составит 25000 ф. ст., однако, мистер Петере считает, что нет необходимости вкладывать в данный инвестиционный фонд все деньги; часть из них он намерен перевести на свой счет жилищно-строительного кооператива, который гарантирует ему 9% годовых.

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

Поэтому ему посоветовали не менее 40% от общей суммы вложить в вариант А и перевести на свой счет. Для обеспечения значительного роста капитала не менее 25% общей суммы денежных средств, вложенных в инвестиционный фонд, необходимо поместить в проект В, однако, вложения в В не должны превышать 35% общего объема вложений в инвестиционный фонд ввиду высокой вероятности риска, соответствующей проекту В.

Кроме того, для сохранности капитала в проекты А и С следует вложить не менее 50% средств, помещаемых в инвестиционный фонд.

В настоящее время проект А позволяет получать 10 % годовых и обеспечивает 1% роста капитала; проект В предполагает рост капитала в 15%; проект С дает 4% годовых и 5%-ный рост капитала.

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

7) Китайская компания с ограниченной ответственностью по производству гусеничных механизмов выпускает пять сходных друг с другом товаров -- А, В, С, D и Е. В нижеследующей таблице представлены расходы ресурсов, необходимых для выпуска единицы каждого товара, а также недельные запасы каждого ресурса и цены продажи единицы каждого продукта.

Ресурсы.	Товар	Недельный запас ресурсов
	А	В	С	D	Е
Сырье, кг Сборка, ч Обжиг, ч Упаковка,ч	6,00 1,00 3 0,50	6,50 0,75 4,50 0,50	6,10 1,25 6 0,50	6,10 1,00 6 0,75	6,40 1,00 4,50 1,00	35000 6000 30000 4000
Цена продажи, ф.ст.	40	42	44	48	52

Известны также издержки, связанные с использованием каждого вида ресурсов:

сырье -- 2,10 ф. ст. за 1 кг;

сборка --. 3,00 ф. ст. за 1 ч;

обжиг -- 1,30 ф. ст. за 1 ч;

упаковка -- 8,00 ф. ст. за 1 ч.

Требуется:

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

8) Нефтяная компания "РТ" для улучшения эксплуатационных качеств и снижения точки замораживания дизельного топлива, которое она производит, добавляет в него определенные химикаты. В каждом бензобаке объемом 1000 л должно содержаться не менее 40 мг химической добавки X, не менее 14 мг химической добавки Y и не менее 18 мг химической добавки Z. Необходимые химические добавки в форме готовых смесей поставляют "РТ" две химические компании А и В.

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

Продукт	Химические добавки, мг/л
	Х	У	Z
А В	4 5	2 1	3 1

Стоимость продукта А -- 1,50 ф. ст. за 1 л, а продукта В -- 3,00 ф. ст. за 1 л.

Требуется: найти ассортиментный набор продуктов А и В, минимизирующий общую стоимость добавленных в топливо химикатов.

9) Администрация компании "Nemesis Company", осуществляя рационализаторскую программу корпорации, приняла решение о слиянии двух своих заводов в Аббатсфилде и Берчвуде.

Предусматривается закрытие завода в Аббатсфилде и за счет этого -- расширение производственных мощностей предприятия в Берчвуде.

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

Квалификация рабочих	Аббатсфилд	Берчвуд
Высокая Низкая	200 300	100 200
Итого	500	300

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

После проведения всесторонних переговоров с привлечением руководителей профсоюзов были выработаны следующие финансовые соглашения:

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

Квалифицированные рабочие - 2000 ф. ст.;

Неквалифицированные рабочие - 1500 ф. ст.

2. Рабочие завода в Аббатсфилде, которые должны будут переехать, получат пособие по переезду в размере 2000 ф. ст.

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

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

S1 -- число квалифицированных рабочих, переведенных на новую работу с завода в Аббатсфилде;

S2 -- число квалифицированных рабочих, переведенных на новую работу с завода в Берчвуде;

Ui -- число неквалифицированных рабочих, переведенных на новую работу с завода в Аббатсфилде;

U2 -- число неквалифицированных рабочих, переведенных на новую работу с завода в Берчвуде.

10) Компания "Bermuda Paint" -- частная промышленная фирма, специализирующаяся на производстве технических лаков. Представленная ниже таблица содержит информацию о ценах продажи и соответствующих издержках производства единицы полировочного и матового лаков.

Лак	Цена продажи 1 галлона, ф.ст	Издержки производства 1 галлона, ф. ст.
Матовый Полировочный	13,0 16,0	9,0 10,0

Для производства 1 галлона матового лака необходимо затратить 6 мин трудозатрат, а для производства одного галлона полировочного лака -- 12 мин. Резерв фонда рабочего времени составляет 400 чел.-ч. в день. Размер ежедневного запаса необходимой химической смеси равен 100 унциям, тогда как ее расход на один галлон матового и полировочного лаков составляет .0,05 и 0,02 унции соответственно. Технологические возможности завода позволяют выпускать не более 3000 галлонов лака в день.

В соответствии с соглашением с основным оптовым покупателем компания должна поставлять ему 5000 галлонов матового лака и 2500 Галлонов полировочного лака за каждую рабочую неделю (состоящую из 5 дней). Кроме того, существует профсоюзное соглашение, в котором оговаривается минимальный объем производства в день, равный 2000 галлонов. Администрации данной компании необходимо определить ежедневные объемы производства каждого вида лаков, которые позволяют получать максимальный общий доход.

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

11) Членов Ассоциации ученых Мидленда недавно уведомили, что их ассоциация получит государственные гранты на проведение исследований в соответствии с четырьмя основными исследовательскими проектами. Исполнительный директор ассоциации должен по каждому проекту назначить научного руководителя. В настоящее время эти обязанности можно возложить на одного из пяти исследователей -- Адаме, Браун, Карр, Дэй и Иване. Время, требуемое для завершения каждого из исследовательских проектов, зависит от опыта и способностей исследователя, которому будет поручено руководство выполнением проекта. Исполнительному директору были представлены оценки времени выполнения проекта каждым из ученых (в днях).

Ученый-исследователь	Проект
	1	2	3	4
Адаме Браун Карр Дай Иване	80 72 96 60 64	120 144 148 108 140	60 48 72 52 60	104 110 120 92 96

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

Требуется: Определить оптимальный вариант назначения научных руководителей проектов и, следовательно, общее число дней, необходимое для завершения четырех проектов. Найти какие-либо другие варианты назначения, которые привели бы к тому же результату. Учитывая, что ученые Браун, Карр и Дэй отдают предпочтение проектам 2 и 3, а ученые Адаме и Иване -- проектам 1 и 4, какой из имеющихся оптимальных вариантов назначения, принятый исполнительным директором, был бы наиболее разумным?

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

Рассмотрим еще один пример, где используется средство поиска решений. Предположим, что фирма имеет 4 фабрики и 5 центров распределения ее товаров. Фабрики фирмы располагаются в Денвере, Бостоне, Новом Орлеане и Далласе с производственными возможностями 200, 150, 225 и 175 единиц продукции ежедневно, соответственно. Центры распределения товаров фирмы располагаются в Лос-Анджелесе, Далласе, Сент-Луисе, Вашингтоне и Атланте с потребностями в 100, 200, 50, 250 и 150 единиц продукции ежедневно, соответственно. Хранение на фабрике единицы продукции, не поставленной в центр распределения, обходится в $0,75 в день, а штраф за просроченную поставку единицы продукции, заказанной потребителем в центре распределения, но там не находящейся, равен $2,5 в день. Стоимость перевозки единицы продукции с фабрик в пункты распределения приведена в таблице "Транспортные расходы":

Таблица "Транспортные расходы"

		1	2	3	4	5
		Лос-Анджелес	Даллас	Сен-Луис	Вашингтон	Атланта
1	Денвер	1.50	2.00	1.75	2.25	2.25
2	Бостон	2.50	2.00	1.75	1.00	1.50
3	Новый Орлеан	2.00	1.50	1.50	1.75	1.75
4	Даллас	2.00	0.50	1.75	1.75	1.75

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

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

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

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

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

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

-- объем перевозок с i-ой фабрики в j-ый центр распределения.

Функция цели -- это суммарные транспортные расходы, т. е. где - стоимость перевозки единицы продукции с i-и фабрики j-й центр распределения. Неизвестные в данной задаче должны удовлетворять следующим ограничениям:

o Объемы перевозок не могут быть отрицательными

o Так как модель сбалансирована, то вся продукция должна быть вывезена с фабрик, а потребности всех центров распределения должны быть полностью удовлетворены

В результате имеем следующую модель:

Минимизировать:

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

где - объем производства на i-й фабрике, bj -- спрос в j-м центре распределения.

Для решения этой задачи с помощью средства поиска решений введем данные, как показано на рис. 5.

В ячейки А1:Е4 введены стоимости перевозок. Ячейки А6:Е9 отведены под значения неизвестных (объемы перевозок). В ячейки G6:G9 введены объемы производства на фабриках, а в ячейки А11:Е11 введена потребность в продукции в пунктах распределения. В ячейку F10 введена целевая функция =СУММПРОИЗВ(А1:Е4;А6:Е9).

Рис. 1. Исходные данные транспортной задачи

В ячейки А10:E10 введены формулы

=СУММ(Аб:А9)

=СУММ(В6:В9)

=СУММ(С6:С9)

=СУММ(D6:D9)

=СУММ(Е6:Е9) определяющие объем продукции, ввозимой в центры распределения.

В ячейки F6:F9 ведены формулы

=СУММ(А6:Е6)

=СУММ(А7:E7)

=СУММ(А8:Е8)

=СУММ(А9:Е9) вычисляющие объем продукции, вывозимой с фабрик.

Теперь выберем команду Сервис, Поиск решения (Tools, Solver) и заполним открывшееся диалоговое окно Поиск решения (Solver), как показано на рис. 6.

Не забудьте в диалоговом окне Параметры поиска решения (Solver Options) установить флажок Линейная модель (Assume Linear Model). После нажатия кнопки Выполнить (Solve) средство поиска решений находит оптимальный план поставок продукции и соответствующие ему транспортные расходы (рис. 3).

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



Рис. 3. Оптимальное решение транспортной задачи

Задания для самостоятельного решения

1) Решить транспортную задачу со следующими условиями:

Пункты отправления	Пункты назначения	Запасы
	В1	В2	В3	В4
А1	3	4	6	1	460
А2	5	1	2	3	340
А3	4	5	8	1	300
Потребности	350	200	450	100

2) Для строительства трех объектов используется кирпич, изготовляемый на трех заводах. Ежедневно каждый из заводов может изготовлять 100, 150 и 50 усл. ед. кирпича. Ежедневные потребности в кирпиче на каждом из строящихся объектах соответственно равны 75, 80, 60 и 85 усл. ед. Известны также тарифы перевозок 1 усл. ед. кирпича с каждого с заводов к каждому из строящихся объектов:

Составить такой план перевозок кирпича к строящимся объектам, при котором общая стоимость перевозок является минимальной.

3) На трех железнодорожных станциях скопилось 120, 110 и 130 незагруженных вагонов. Эти вагоны необходимо перегнать на железнодорожные станции В1, В2, В3, В4 и В5. На каждой из этих станций потребность в вагонах соответственно равна 80, 60, 70, 100 и 50. Тарифы перевозок задаются матрицей

Составить такой план перегонок вагонов, при котором общая стоимость была минимальной.

4) Компания "Royal Wedgetoun Pottery" получила заказы на три вида выпускаемой ею продукции (бокалы, чашки и вазы), которые необходимо удовлетворить в течение следующей недели. Размеры заказов следующие:

Продукт	Размер заказа, единиц
Бокалы Чашки Вазы	4000 2400 1000

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

Станок	Бокалы	Чашки	Вазы
А В С	1,20 1,40 1,10	1,30 1,30 1,00	1.10 1,50 1,30

Кроме того, известно, что производственные мощности станков В и С на следующую неделю составят 3000 единиц, а станка А -- 2000 единиц.

Требуется, используя транспортную модель, найти план производства для видов продукции и станков, минимизирующий общую стоимость производства. Определить значение минимальной стоимости.

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

5) Компания "Orange Computer" производит только один вид продукции -- матричные печатающие устройства, которые в настоящее время являются дефицитом. Четыре основных покупателя -- это крупные специализированные компьютерные универмаги, расположенные в Аббатстауне, Бесвиче, Карлике и Денстоуне, уже подали заявки, общий размер которых превышает общие производственные мощности трех заводов компании в Рексфорде, Сидоне и Тристроне. Компания должна принять решение о том, как распределить производственные мощности, чтобы получить максимальную прибыль. После того, как каждый принтер тщательно упакован в мягкую упаковку, предохраняющую его от каких-либо повреждений, его помещают в отдельную коробку. В нижеследующей таблице приведены значения стоимости транспортировки одной единицы от каждого завода-производителя в каждый специализированный универмаг (ф. ст.):

	"Аббатстаун"	"Бесвич"	"Карлик"	"Денстоун"
Рсксфорд Сидон Тристрон	22 24 26	24 20 20	22 18 26	30 28 24

Поскольку все четыре специализированных универмага расположены в различных частях страны и, следовательно, стоимость транспортировки продукции между заводами-производителями и универмагами различна, а также ввиду некоторых различий и в издержках производства каждого из четырех заводов, существующая структура цен предусматривает возможность установления различных цен для каждого из четырех универмагов. В настоящее время установлены следующие цены за единицу продукции: 230 ф. ст. в Аббатстауне, 235 ф. ст. в Бесвиче, 225 ф. ст. в Карлике и 240 ф. ст. в Денстоуне. Издержки производства на единицу продукции составляют 150 ф. ст. на заводах в Рексфорде и Тристроне и 155 ф. ст. на заводе в Сидоне.

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

Значения спроса в Аббатстауне, Бесвиче, Карлике и Денстоуне равны 850, 640, 380 и 230 единицам соответственно. Производственные мощности позволяют производить на заводе в Рексфорде 625, в Сидоне -- 825, а в Тристроне -- 450 принтеров. Используя алгоритм решения транспортной задачи, определить оптимальное распределение перевозок. Определить соответствующую оптимальному решению прибыль.

Варианты для индивидуальной работы

Вариант	Номер задачи линейного программирования	Номер транспортной задачи
Вариант1	1	1
Вариант2	2	2
Вариант3	3	3
Вариант4	4	4
Вариант5	5	5
Вариант6	6	1
Вариант7	7	2
Вариант8	8	3
Вариант9	9	4
Вариант10	10	5
Вариант11	2	1
Вариант12	4	3
Вариант13	6	5
Вариант14	8	2
Вариант15	11	4

Размещено на Allbest.ur

...