Просмотр промежуточных результатов «Поиска решения»

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

В диалоговом окне «Поиск решения» нажмите кнопку Параметры.

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

На экране появится диалоговое окно Текущее состояние «Поиска решения», а влияющие ячейки листа изменят свои значения.

Чтобы остановить «Поиск решения» и вывести на экран диалоговое окно Результаты «Поиска решения», нажмите кнопку Стоп.

Чтобы выполнить следующую итерацию и просмотреть ее результаты, нажмите кнопку Продолжить.

Возникающие проблемы и сообщения процедуры «Поиска решения»

При моделировании или отладке моделей возможны следующие ситуации:

1 Оптимальное решение не найдено.

2 «Поиск решения» может остановиться до достижения оптимального решения по следующим причинам.

3 Пользователь прервал процесс поиска.

4 Команда Показывать результаты итераций в диалоговом окне Параметры «Поиска решения» выбрана перед Выполнить.

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

6 Установлен флажок Линейная модель в диалоговом окне Параметры «Поиска решения», в то время как решаемая задача нелинейна.

7 Значение, заданное в поле Установить целевую диалогового окна «Поиск решения», неограниченно увеличивается или уменьшается. Необходимо уменьшить значения полей Максимальное время или Итерации в диалоговом окне Параметры «Поиска решения».

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

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

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

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

Итоговые сообщения процедуры «Поиска решения»

1 Если «Поиск решения» успешно завершен, в диалоговом окне «Результаты поиска решения» выводится одно из следующих сообщений:

Решение найдено. Все ограничения и условия оптимальности выполнены.

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

Поиск свелся к текущему решению. Все ограничения выполнены.

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

2 Если поиск не может найти оптимальное решение, в диалоговом окне «Результаты поиска решения» выводится одно из следующих сообщений:

Поиск не может улучшить текущее решение. Все ограничения выполнены.

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

3 Поиск остановлен (истекло заданное на поиск время).

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

4 Поиск остановлен (достигнуто максимальное число итераций).

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

5 Значения целевой ячейки не сходятся.

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

6 Поиск не может найти подходящего решения.

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

7 Поиск остановлен по требованию пользователя.

Нажата кнопка Стоп в диалоговом окне Текущее состояние «Поиска решения» после прерывания «Поиска решения» в процессе выполнения итераций.

8 Условия для линейной модели не удовлетворяются.

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

9 При поиске решения обнаружено ошибочное значение в целевой ячейке или в ячейке ограничения.

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

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

10 Мало памяти для решения задачи.

Система не смогла выделить память, необходимую для «Поиска решения». Закройте некоторые файлы или приложения и попытайтесь снова выполнить процедуру «Поиска решения».

Практические и лабораторные задания

Задание 1

Найти X1, X2, доставляющие максимум целевой функции F(x)=8*X1+6*X2 при ограничениях 2*X1+4*X2<=700;

X1+5*X2<=800;

3*X1+2*X2<=600;

X1>=0; X2>=0.

Задание 2

Привести к канонической форме задачу линейного программирования:

F(x) = 2*X1+X2-X3

2*X2-X3 5;

X1+X2-X3 -1;

2*X1-X2 -3;

X1 0, X2 0, X3 0.

Задание 3

Оптимизация привлечения подрядчиков для выполнения работ на пяти объектах.

Необходимо составить график производства работ с условием минимизации затрат. При этом каждая фирма может работать только на одном объекте. На одном объекте может работать только одна фирма. Работы проводятся одновременно. Известны расценки и сроки выполнения работ (см. таблицы 12 и 13).

Таблица 13– Стоимость 1 часа работы, тыс. руб.

Объекты	Подрядные фирмы
	1	2	3	4	5
1	3,45	3,24	3,69	4,01	3,11
2	5,25	5,85	5,42	5,47	5,48
3	4,88	4,59	4,75	4,23	4,15
4	7,33	7,68	7,80	7,42	7,12
5	8,58	7,98	7,85	8,05	8,26

Таблица 14– Сроки выполнения работ, час.

Объекты	Подрядные фирмы
	1	2	3	4	5
1	18	20	21	22	24
2	13	18	17	14	15
3	12	10	11	14	15
4	22	16	19	21	14
5	19	11	14	17	17

Задание 4

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

Таблица 15 - Исходные данные

Заводы	Затраты на перевозку от завода x к складу y
Челябинск	10	8	6	5	4
Уфа	6	5	4	3	6
Самара	3	4	5	5	9

Таблица 16 - Исходные данные

Потребности складов, ед.	Казань	Липецк	Воронеж	Курск	Москва
	180	80	200	160	220

Таблица 17 - Максимальные поставки с заводов, ед.

Челябинск	310
Уфа	260
Самара	280

Формирование экономико-математической модели

Целевая функция – сумма транспортных расходов на перевозку товаров до каждого склада. Стоимость перевозки до одного склада определяется как сумма произведений затрат на перевозку до данного склада от каждого поставщика на количество доставленного товара. Критерий – минимизация.

Изменяемые ячейки (неизвестные) – количество товара, доставляемого с определенного завода до определенного склада. Изменяемых ячеек – 15.

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

• количество перевозимого товара – неотрицательная величина;

• потребности каждого склада должны быть удовлетворены;

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

Описание компьютерной информационной технологии получения решения

На рабочий лист Excel вводятся все исходные данные (рисунки 7, 8, 9):

ячейки С5:G7 – изменяемые;

ячейка H28 – целевая;

потребности складов – С11:G11;

максимальные поставки – С14:С16;

в ячейки C8:G8, H5:H7 вводятся формулы для ограничений.

Открывается диалоговое окно ««Поиск решения»», в него вводятся целевая ячейка, критерий оптимизации, интервал изменяемых ячеек, ограничения. Запускается программа. Найденное решение сохраняется.

Рисунок 7 – Ввод исходных данных на рабочий лист

Рисунок 8 – Ввод формул для ограничений

Рисунок 9 – Ввод формул для получения целевой ячейки

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

На рисунке 11 представлено заполненное диалоговое окно «Поиска решения». После запуска кнопки «Выполнить» выйдет диалоговое окно «Результаты поиска решения» (рисунок 12). Нажав кнопку ОК, можно на исходном рабочем листе просмотреть результаты (рисунок 13). На рисунке 14 представлен фрагмент рабочего листа с минимальным значением целевой функции.

Рисунок 10 – Заполнение диалогового окна «Поиска решения»

Рисунок 11 – Диалоговое окно «Результаты поиска решения» сообщит, что решение найдено

Рисунок 12 – Оптимальный план перевозок товара с трех заводов на пять складов

Рисунок 13 – Фрагмент рабочего листа с минимальным значением целевой ячейки

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

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

Задание 5

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

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

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

Период накопления фонда – 2008-2034 гг.;

период отчислений – 2008-2023 гг.;

отчисления ежегодные в течение периода отчислений;

конечная величина фонда – 170,91 млн руб.;

прогноз динамики добычи –в таблице 18;

целевое расходование – 6,33 млн руб. ежегодно;

ставка наращения – 12% годовых;

расходы по обслуживанию – 9%;

налог на доход – 17,5%.

Таблица 18 - Исходные данные по добыче

Год	2008	2009	2010	2011	2012	2013	2014	2015
Добыча, тыс. т	159,7	142,5	128,1	116,0	104,7	94,4	85,8	78,3
Год	2016	2017	2018	2019	2020	2021	2022	2023
Добыча, тыс. т	71,4	64,5	47,2	18,3	17,3	16,4	10,7	3,8

Формирование экономико-математической модели

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

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

P_t+1 = (P_t + V_t) · (1+ i · (1 – q/100)) - R_t, (9)

где P_t+1 – величина фонда на начало следующего года, тыс. руб.; P_t – величина фонда на начало текущего года, тыс. руб.; q – ставка налоговых отчислений с полученного годового дохода, %; R_t – ежегодные отчисления на текущую ликвидацию скважин (целевое использование), тыс. руб.

После прекращения разработки месторождения отчисления в резерв также прекращаются, но средства расходуются не одномоментно, наращение резервов продолжается. Рекуррентная формула (9) приобретает следующий вид:

P_t+1 = P_t + P_t · i · (1 – q/100) - R_t. (10)

Целевая функция представляет собой накопленный ликвидационный фонд после ликвидации всех объектов обустройства месторождения (неиспользованный остаток средств фонда) и, согласно принципу финансовой эквивалентности потоков поступлений в фонд и оттока средств из фонда, он должен равняться нулю:

F(t) = Р_т = 0. (11)

Система ограничений должна содержать требование достаточности накопленных к текущему периоду средств фонда на покрытие текущих ликвидационных расходов:

( P_t + V_t) · (1+ i · (1 – q/100)) ≥ R_t – в период Т₁,

P_t+P_t·i · (1 – q/100) ≥ R_t – в период Т₂, (12)

t = 1,…,T.

Переменной (искомой) величиной является величина отчислений в фонд V_t.

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

Величина ежегодного взноса V_t равна произведению годовой добычи нефти и потонной ставки отчислений:

V_t = Q_t · s, (13)

где Q_t – годовая добыча нефти в текущем периоде, тыс. т;

s – потонная ставка отчислений, руб./т.

Описание компьютерной информационной технологии получения решения

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

Целевая ячейка – это ячейка АЕ15 (рисунок 15).

Изменяемая ячейка D21 – это ячейка, на которую ссылаются рекуррентные формулы (рисунок 14) в строке 2 – вынесена за пределы таблицы.

Ограничения представлены в виде рекуррентных формул в строках 8 и 9.

Рисунок 14 – Формулы расчетной таблицы

Рисунок 15 – Рекуррентные формулы и целевая ячейка расчетной таблицы

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

В диалоговое окно «Поиска решения» вводятся целевая ячейка, изменяемая ячейка, ограничения, «Установить целевую ячейку равной значению 0» (рисунок 16). Полученное после запуска программы оптимальное решение представлено на рисунке 17. Величина потонной ставки отчислений в ликвидационный фонд, при которой накопленные средства фонда достаточны для покрытия ликвидационных расходов, составила 77,0 руб. Критерий оптимальности и условия ограничений соблюдены (рисунок 18).

Рисунок 16 – Диалоговое окно «Поиска решения» с заданными параметрами

Рисунок 17 – Фрагмент рабочего листа с оптимальным значением целевой ячейки

Рисунок 18 – Фрагмент рабочего листа с требуемым нулевым значением целевой ячейки после получения оптимального решения

Задание 6

Управление оборотным капиталом.

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

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

Таблица 18 – Виды депозитов и доходности

	Доход, %	Срок, мес.	Месяцы вложений
1-мес. депозит	1	1	1,2,3,4,5,6
3-мес. депозит	4	3	1,4
6-мес. депозит	9	6	1

Таблица 19 – Таблица для решения

Показатель	1 мес.	2 мес.	3 мес.	4 мес.	5 мес.	6 мес.	7 мес.
Нач. сумма	400000
Погашение вклада
Начисление процентов
1-мес. депозит	+	+	+	+	+	+
3-мес. депозит	+			+
6-мес. депозит	+
Расходы
Кон. сумма
Примечание - Знак «+» обозначает изменяемую ячейку.

Задание 7

Стандартом предусмотрено, что октановое число автомобильного бензина А-76 должно быть не ниже 76, а содержание серы в нем – не более 0,3%. Для изготовления такого бензина на заводе используется смесь из четырех компонентов. Данные о ресурсах смешиваемых компонентов, их себестоимости и их октановом числе, а также о содержании серы приведены в таблице 20.

Таблица 20 – Исходные данные

Характеристика	Компонент автомобильного бензина
	№1	№2	№3	№4
Октановое число	82	86	88	90
Содержание серы, %	0,35	0,35	0,3	0,2
Ресурсы, т	700	600	500	300
Себестоимость, ден.ед./т	40	45	60	90

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

Задание 8

Требуется определить, в каком количестве необходимо выпускать продукцию четырех видов (Прод1, Прод2, Прод3, Прод4) для изготовления которой требуются ресурсы трех видов: трудовые, сырьевые, финансовые. Количество ресурса каждого вида, необходимое для выпуска единицы продукции данного вида, называется нормой расхода. Нормы расхода, наличие располагаемого ресурса, а также прибыль, получаемая от реализации единицы каждого вида продукции, приведены в таблице 21.

Таблица 21 – Исходные данные

Ресурсы	Прод1	Прод2	Прод3	Прод4
Прибыль	60	70	120	130
Трудовые	1	1	1	1
Сырьевые	6	5	4	3
Финансовые	4	6	10	13

Задание 9

Компания производит два основных вида продукции. Первый вид продукции требует 2 единицы сырья А и 2 единицы сырья В и приносит прибыль 2 денежные единицы. Второй вид продукции требует 3 единицы сырья А и 5 единиц сырья В, приносит прибыль компании 4 денежные единицы. Найти оптимальный план производства, если доступно 1200 единиц сырья А и 1600 единиц сырья В.

Задание 10

Нефтеперерабатывающий завод получает четыре полуфабриката: 400 тыс. л. алкилата, 250 тыс.л. крекинг-бензина, 350 тыс.л.бензина прямой перегонки и 100 тыс.л. изопентана. В результате этих четырех компонентов в разных пропорциях образуются три сорта авиационного бензина: бензин А-2: 3:5:2, бензин В-3:1:2:1, бензин С-2:2:1:3. Стоимость 1 тыс.л. указанных сортов бензина характеризуется числами 120 д.е., 100 д.е., 150 д.е.

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

Задание 11

Из двух сортов бензина образуются две смеси –А и В. Смесь А содержит бензина 60% 1-го сорта и 40% 2-го сорта; смесь В-80% 1-го сорта и 20% 2-го сорта. Цена 1 кг смеси А -10 д.е., а смеси В – 12 д.е. Составьте план образования смесей, при котором будет получен максимальный доход, если в наличии имеется бензина 50 т. 1-го сорта и 30 т. 2-го сорта.

Задание 12

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

Таблица 22 - Относительные уровни издержек на предприятиях

Предприятия	1	2	3	4	5	6
Издержки	0,4	0,5	0,2	0,8	0,6	0,3

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

1-й вид ресурсов 4*X1+X4=16

2-й вид ресурсов 2*X2+X5=10

3-й вид ресурсов x3+2*X4+6*X5=76

4-й вид ресурсов 4*X1+3*X2+X6=24

(

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