Решение оптимизационных задач

 

2.1. Решение задачи однопараметрической безусловной оптимизации.

Цель оптимизации – максимизировать прибыль в первом квартале за счёт изменения затрат на рекламу в этом квартале. Последовательность операций в MS Excel для решения задачи следующая:

- вызовите диалоговое окно Сервис®Поиск Решения;

- в открывшемся окне задайте целевую ячейку B15 и изменяемую ячейку В11;

- запустите процесс поиска. Результатом решения должна стать квартальная прибыль, равная 17093 руб., соответствующая затратам на рекламу в первом квартале 15093 руб;

- после ознакомления с результатами закройте диалоговое окно.

2.2. Решение задачи многопараметрической безусловной оптимизации.

Цель оптимизации: распределить расходы на рекламу поквартально таким образом, чтобы годовая прибыль от продажи продукции была максимальна. При этом затраты на рекламу ничем не ограничены. Особенности решения данной задачи по сравнению с задачей п. 2.1 следующие. В диалоговом окне Поиск решения целевой должна быть установлена ячейка F15, а диапазон изменяемых ячеек B11:E11 (выделяется мышью).

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

2.3. Решение задачи многопараметрической оптимизации с учётом ограничения - равенства.

Цель оптимизации: распределить фиксированный годовой бюджет расходов на рекламу поквартально таким образом, чтобы годовая прибыль была максимальна. Годовой бюджет расходов на рекламу требуется израсходовать без остатка. Особенности решения данной задачи по сравнению с задачей п. 2.2 следующие. В диалоговом окне Поиск решения выбирается кнопка Добавить (ограничение). В открывшемся диалоговом окне в левом поле устанавливается ссылка на ячейку F11, в среднем – отношение =, а в правом – ограничение расходов на рекламу 40000.

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

2.4. Решение задачи многопараметрической оптимизации с ограничениями-неравенствами.

Основное отличие цели оптимизации от задачи п. 2.3 – средства, заложенные на рекламу, не требуется израсходовать в полном объёме. При этом в ограничении задачи устанавливается знак <= вместо =. Бюджет расходов установите равным 50000.

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

2.5. Самостоятельно решите рассмотренную задачу с двумя ограничениями. Первое устанавливает минимальные расходы на рекламу 50000, второе – максимальные затраты на рекламу 100000.

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

 

Лабораторная работа № 5. Решение транспортной

Задачи

 

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

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

 

Исходные данные

1. Число поставщиков N и общее количество потребителей M. Для определённости принимается N = 5 и M = 3, что отражается в размерности последующих таблиц

2. Стоимости доставки единицы товара от каждого поставщика до каждого потребителя сведены в матрицу стоимостей перевозок С с элементами , где i = 1..M – номер потребителя; j = 1..N – номер поставщика.

 

Таблица 2.5.1 Таблица стоимостей перевозок
Стоимость перевозки единицы товара от поставщика к потребителю	Поставщики
Потребители	А
Б
В

 

3. Каждый поставщик характеризуется наличием ресурса , где i = 1.. N – номер поставщика.

4. Каждый потребитель характеризуется величиной потребности в ресурсе , где j = 1.. M – номер потребителя

 

Описание решения

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

.	(2.5.1)

Требуется определить такие элементы матрицы перевозок (i = 1..M – номер потребителя; j = 1..N – номер поставщика), чтобы все потребности потребителей были обеспечены, все ресурсы поставщиков были потрачены, а общая стоимость затрат на перевозки W (целевая функция) была минимальной.

 

Таблица 2.5.2 Таблица объёмов перевозок
Объем перевозки товара от поставщика к потребителю	Поставщики
					Потребность
Потребители	А
Б
В
Объём располагаемого ресурса

 

Целевая функция имеет вид

.	(2.5.2)

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

.	(2.5.3)

Для сбалансированной задачи ограничениями при поиске целевой функции будут являться использование всех имеющихся ресурсов каждого поставщика (2.5.4) и обеспечение потребностей каждого покупателя (2.5.5):

для j = 1.. M;	(2.5.4)
для i = 1.. N.	(2.5.5)

Возможны два варианта несбалансированной задачи.

1. Суммарные потребности поставщиков превосходят общие потребности потребителей, т.е.

.	(2.5.6)

Тогда все потребности потребителей должны быть выполнены, а некоторая часть ресурсов поставщиков окажется неизрасходованной, что приведёт к изменению знака в условии (2.5.4) с равенства на неравенство

2. Потребности потребителей превосходят имеющиеся ресурсы поставщиков, т.е.

.	(2.5.7)

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

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

 

Порядок решения задачи

 

Подготовка шаблона для решения задачи

 

По образцу фрагмента рабочего листа MS Excel, изображённого на рис. 2.5.1, введите на новом листе матрицы объёмов и стоимостей перевозок. Транспортная задача пока не решена, поэтому матрица объёмов перевозок пока пуста. В рассчитываемые ячейки введите формулы, приведённые в табл. 2.5.3.

	A	B	C	D	E	F	G	H	I
	Таблица стоимостей перевозок
			Оптовые базы
	Магазины	А
	Б
	В
	Таблица объёмов перевозок
			Оптовые базы
								Всего	Потребность
	Магазины	А
	Б
	В
	Всего
	Мощность
	Целевая функция

 

Рис. 2.5.1. Шаблон MS Excel для решения транспортной задачи

 

Таблица 2.5.3

Формулы Excel для решения транспортной задачи

Яче-йка	Формула	Описание
H11	=CУММ(С11:G11)	Расчёт объёмов перевозок ресурса от всех оптовых баз (поставщиков) в каждый магазин (потребитель)
H12	=CУММ(С12:G12)
H13	=CУММ(С13:G13)

 

Окончание табл. 2.5.3

С14	=СУММ(C11:C13)	Расчёт объёмов перевозок ресурса от каждой оптовой базы (поставщика) всем магазинам (потребителям)
D14	=СУММ(D11:D13)
E14	=СУММ(E11:E13)
F14	=СУММ(F11:F13)
G14	=СУММ(G11:G13)
C17	=СУММПРОИЗВ(C4:G6;C11:G13)	Расчёт значения целевой функции – суммарной стоимости перевозок