4.10 Лабораторная работа Решение задач оптимизации

Средство «Подбор параметра», которое мы рассматривали ранее – это частный случай более мощного средства MS Excel – надстройки «Поиск решений». Она предназначена главным образом для решения задач оптимизации, например, определение условий максимальной прибыли при производстве продукции или составление плана перевозок с минимальными затратами.

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

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

Имеется n пунктов поставки и m пунктов потребления некоторого продукта. Для каждого пункта поставки имеется запас A_n продукта, а для каждого пункта потребления имеется потребность B_m продукта. Известна стоимость перeвозки c_nm единицы продукта из каждого пункта поставки в каждый пункт потребления (тариф). Требуется составить план перевозок с минимальной стоимостью.

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

Для объяснения решения таких задач конкретизируем исходные данные. Это удобнее сделать в табличной форме (эта таблицу не надо набирать в Excel):

Поставщики	Тарифы			Запасы
	Потребитель В1	Потребитель В2	Потребитель В3
Поставщик А1	5	4	4	15
Поставщик А2	2	2	3	25
Поставщик А3	3	4	5	10
Поставщик А4	5	3	3	15
Потребность	10	20	35	65

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

Для понимания сути исходных данных ответьте на вопросы:

1. Сколько имеется пунктов поставки и пунктов потребления?

2. Какова стоимость перевозки единицы продукта, например, от поставщика А₃ потребителю В₁?

3. Какова стоимость перевозки всего необходимого продукта, например, от поставщика А₃ потребителю В₁?

4. Что означает число 65 в выделенной ячейке таблице?

1 этап решения. Чтобы решить задачу ЭТ, необходимо ввести таблицу, отражающую условие задачи (эту таблицу введите на лист Excel):

	A	B	C	D	E	F
1	Поставщики	План перевозок			Реализовано	Запасы
2		Потребитель В1	Потребитель В1	Потребитель В1
3	Поставщик А1					15
4	Поставщик А2					25
5	Поставщик А3					10
6	Поставщик А4					15
7	Получено
8	Потребность	10	20	35
9	Целевая функция:

В строке «Получено» для каждого потребителя введите функцию, подсчитывающую сумму по всем поставщикам. Аналогично – в столбец «Реализовано».

В ячейке, предназначенной для целевой функции, введите эту функцию: =(B3*5+B4*2+B5*3+B6*5)+(C3*4+C4*2+C5*4+C6*3)+(D3*4+D4*3+D5*5+D6*3).

2 этап решения. Следующий важный момент – определение ограничений.

• Во-первых, это неотрицательность значений ячеек плана перевозок.

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

• В-третьих, равенство значений строки «Получено» соответствующим значениям строки «Потребность».

3 этап решения. После такой подготовительной работы можно применить надстройку «Поиск решения». Ее вызов осуществляется через меню Сервиз. Если эта надстройка не установлена, можно установить ее через команду Сервис/Надстройки/Поиск решения.

После открытия окна надстройки «Поиск решений» заполните параметры:

• В поле «Установить целевую ячейку» - адрес ячейки с целевой функцией (E9);

• Отметьте параметр «минимальному значению», так как в решаемой задаче необходимо минимизировать целевую функцию;

• В поле «Изменяемые ячейки» введите адреса ячеек планов перевозок (B3:D6), так как именно их значения нам надо определить;

• В поле «Ограничения» с помощью кнопки Добавить введите все определенные на предыдущем этапе ограничения;

• Кнопка «Выполнить» (но не спешите нажимать ОК).

4 этап решения. Задача решена, но на этом не следует останавливаться. В решении такой задачи очень важен этап анализа результатов, так как полученное решение хотя и оптимально, но не единственно. А для реальных ситуаций не всегда возможно реализовать именно оптимальное решение, поэтому важно просмотреть все возможные варианты. Для их поиска предусмотрено создание отчетов трех типов: отчет по результатам, отчет по устойчивости, отчет по пределам – выделите все типы отчетов в окне «Тип отчета». Вот теперь – ОК.

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