Лабораторная № 5

Цель занятия: Компьютер с помощью программного обеспечения реализует алгоритмы поиска оптимального решения, которые преобразуют исходные данные в искомый результат. Таким программным обеспечением, выполняющим поиск оптимальных решений, является Excel. Поиску оптимальных решений с помощью Excel посвящена эта лабораторная работа.

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

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

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

Пусть требуется определить, в каком количестве надо выпускать продукцию четырёх типов: Стол, Табурет, Шкаф, Полка, для изготовления которых требуются ресурсы трёх видов: трудовые, сырьё, финансы с тем, чтобы получить максимальную прибыль.

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

Табл1.

Ресурс	табурет	полка	стол	шкаф	знак	наличие
прибыль	60	70	120	130	max	-
трудовые	1	1	1	1	<=	16
Сырьё	6	5	4	3	<=	110
финансы	4	6	10	13	<=	100

Составление математической модели.

Математическая модель должна состоять из трёх составляющих:

целевой функции (ЦФ), ограничений (ОГР) и граничных условий (ГРУ)

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

• Максимизация

• Минимизация

• Назначение заданного значения

ОГР – ограничения устанавливают зависимости между переменными

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

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

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

В этом ограничении левая часть равна величине требуемого сырья, а правая показывает количество имеющегося в наличии сырья.

Аналогично можно составить ограничения для остальных ресурсов (трудовые, финансы).

Составим зависимость для целевой функции (ЦФ). Критерий оптимизации в нашей задаче – получение максимальной прибыли. Выпуск одного табурета приносит 60 единиц прибыли, тогда выпуск всех табуретов будет приносить прибыли. С учётом того, что для других видов продукции зависимости аналогичны, общая прибыль от выпускаемой продукции будет иметь вид:

Нужно ответить на вопрос, при каких значениях функция будет принимать max значение.

Математическая модель задачи будет иметь вид:

(1)

Основные положения симплекс – метода.

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

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

В геометрии есть такое понятие « симплекс». Симплексом тела в k-мерном пространстве называют совокупность k+1 его вершин. На плоскости - это три вершины треугольника. С учётом этого понятия аналитический метод решения задачи линейного программирования называют симплекс – методом.

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

На первом шаге вводим новые переменные y_i и осуществляем переход от системы неравенств к системе уравнений. Получаем систему:

(2)

y_i- равны величине неиспользованного ресурса

Систему переписываем в следующем виде:

(3)

Эту же систему можно представить в виде таблицы, приведённой ниже:

Табл.2

	А	В	С	D	E	F
1	Величина	Своб.член	Х1	Х2	Х3	Х4
2	F	0	-60	-70	-120	-130
3	Y1	16	1	1	1	1
4	Y2	110	6	5	4	3
5	Y3	100	4	6	10	13

Таблица называется симплекс - таблицей и является основной формой решения задачи линейного программирования. В этой таблице все переменные делятся на свободные и базисные. Свободные переменные находятся в ячейках С1:F1, базисные – в ячейках A3:A5.

Если переменная свободная, то её значение равно 0. В приведённой выше таблице все основные переменные свободные, следовательно

Значения базисных переменных :

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

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

Признак1.(определяет наличие допустимого решения)

Решение является допустимым, если в столбце свободных членов (B3:B5) все величины неотрицательные.

Признак2. (определяет наличие оптимального решения)

1. Целевая функция имеет минимальное значение в том случае, когда все элементы в строке целевой функции (C2:F2 в нашей задаче) будут отрицательными.

2. Целевая функция имеет максимальное значение в том случае, когда все элементы в строке целевой функции (C2:F2 в нашей задаче ) будут положительными.

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

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

Решение задачи с помощью Excel

1. Запустите Excel.

2. П одготовьте таблицу для ввода условий задачи по образцу:

3. Введите исходные числовые данные из табл1 в таблицу:

4. Введём зависимость для целевой функции из математической модели (1):

   • Установите курсор в ячейку F6.

   • Вызвать Мастер функций

   • Курсор в окно Категория на категорию Математические

   • Курсор в окно Функции на Суммпроиз.

   • ОК

Н а экране: диалоговое окно:

• В массив 1 ввести B$3:E$3

• В массив 2 ввести B6:E6

• ОК

5. Введём зависимости для левых частей ограничений:

• Курсор в F6

• Копировать в буфер

• Курсор в F9

• Вставить из буфера

• Скопировать F9 в F10:F11

Д олжно получиться следующее:

6. Запишите таблицу в свою папку под именем Задача1. Теперь можно приступить к непосредственному решению задачи.

7. Выбрать из меню Сервис, Надстройка и подключить Поиск решения

8. Выбрать из меню Сервис, Поиск решения

Н а экране : диалоговое окно Поиск решения:

9. Назначьте целевую функцию. Для этого нужно установить курсор в окно Установить целевую функцию и ввести адрес $F$6

10. Введите направление целевой функции: Максимальному значению

11. Введите адреса искомых переменных:

• Курсор в поле Изменяя ячейки

• Ввести адреса $B$3:$E$3

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

• Д обавить. На экране появится диалоговое окно Добавление ограничения.

Используя это окно введите граничные условия на переменные ( ): В3>=B4, C3>=C4, D3>=D4,E3>=E4:

• В окне Ссылка на ячейку ввести В3

• Курсор на стрелку и на экране: знаки для ввода в ограничения

• Курсор на знак >=

• Курсор в правое окно

• Ввести В4

• Добавить

• Аналогично ввести граничные условия для остальных переменных

Аналогично ввести ограничения:

F9<=H9, F10<=H10, F11<=H11

• После ввода последнего ограничения вместо Добавить ввести ОК

На экране: диалоговое окно Поиск решения с введёнными условиями

На этом ввод условий задачи заканчивается. На очереди следующий шаг – решение задачи.

13. В ыбрать Параметры. На экране : диалоговое окно Параметры поиска решения:

С помощью команд, находящихся в этом диалоговом окне можно вводить условия для решения задач оптимизации всех классов.

Максимальное время. Служит для назначения времени в секундах, выделяемого на поиск решения задачи. В поле можно ввести время не превышающее 9 часов. Значение 100 используется по умолчанию.

Предельное число итераций. Служит для назначения числа итераций. Используется по умолчанию 100.

14. Установите флажок Линейная модель, что обеспечит применение симплекс – метода, ОК.

На экране должно появиться знакомое окно Поиск решения

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

1 6. Запишите результат в свою папку под именем Симплекс.

Из последней таблицы видно, что в оптимальном решении

Табурет = В3 =10

Полка = С3 = 0

Стол = D3 = 6

Шкаф = Е3 = 0

При этом максимальная прибыль будет составлять F6 = 1320, а количество использованных ресурсов равно:

Трудовых = F9=16

Сырья = F10=84

Финансов = F11=100

Трудовые ресурсы и финансы использованы полностью.