519

2)Поиск решения линейных задач симплексметодом – для линейных задач.

3)Эволюционный поиск решения – для негладких

задач.

8.Нажмите кнопку Найти решение и выполните одно из указанных ниже действий:

1) Чтобы сохранить значения решения на листе, в диалоговом окне Результаты поиска решения (рис. 2.3.3) выберите вариант Сохранить найденное решение.

2) Чтобы восстановить исходные значения, выберите вариант Восстановить исходные значения.

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

Примечания:

1)Чтобыпрерватьпоискрешения, нажмитеклавишу Esc. Лист Microsoft Excel будет пересчитан с учетом последних найденныхзначенийдляячеекпеременныхрешения.

2)Чтобы создать отчет, основанный на найденном решении, выберите тип отчета в поле Отчеты и нажмите кнопку ОК. Отчет будет помещен на новый лист книги.

41

Если решение не найдено, будут доступны только некоторые отчеты или они вообще не будут доступны.

3) Чтобы сохранить значения ячеек переменных решения в качестве сценария, который можно будет отобразить позже, нажмите кнопку Сохранить сценарий в диа-

логовом окне Результаты поиска решения, а затем вве-

дите имя этого сценария в поле Название сценария.

2.4.Параметры надстройки Поиск решения

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

(рис. 2.4.1).

Рис. 2.4.1. Диалоговое окно Параметры надстройки Поиск решений

Максимальное время – служит для ограничения времени, отпущенного на поиск решения задачи. В этом поле можно ввести время в секундах, не превышающее 32 767

42

(примерно 9 ч); значение 100, используемое по умолчанию, вполне приемлемо для решения большинства простых задач.

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

Точность ограничения – определяет точность вычислений. Чем меньше значение этого параметра, тем выше точность вычислений.

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

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

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

Показывать результаты итераций – приостанавли-

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

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

Сохранить модель – служит для отображения на экране одноименного диалогового окна, в котором можно

43

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

Оценка линейная – выберите этот переключатель для работы с линейной моделью.

Оценка квадратичная – выберите этот переключатель для работы с нелинейной моделью.

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

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

2.5. Анализ отчетов

Отчет о результатах

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

Рис. 2.5.1. Отчет о результатах

44

Первое значение, которое выдает программа, – это значение целевой функции, где:

1.1– ячейка, гдерасполагаетсяформулацелевойфункции;

1.2– наименование целевой функции;

1.3– первоначальное значение целевой функции;

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

2.1– ячейки, где располагаютсяосновные переменные;

2.2– наименование основных переменных;

2.3– первоначальные значенияосновных переменных;

2.4– оптимальные значения основных переменных;

2.5– условиенацелочисленностьосновныхпеременных. Третье – значения системы ограничений, где:

3.1– ячейки, где располагаются формулы системы ог-

раничений;

3.2– наименование ограничений;

3.3– количество использованных ресурсов (значения ограничений);

3.4– условие ограничения;

3.5– состояние использования ресурсов (полностью использован или имеются остатки);

3.6– количество остатка ресурсов (значение дополнительных переменных оптимальной задачи).

Отчет об устойчивости

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

45

отчет содержит данные для градиентов и множителей Лагранжа.

Более подробно рассмотрим отчет об устойчивости на рис. 2.5.2.

Рис. 2.5.2. Отчет об устойчивости

Ячейки переменных:

1.1– ячейки, гдерасполагаютсяосновные переменные;

1.2– наименования основных переменных;

1.3– оптимальные значения основных переменных;

1.4– приведенная стоимость (значения дополнительных переменных двойственной задачи) – характеризует эффективность того или иного варианта плана (выпуска продукта). Если приведенная стоимость равна 0, то соответствующую продукцию производить выгодно, она вошла в оптимальный план. Если приведенная стоимость больше 0, то эта продукция на рассматриваемых условиях не выгодна. Чем больше приведенная стоимость, тем менее эффективна соответствующая продукция.

1.5– коэффициенты эффективности целевой функции;

1.6и 1.7 – границы допустимых изменений значений коэффициентов эффективности целевой функции при условии, что количество оптимальной продукции (план) не изменится.

46

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

2.1– ячейки, где располагаются формулы системы ограничений;

2.2– наименование ограничений;

2.3– количество использованных ресурсов (значения ограничений);

2.4– теневая цена (значения основных переменных двойственной задачи), показывает ценность единицы ресурса. Этот показатель указывает на то, как изменится оптимальное значение целевой функции при изменении запасов ресурсов на единицу;

2.5– запасы ресурсов;

2.6и 2.7 – границы допустимых изменений значений запасов ресурсов, при которых двойственная оценка не изменится (диапазон устойчивости двойственной оценки).

Отчет о пределах

Третий отчет, который выдает программа, – это отчет о пределах. Форма данного отчета представлена на рис. 2.5.3.

Рис. 2.5.3. Отчет о пределах

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

47

2.6. Пример решения задачи линейного программирования

с помощью надстройки Поиск решения

Постановка задачи

Фирма производит два вида продукции – А и В по определенной цене. На их производство требуется четыре вида ресурсов: S1, S2, S3, S4, которые есть в наличии на фирме в определенном количестве. Также имеется информация о том, сколько нужно каждого вида ресурса на производство единицы продукции. Исходные данные представлены в табл. 2.6.1.

					Таблица 2.6.1
			Исходные данные
	Вид	Норма расхода ресурса			Запас
		на ед. продукции, кг
	ресурса				ресурса, кг
		А		В
	S1	0,5		0,4	120
	S2	1,0		2,0	200
	S3	1,7		2,0	240
	S4	0,5		0,4	70
	Цена, руб.	15		25

Найти

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

Моделирование

Пусть х1 – количество выпускаемой продукции А (шт.); х2 – количество выпускаемой продукции В (шт.).

48

Тогда целевая функция Z = 15x1 + 25x2 → max, а система ограничений примет вид

0,5x1 0, 4x2 120;x1 2x2 200;

1,7x1 2x2 240;0,5x1 0, 4x2 70.

Приведем систему ограничений в канонический вид:

0,5x1 0, 4x2 x3 120;

x1 2x2 x4 200;

1,7x1 2x2 x5 240;0,5x1 0, 4x2 x6 70;

х1, х2, х3, х4, х5, х6 ≥ 0,

где х1, х2 – основные переменные; х3, х4, х5, х6 – дополнительные переменные, которые

обозначают остаток ресурсов на складе

Решение задачи

Составим таблицу на листе в MS Excel для решения задачи (рис. 2.6.1).

Рис. 2.6.1. Построение таблицы исходных данных в MS Excel

49

Далее нам надо установить взаимосвязи между ограничениями, неизвестными и целевой функцией. Для этого мы строим дополнительный столбец Использовано, в котором вводим формулу: =СУММПРОИЗВ(Норма; План). Диалоговое окно ввода функции представлено на рис. 2.6.2. Норма – это затраты определенного ресурса на производство единицы продукции А и B, а План – количество продукции, которое мы ищем. В ячейке Выручка вводим формулу =СУММПРОИЗВ(Цена; План). Диалоговое окно ввода функции представлено на рис. 2.6.3. Таким образом, мы заполнили формулами столбец Использовано и ячейку Выручка. Поскольку план – это переменные, от которых зависит количество использованных ресурсов и выручка, то ячейки с формулами напрямую зависят от данных, которые там появятся в результате поиска решений.

Рис. 2.6.2. Диалоговое окно функции СУММПРОИЗВ для ввода ограничений по материалу

50