Контрольная работа

21

Зависимости для левых частей ограничений. Левые части ограничений задачи (1.1)

представляют собой сумму произведений каждой из ячеек, отведенных для значений переменных задачи (B12:E12), на соответствующую ячейку, отведенную для коэффициентов конкретного ограничения (B7:E7 – 1-е ограничение; B8:E8 – 2-е ограничение и B9:E9 – 3-е ограничение):

=СУММПРОИЗВ($B$12:$E$12;B7:E7)

=СУММПРОИЗВ($B$12:$E$12;B8:E8)

=СУММПРОИЗВ($B$12:$E$12;B9:E9)

На экране в полях F7, F8 и F9 появится 0 (нулевое значение) (рис.2.2). 1. Решение задачи.

Дальнейшие действия производятся в окне «Поиск решения», которое вызывается из меню «Сервис» (рис.2.3):

Сервис /Поиск решения;

в поле Установить целевую ячейку введите $F$12;

из группы Равно выберите переключатель максимальному значению;

Рис. 2.3. Окно Поиск решения задачи (2.1)

в поле Изменяя ячейки введите ячейки с первоначальными значениями переменных путем выделения мышью – $B$12:$E$12;

введите ограничения:

1.нажмите кнопку Добавить (поле Ограничения), после чего появится диалоговое окно Добавление ограничения (рис. 2.4);

2.в поле Ссылка на ячейку введите адрес ячейки, в которой записана левая часть первого ограничения задачи 2.1, $F$7;

3.в поле знака откройте список предлагаемых знаков и выберите =;

4.в поле Ограничение введите адрес ячейки, в которой записана правя часть первого ограничения $H$7;

5.остальные ограничения вводятся аналогично, используя кнопку Добавить окна

Добавление ограничения;

Рис. 2.4. Добавление первого ограничения задачи (2.1)

22

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

Рис. 2.5. Добавление граничных условий задачи (2.1)

подтвердите ввод всех перечисленных выше условий нажатием кнопки OK.

Окно Поиск решения после ввода всех необходимых данных задачи (2.1) представлено на рисунке 2.3.

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

Изменить или Удалить (рис. 2.3);

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

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

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

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

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

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

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

линейной задачи за счет применение симплекс-метода.

23

Подтвердите установленные параметры нажатием кнопки OK;

­задача запускается на решение в окне Поиск решения путем нажатия кнопки

Выполнить;

­после запуска на решение задачи линейного программирования на экране появляется окно Результаты поиска решения с одним из сообщений, представленных на рисунках 2.7, 2.8 и 2.9.

Рис. 2.7. Сообщение об успешном решении задачи

Рис. 2.8. Сообщение при несовместной системе ограничений задачи

Рис. 2.9. Сообщение при неограниченности целевой функции в требуемом направлении

Иногда сообщения, представленные на рисунках 2.8 и 2.9, свидетельствуют не о характере оптимального решения задачи, а о том, что при вводе условий задачи в Excel были допущены ошибки, не позволяющие Excel найти оптимальное решение, которое в действительности существует.

Если при заполнении полей окна Поиск решения были допущены ошибки, не позволяющие Excel применить симплекс-метод для решения задачи или довести ее решение до конца, то после запуска задачи на решение на экран будет выдано соответствующее сообщение с указанием причины, по которой решение не найдено. Иногда слишком малое значение параметра Относительная погрешность не позволяет найти оптимальное решение. Для исправления этой ситуации увеличивайте погрешность поразрядно, например от 0,000001 до 0,00001 и т.д.

В окне Результаты поиска решения представлены названия трех типов отчетов: Результаты, Устойчивость, Пределы. Они необходимы при анализе полученного решения на чувствительность. Для получения же ответа (значений переменных, целевой функции и левых частей ограничений) прямо в экранной форме просто нажмите кнопку OK. После этого в экранной форме появляется оптимальное решение задачи (рис. 2.10).

24

Рис. 2.10. Экранная форма задачи (1.1) после получения решения

3. Анализ оптимального решения на чувствительность в MS Excel

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

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

Рис. 3.1. Типы отчетов Отчет по результатам. Отчет по результатам состоит из трех таблиц (рис. 3.2):

1)таблица 1 содержит информацию о целевой функции;

2)таблица 2 содержит информацию о значениях переменных, полученных в результате решения задачи;

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

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

25

Рис. 3.2. Лист отчета по результатам

Если ресурс используется полностью (то есть ресурс дефицитный), то в графе Статус соответствующее ограничение указывается как «связанное»; при неполном использовании ресурса (то есть ресурс недефицитный) в этой графе указывается «не связан.».

Для граничных условий (строки 24-27 на рис. 3.2) в графе Разница показана разность между значением переменной в найденном оптимальном решении и заданным для нее граничным условием.

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

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

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

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

­результирующие значения переменных;

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

­коэффициенты целевой функции;

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

26

Рис. 3.3. Отчет по устойчивости Таблица 2 (рис. 3.3) содержит информацию, относящуюся к ограничениям:

­величина использованных ресурсов в колонке Результ. значение;

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

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

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

Рис. 3.4. Отчет по пределам

4. Двойственная задача линейного программирования

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

27

Прямая задача

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

L X c1x1 c2 x2 ... cn xn max min ,

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

a11x1			a12 x2			... a1n xn				( , )b1 ,
			a22 x2			... a2n xn				( , )b2 ,
a21x1
							...
a		x	a	m2	x	2	... a	mn	x	n	( , )b ,
	m1 1										m
x	j	0 j 1,..., n .

Двойственная задача

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

F Z b1 z1 b2 z2 ... bm zm min max ,

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

a11z1 a21z2 ... am1 zm ( , )c1 ,

a12 z1 a22 z2 ... am2 zm ( , )c2 ,

...

a1n z1 a2n z2 ... amn zm ( , )cn ,

z 0 i 1,..., m .

i

Рассмотрим задачу линейного программирования (2.1):

L X 130,5x1 20x2 56x3 87,8x4 max;1,8x1 2x2 x3 4x4 756,

6x1 2x2 4x3 x4 450,

4x 1 1,5x2 10,4x3 13x4 89,x j 0; j 1,4.

В сформулированной задаче

неравенство 6x1 2x2 4x3

x4

450

эквивалентно неравенству 6x1 2x2 4x3

x4 450 ,

а равенство

1,8x1 2x2

x3

4x4

756 можно

представить как два

неравенства:

1,8x1 2x2 x3

4x4 756 и 1,8x1 2x2

x3 4x4 756 .

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

представить в виде (4.1):

L X 130,5x1

20x2

56x3

87,8x4 max;

1,8x

2x

x 4x

756,

1

2

3

4

1,8x1 2x2

x3

4x4 756

(4.1).

2x2 4x3

x4

450,

6x1

4x

1,5x

10,4x

13x

89,

1

2

3

4

x

j

0; j 1,4.

Поэтому двойственная задача имеет следующий вид (4.2):

F Z 756z1 756z2 450z3 89z4 min;

1,8z		1,8z		2	6z	3	4z		4	130,5,
	1
2z1 2z2 2z3 1,5z4								20			(4.2)
	z2	4z3 10,4z4 56
z1
								87,8,
4z 1 4z2 x3 13z4
	0; i 1,4.
zi

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

28

становится коэффициентами новой целевой функции. Матрица коэффициентов ограничений транспонируется.

Рис. 4.1. Схема формирования двойственной задачи Ввод зависимостей для двойственной задачи показан на рисунке 4.2.

Рис. 4.2. Ввод зависимостей для двойственной задачи Левая часть ограничений представляет собой произведение матрицы коэффициентов

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

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

29

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

Рис. 4.3. Решение для двойственной задачи Открыв отчет по устойчивости (рис. 4.4), можно увидеть новые двойственные оценки

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

Рис. 4.4. Отчет по устойчивости для двойственной задачи

30

5. Графический способ решения задач линейного программирования

Пример. Некоторое предприятие выпускает две марки элитных часов (n=2), которые имеют условные названия: «Банкир» и «Президент». Для изготовления часов «Банкир» требуется 50 гр. золота и 30 гр. платины, а для изготовления часов «Президент» требуется 40 гр. золота и 50 гр. платины (m=2). Предприятие продает часы «Банкир» по цене $1500 за 1 шт., а часы «Президент» – по цене $2100 за 1 шт. Запасы драгоценных металлов на складе предприятия ограничены следующими значениями: золота – 1,5 кг и платины – 1,8 кг. Требуется определить оптимальную партию часов «Банкир» и «Президент», которую может изготовить предприятие с целью получения максимальной прибыли.

Решение.

Экономико-математическая модель задачи.

Переменные: x1, x2 – количество часов соответственно марки «Банкир» и «Президент».

Целевая функция:

f X 1500x1 2100x2 max .

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

50x1 40x2 1500,

30x1 50x2 1800,

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

На одной диаграмме следует построить 3 графика линейных функций: f1 1500 / 40 50 / 40x1 150 / 4 5 / 4x1,

f2 1800 / 50 30 / 50x1 36 3 / 5x1,

где в качестве зависимой переменной y с соответствующим индексом используется вторая переменная данной задачи. В качестве третьей функции следует использовать целевую линейную функцию (рис. 5.1)

f3 76650 / 2100 1500 / 2100x1 36,5 5 / 7x1,

которая соответствует некоторому значению целевой функции.

Рис. 5.1. Экранные формы в режиме просмотра формул Для построения графиков необходимо воспользоваться мастером диаграмм (Вставка/

Точечная).