Линейное программирование – это раздел математики, занимающийся решением таких задач на отыскание наибольших и наименьших значений, для которых методы математического анализа оказываются непригодными. Другими словами термин «линейное программирование» характеризует определение программы (плана) работы конкретного экономического объекта на основе выявления линейных связей между его элементами. Задачей линейного программирования является нахождение оптимального, т. е. наилучшего, плана при заданной системе налагаемых на решение ограничений.
К классу задач линейного программирования относится большое количество разнообразных задач планирования и управления, как, например:
1) нахождение оптимального плана выпуска продукции (оптимальное распределение ресурсов);
2) оптимизация межотраслевых потоков (планирование производства различных видов продукции по отраслям);
3) определение оптимального рациона (оптимизация состава химической смеси);
4) транспортная задача (оптимальное распределение потоков товарных поставок по транспортной сети);
5) задача о размещении производства (планирование с учетом затрат на производство и транспортировку продукции);
6) задача о назначениях (оптимальное распределение различных видов транспортных средств) и др.
В настоящее время одним из перспективных, но недостаточно распространенных способов численного решения задач линейного программирования является использование надстройки «Поиск решения» электронных таблиц Microsoft Excel. В частности, «Поиск решения» предоставляет возможность:
a) использования планов большой размерности (т. е. с большим количеством варьируемых переменных);
b) задания ограничений сложного вида;
c) отыскания оптимального из допустимых решений;
d) генерирования множества различных решений, сохраняемых в дальнейшем в виде сценариев;
e) автоматического создания отчета по решению задачи.
Теоретической основой надстройки «Поиск решения» является симплекс-метод, позволяющий находить оптимальное решение задачи планирования с помощью итерационного процесса перехода к улучшающимся планам. «Поиск решения» является дополнением Excel, т. е. может не входить в стандартный вариант установки электронных таблиц. Для его добавления достаточно воспользоваться командой Файл ® Параметры®Надстройки ®Перейти®Поиск решения ® ОК
В качестве примера рассмотрим решение следующей задачи.
Задача 1.Для диетического питания в ежедневный рацион необходимо включить не менее 33 единиц питательного вещества А, 23 единиц вещества В и 12 единиц вещества С. Для диеты используется 3 вида продуктов. Данные о содержании питательных веществ и стоимости весовой единицы каждого продукта даны в таблице 1.
Таблица 1
А
В
С
Стоимость
Весовая единица продукта I
4 ед.
3 ед.
1 ед.
20 к.
Весовая единица продукта II
3 ед.
2 ед.
1 ед.
20 к.
Весовая единица продукта III
2 ед.
1 ед.
2 ед.
10 к.
Требуется составить наиболее дешёвый рацион, при котором пациент получил бы необходимые количества питательных веществ А, В и С.
Решение. Пусть х1, х2, х3 – количества продуктов I, II, III видов, включаемые в ежедневный рацион (хi³0, i=1, 2, 3). Тогда должно быть:
(1)
При этом линейная функция (стоимость рациона)
f=20х1+20х2+10х3®min. (2)
При решении задачи с помощью надстройки Поиск решения необходимо:
1. Открыть окно Microsoft Excel;
2. сделаем первый столбец А – столбцом заголовка, т.е. заполним ячейки A1¸А4 таблицы обозначениями х1, х2, х3 и min соответственно;
3. активизируйте ячейку В4 и запишите в неё формулу (2);
4. в область ячеек А7¸С9 запишите систему (1);
5. Для решения поставленной задачи На ленте Даные выполните нажатие ЛКМ на Поиск решения…;
6. в появившемся окне в поле «Установить целевую» нажатием ЛКМ выделите ячейку В4; в поле «Изменяя ячейки»выделите область В1¸В3; нажатием ЛКМ установите флажок в поле «минимальному значению».
7. У нас осталось незаполненным поле «Ограничения», поэтому ЛКМ нажмем на копке Добавить;
8. после того, как появилось окно Добавление ограничения активизируйте поле «Ссылка на ячейку» и выполните нажатие ЛКМ на ячейке А7. В следующем поле выберите знак « >= », затем в поле «Ограничения» выполните нажатие ЛКМ на ячейке С7;
9. аналогично описанному в предыдущем пункте добавьте ограничения, записанные в область ячеек А8¸С9;
10. помимо ограничений, введённых нами в электронную таблицу, в задаче есть ещё одно ограничение, которое мы тоже должны внести (хi³0). Поэтому мы должны добавить ещё одно ограничение: $B$1:$B$3>=0.
11. Теперь все ограничения нами учтены и мы можем нажать лкм на ОК, после чего мы снова попадаем в диалоговое окно Поиск решения, где лкм нажимаем на Выполнить.
12. Появляется диалоговое окно Результаты поиска решения, в котором компьютер предлагает по умолчанию сохранить найденное решение. Если вы согласны с полученными результатами, то лкм нажмите на кнопке ОК.
(1)
