ФГОУ ВПО «КУРГАНСКАЯ ГОСУДАРСТВЕННАЯ СЕЛЬСКОХОЗЯЙСТВЕННАЯ АКАДЕМИЯ имени Т.С.Мальцева»
КАФЕДРА ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ И ИНФОРМАТИКИ
М.И. Цисарева
МЕТОДИЧЕСКОЕ РУКОВОДСТВО
по решению оптимизационных задач симплексным методом линейного программирования
в пакете MICROSOFT EXCEL
Лесниково – 2011
ЗАДАЧА
В пакете Microsoft Excel имеется модуль для решения задач линейной оптимизации, позволяющий выполнять поиск решения непосредственно по данным матрицы задачи.
Последовательность решения задачи:
-
Ввод матрицы.
-
Ввод формул расчётов.
-
Выполнение настроек для решения.
-
Решение задачи, анализ решения и исправление ошибок.
Методику работы рассмотрим на следующем примере.
Условие задачи. Для выращивания зерновых культур (пшеницы, ячменя и гороха) выделяется 1200 га пашни, 14000 чел.-ч трудовых ресурсов и 1500 ц минеральных удобрений. Площадь посева пшеницы должна составлять не менее 800 га. Критерий оптимальности – максимум валового производства зерна.
Матрица задачи
|
Ограничения |
Пшеница Х1 |
Ячмень Х2 |
Горох Х3 |
Тип ограничения |
Объём ограничения |
|
1. По площади пашни, га |
1 |
1 |
1 |
<= |
1200 |
|
2. По затратам труда, чел.-ч |
12 |
11 |
18 |
<= |
14000 |
|
3. По удобрениям, ц |
1,4 |
1,2 |
0,9 |
<= |
1500 |
|
4. По посевам пшеницы, га |
1 |
0 |
0 |
>= |
800 |
|
Целевая функция, ц |
20 |
18 |
15 |
|
max |
Ввод матрицы
Для удобства работы с модулем оптимизации матрицу задачи размещают на листе с учётом следующих моментов.
1. Верхние строки листа отводят под область переменных, где последовательно набирают:
1 строка - номера и названия переменных,
2 строка оставляется пустой для последующей записи значений переменных величин,
3 строка – коэффициенты целевой функции.
2. Ниже располагают область ограничений, отделив её от области переменных одной-двумя пустыми строками. Каждое ограничение матрицы располагается одной строкой, причём столбец А отводится под название ограничения, а коэффициенты проставляются в столбцах соответствующих переменных.
3. Тип ограничения и объём ограничения располагают отдельными столбцами, оставив перед ними пустой столбец для записи формул, по которым рассчитывается левая часть ограничений.
Разместится эта матрица на листе Microsoft Excel с учётом изложенных выше требований следующим образом.
Ввод формул расчётов
Формулы должны предусматривать расчёт объёмов ограничений и целевой функции, получаемых в результате решения задачи при разных значениях переменных величин.
Величина объёмов ограничений и целевой функции определяется как сумма произведений значений переменных величин на соответствующие коэффициенты при них в ограничениях и целевой строке. Значения самих переменных рассчитываются на каждом шаге автоматически по методике симплексного метода.
Вводятся формулы в свободный столбец слева от типа ограничения (в нашем примере – столбец Е, обозначенный «Значение по решению»), начиная со строки, в которой размещены коэффициенты целевой функции и заканчивая строкой последнего ограничения. В формулах используется математическая функция СУММПРОИЗВ, в которой первый диапазон ячеек (массив 1) включает значения переменных, а второй (массив 2) – технико-экономические коэффициенты. Для ускорения процесса ввода формул её набирают для ячейки целевой функции, фиксируют адреса массива 1, а затем копируют в остальные ячейки столбца (в нашем примере – в ячейки Е6 – Е8).
В нашем примере исходная формула будет записана в ячейку Е4 следующим образом: =СУММПРОИЗВ($B$2:$D$2;B3:D3). В ячейке для объёма последнего ограничения (Е9) эта формула примет вид: =СУММПРОИЗВ($B$2:$D$2;B9:D9).
В нашем примере это будет выглядеть так:
После этого переходят к этапу решения задачи, выполнив предварительно необходимые настройки.
Выполнение настроек для решения задачи
Начинают этот этап с вывода диалогового окна «Поиск решения» с помощью строки меню: СЕРВИС| ПОИСК РЕШЕНИЯ…
В окне поиска решения делают следующие настройки.
-
Указывают адрес ячейки, в которой будет рассчитываться значение целевой функции (в нашем примере – Е3).
-
Устанавливают критерий отбора целевой функции (максимум / минимум).
-
В строке «Изменяя ячейки» указывают диапазон ячеек, в которых будут размещаться значения переменных величин (в нашем примере – ячейки В2:D2).
Примечание: фиксация адресов ячеек выполняется самой программой.
-
В разделе “Ограничения” нужно установить соответствие между объёмами ограничений по условию задачи и по решению. Для этого выбирается кнопка «Добавить» и в появившемся окне «Добавление ограничения» указываются по последнему ограничению последовательно: «Ссылка на ячейку» - адрес ячейки с объёмом ограничения по решению (Е6), тип ограничения (<=), «Ограничение» - объём ограничения по условию (G6).
Аналогично вводятся условия по всем остальным ограничениям. Для перехода к следующему ограничению выбирается кнопка «Добавить», по окончании - ОК.
Примечание. В том случае, когда несколько подряд расположенных ограничений имеют одинаковый тип, ввод условий можно ускорить, объединяя ячейки, т.е. в окне «Ссылка на ячейку» указать блок ячеек с объёмами ограничений по решению, относящийся ко всем ограничениям одного типа, аналогично в окне «Ограничение» – блок ячеек с объёмами ограничений по условию.
В нашем примере окно «Поиск решения» после выполнения настроек буден выглядеть следующим образом:
-
После этого в окне «Поиск решения» выбирается кнопка «ПАРАМЕТРЫ» и в появившемся окне отмечаются необходимые для решения задачи параметры:
-
Предельное число итераций – 1000
-
Линейная модель
-
Неотрицательные значения
-
В пунктах «Оценки», «Разности», «Метод поиска» отмечается первая строка.
В
нашем примере окно «Параметры поиска
решения» после выполнения настроек
буден выглядеть так: