Пример решения задачи линейного программирования с помощью MS Excel

Хозяйство специализируется в полеводстве на производстве зерна, сахарной свеклы и подсолнечника. В с.-х. предприятии имеются 3200 га пашни, трудовые ресурсы в объеме 7 000 чел.-дней и минеральные удобрения в объеме 15000 ц.д.в. Требуется найти такое сочетание посевных площадей, которое обеспечило бы получение максимума прибыли.

Следует также учесть, что

- площадь посева технических культур (сахарной свеклы и подсолнечника) не должна превышать 25% общей площади пашни;

- хозяйством заключен договор на продажу зерна в объеме 65000 ц.

Для разработки экономико-математической модели необходима подготовка входной информации (табл. 1).

Таблица 1

Показатели	Сельскохозяйственные культуры
	зерновые	сахарная свекла	подсолнечник
Урожайность, ц/га
Цена реализации 1 ц продукции, руб./ц.
Стоимость товарной продукции с 1 га, тыс. руб.	5,59	20,62	6,73
Затраты на 1 га: МДС, тыс. руб.		12,7
труда, чел.-дней.
минеральных удобрений, ц.д.в.
Прибыль с 1 га, руб.	2,89	7,93	3,63

За неизвестные примем площади посева сельскохозяйственных культур по видам:

X 1 - зерновых культур

X 2 - сахарной свеклы

X 3 - подсолнечника

Для построения экономико-математической модели задачи необходимо учесть все условия. В данном случае, по этим условиям можно составить пять ограничений:

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

1) Х1+Х2+Х3<=3200

- сумма площадей посева технических культур не должна превышать площади, которая может быть отведена для этой цели (3200*0,25=800 га). Коэффициентами при неизвестных в этом ограничении характеризуют расход пашни, отведенной под посевы технических культур, на 1 га каждой технической сельскохозяйственной культуры. В данном случае технико-экономические коэффициенты по неизвестным Х2 и Х3 будут равняться единице, а по нетехническим сельскохозяйственным культурам (Х3) - нулю. В правой части записывается максимальная площадь пашни, которая может быть отведена под посевы технических культур.

2) Х2+Х3<=800

- третье и четвертое ограничения гарантируют, что использование трудовых ресурсов и минеральных удобрений не превысит их наличие в хозяйстве. Другими словами, сумма произведений норм затрат ресурсов на 1 га на площади посева соответствующих сельскохозяйственных культур не должна превышать объемов ресурсов, имеющихся в с.-х. предприятии. Коэффициентами при неизвестных в этих ограничениях будут являться нормы расхода ресурсов (в третьем ограничении – трудовых ресурсов, в четвертом – минеральных удобрений) на 1 га площади посева сельскохозяйственных культур. В данном случае технико-экономические коэффициенты взяты из таблицы 1. В правой части записывается наличие этих ресурсов в хозяйстве.

3) 1,5Х1+4,5Х2+1,5Х3<=7000

4) 2Х1+15Х2+2,3Х3<=15000

- пятое ограничение гарантирует производство запланированного объема зерна. В качестве коэффициентов при переменных выступает выход зерна с 1 га площади посева с.-х. культур. При неизвестной Х1 это урожайность зерновых (таблица 1). При переменных Х2 и Х3 этот коэффициент равен нулю. В правой части записывается план производства зерна.

5) 26Х1>=65000

В результате получена система пяти линейных неравенств с тремя неизвестными. Требуется найти такие неотрицательные значения этих неизвестных Х1>=0; Х2>=0; Х3>=0, которые бы удовлетворяли данной системе неравенств и обеспечивали получение максимума прибыли от отрасли растениеводства в целом:

Z max = 2,89Х1+7,93Х2+3,53Х3

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

Поскольку данная задача решается с помощью MS Excel , то и подготовку всей входной информации для построения экономико-математической модели целесообразно осуществлять также с использованием этого табличного процессора (рис 1). Это облегчает не только расчеты технико-экономических коэффициентов и других данных, но и дает в дальнейшем возможность автоматического обновления информации в экономико-математической модели.

Рисунок 1

Вся разработанная информация сводится в развернутую экономико-математическую модель и заносится в рабочий лист MS Excel . (Рис. 2.)

Рисунок 2

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

Рисунок 3

В столбцы А («№»), В («Ограничения»), С («Единицы измерения») и H («Тип ограничений») вводятся соответствующие данные непосредственно в модель (рис.1). Они не используются в расчетах и служат для информативности и облегчения понимания содержания модели. В столбец I («Объем ограничений») вводятся ссылки на ячейки, содержащие соответствующую названию столбца информацию (значения правых частей построенных ранее неравенств).

Для искомых величин переменных Х1 , Х2 , Х3 нами были оставлены пустые ячейки - соответственно D5 , E 5 , F 5 . Изначально пустые ячейки программа MS Excel воспринимает как ячейки, значение которых равно нулю. Столбец G , названный нами «Сумма произведений », предназначен для определения суммы произведений значений искомых неизвестных (ячейки D5 , E 5 , F 5 ) и технико-экономических коэффициентов по соответствующим ограничениям (строки 6-10) и целевой функции (строка 11). Таким образом, в столбце G определяется:

- - количество используемых ресурсов (ячейка G6 – общей площади пашни; G7 – пашни, которая может быть использована под посевы технических культур; G8 – трудовых ресурсов; G9 – минеральных удобрений);

- - количество произведенного зерна (ячейка G10 );

- - величина прибыли (ячейка G11 ).

На рисунке 2 показано, как в ячейке G11 реализуется запись суммы произведений значений переменных (площадей посева с.-х. культур - ячейки D5 , E 5 , F 5 ) на соответствующие прибыли с 1 га их посева(ячейки D11 , E 11 , F 11 )с помощью функции MS Excel «СУММПРОИЗВ ». Так как при написании данной формулы использованы абсолютные адресации на ячейки от D5 до F 5 ,эта формула может быть скопирована в другие ячейки от G 6 до G10 .

Таким образом, построен опорный план (рис. 2) и получено первое допустимое решение. Значения неизвестных Х1 , Х2 , Х3 равны нулю (ячейки D5 , E 5 , F 5 - пустые ячейки), ячейки столбца G «Сумма произведений» по всем ограничениям (строкам 6-10) и целевой строке (строка 11) также имеют нулевые значения.

Экономическая интерпретация первого опорного плана звучит следующим образом: в хозяйстве имеются ресурсы, рассчитаны все технико-экономические коэффициенты, но процесс производства еще не начат; ресурсы не использовались, и, соответственно, прибыли нет.

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

После выбора данной команды появится диалоговое окно (рис. 4).

Рисунок 4

Поскольку в качестве критерия оптимизации нами выбрана максимизация прибыли, в поле Установить целевую ячейку введите ссылку на ячейку, содержащую формулу расчета прибыли. В нашем случае это ячейка $G$11 . Чтобы максимизировать значение конечной ячейки путем изменения значений влияющих ячеек (влияющими, в данном случае это и изменяемые ячейки, являются ячейки, которые предназначены для хранения значений искомых неизвестных), переключатель установите в положение максимальному значению ;

В поле Изменяя ячейки введите ссылки на изменяемые ячейки, разделяя их запятыми; либо, если ячейки находятся рядом, указывая первую и последнюю ячейку, разделяя их двоеточием ($ D $5:$ F $5 ).

В поле Ограничения введите все ограничения, накладываемые на поиск решения. Добавление ограничения рассмотрим на примере добавления первого ограничения по общей площади пашни.

В разделе Ограничения диалогового окна Поиск решения нажмите кнопку Добавить . Появится следующее диалоговое окно (рис. 5)

Рисунок 5

В поле Ссылка на ячейку введите адрес ячейки, на значение которой накладываются ограничения. В нашем случае, это ячейка $ G $6 , где находится формула расчета используемой пашни в текущем плане.

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

В поле Ограничение введите ссылку на ячейку, в которой находится значение наличия площади пашни в хозяйстве, либо ссылка на это значение. В нашем случае, это ячейка $ I $6

В результате диалоговое окно примет следующий вид (рис. 6).

Рисунок 6

Чтобы принять ограничение и приступить к вводу нового, нажмите кнопку Добавить . Аналогично вводятся и другие ограничения. Чтобы вернуться в диалоговое окно Поиск решения , нажмите кнопку OK .

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

Рисунок 7

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

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

Рисунок 8

Для запуска задачи на решение нажмите кнопку Выполнить и выполните одно из следующих действий:

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

Рисунок 9

Для того чтобы прервать поиск решения, нажмите клавишу ESC .

Лист Microsoft Excel будет пересчитан с учетом найденных значений влияющих ячеек. В результате решения и сохранения результатов поиска на листе модель примет следующий вид (табл. 10).

Рисунок 10

В ячейках D5 -F5 получены значения искомых неизвестных (площади посева равны: зерновых -2500 га, сахарной свеклы - 661 га, подсолнечника – 39 га), в ячейках G6 -G9 определены объемы используемых ресурсов (общей площади пашни – 3200 га; площади пашни, которая может быть использована под посевы технических культур – 700 га; трудовых – 6781,9 чел.-дней; минеральных удобрений – 15000 ц.д.в.), в ячейке G10 установлено количество произведенного зерна (65000 ц.). При всех этих значениях величина прибыли достигает 12603,5 тыс. руб. (ячейка G11 ).

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

Рисунок 11

Одной из наиболее часто встречающихся причин невозможности найти оптимальное решение является такая ситуация, когда в результате решения задачи выясняется, что имеются ограничения, которые не выполняются. Сохранив найденное решение на листе, требуется построчно сравнить полученные значения столбцов «Сумма произведений» и «Объем ограничений» и проверить, удовлетворяет ли отношение между ними ограничению, стоящему в столбце «Тип ограничений». Найдя, таким образом, невыполняемые ограничения необходимо найти и ликвидировать причины, обуславливающие невозможность соблюдения данного конкретного условия (это может быть, например, слишком большие или, наоборот, очень маленькие запланированные объемы ограничений и т.п.).

Если ограничений в модели очень много, то визуально достаточно трудно сравнивать и проверять на верность каждую строку. Для облегчения рекомендуется добавить в модель еще один столбец «Проверка», где с помощью функций MS Excel «ЕСЛИ » и «ОКРУГЛ » можно организовать автоматическую проверку (рис. 12).

Рисунок 12

Цель работы: изучение современных программных средств решения задачи линейного программирования; практическое решение задач линейного программирования графическим методом, симплекс-методом и средствами программыMicrosoftExcel; программная реализация симплекс-метода на языке программирования высокого уровня.

1. Теоретическая часть

Для решения задач линейного программирования в программе Microsoft Excel имеется надстройка Поиск решения , обращение к которой производится из меню Сервис .

Если команда Поиск решения отсутствует в меню Сервис , то требуется установить надстройку «Поиск решения». Для этого в меню Сервис выбирается команда Надстройки , которая открывает диалоговое окно, показанное на рис. 1.

Покажем использование надстройки «Поиск решения» на примере решения следующей задачи.

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

Предприятие изготавливает и реализует три вида продукции – P 1 , Р 2 и Р 3 . Для производства продукции используются три вида ресурсов – комплектующие изделия, сырье и материалы. Запасы ресурсов и их расход на изготовление единицы продукции каждого вида приведены в табл. 1.

Таблица 1

Прибыль от реализации единицы продукции каждого вида составляет 240, 210 и 180 денежных единиц для P 1 , Р 2 и Р 3 соответственно.

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

Математическая модель задачи

Обозначим переменными x 1 , x 2 и x 3 искомые объемы производства продукции видов P 1 , Р 2 и Р 2 , а через F – прибыль предприятия. Тогда математическая постановка представленной задачи принимает следующий вид.

Определить значения переменных x 1 , x 2 и x 3 , для которых достигается максимум целевой функции

F = 240 x 1 + 210 х 2 + 180 x 3

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

Целевая функция описывает суммарную прибыль от реализации произведенной продукции всех трех видов. Ограничения (1), (2) и (3) учитывают расход и запасы комплектующих изделий, сырья и материалов соответственно. Поскольку объемы производства продукции не могут быть отрицательными, добавляются условия

x 1 ≥ 0; x 2 ≥ 0; x 3 ≥ 0.

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

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

Шаг 1. Исходные данные задачи записываются на рабочем листе электронной таблицы. Один из вариантов показан на рис. 2.

Замечание. Если известно исходное допустимое базисное решение, то можно несколько ускорить процесс поиска оптимального решения. Для этого начальные значения некоторых или всех переменных могут быть заданы вручную. В данном примере для их хранения используются ячейки $B$2, $C$2 и $D$2. Если допустимое базисное решение не задано, то программа Excel автоматически определяет начальные значения переменных задачи.

Шаг 2. В ячейку E3 вводится формула

СУММПРОИЗВ(В3:D3; $B$2:$D$2)

для вычисления текущего значения целевой функции, которая находит сумму попарных произведений ячеек (В3:D3) с коэффициентами при переменных в выражении целевой функции на ячейки ($B$2:$D$2) с текущими значениями переменных.

Шаг 3. Чтобы задать ограничения решаемой задачи, в ячейки E5, E6 и E7 копируется формула из ячейки E3. После этого в указанных ячейках должны быть получены формулы, представленные в табл. 2.

Таблица 2

	СУММПРОИЗВ(В5:D5; $B$2:$D$2)
	СУММПРОИЗВ(В6:D6; $B$2:$D$2)
	СУММПРОИЗВ(В7:D7; $B$2:$D$2)

Шаг 4. После создания таблицы с исходными данными курсор устанавливается в ячейку E3, содержащую формулу для вычисления целевой функции. Далее в меню Сервис выбирается команда Поиск решения , которая открывает диалоговое окно, приведенное на рис. 3.

В поле Установить целевую ячейку окна «Поиск решения», показанного на рис. 3, должен появиться адрес ячейки с формулой целевой функции (в данном примере это ячейка $E$3).

Затем в этом окне (рис. 3) заполняются следующие поля этого окна:

В поле Равной переключатель вида экстремума целевой функции устанавливается в положение максимальное значение (или минимальное значение при соответствующей постановке задачи);

В поле Изменяя ячейки указывается диапазон ячеек со значениями переменных задачи, выделяемый на рабочем листе электронной таблицы (в примере это ячейки $B$2:$D$2);

В поле Ограничения задаются ограничения исходной задачи. Для этого курсор устанавливается в поле ввода ограничений и нажимается кнопка Добавить . В результате выводится диалоговое окно «Добавление ограничения», показанное на рис. 4.

В этом окне в поле Ссылка на ячейку вводится адрес ячейки с формулой соответствующего ограничения (например, для ограничения (1) это будет ячейка E5), а в поле Ограничение указывается предельное значение, которое может принимать выбранное ограничение (в данном примере правая часть ограничения (1) находится в ячейке G5).

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

Затем выбирается вид отношения, связывающего левую и правую части ограничения, что показано на рис. 5.

После нажатия кнопки Добавить в окне «Добавление ограничения» (или кнопки ОК для ввода последнего ограничения) данное ограничение попадает в список ограничений решаемой задачи. С помощью кнопок Удалить и Изменить можно удалять выделенные в списке ограничения или вносить в них исправления.

Замечание . В окне «Добавление ограничения» можно указать, что все или некоторые переменные должны принимать только целые значения (рис. 5). Это позволяет получать решения задач целочисленного линейного программирования (полностью или частично целочисленных).

Шаг 5. После заполнения всех полей окна «Поиск решения» нажимается кнопка Параметры (рис. 3), которая открывает диалоговое окно «Параметры поиска решения», показанное на рис. 6.

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

Здесь (рис. 6) также можно определить параметры процесса решения: предельное время поиска решения, максимальное количество итераций, точность и т.п. Флажок Показывать результаты итераций позволяет по шагам следить за поиском решения. Флажок Автоматическое масштабирование включается в том случае, когда разброс значений переменных очень велик.

Шаг 6. Задав необходимые параметры в окне «Параметры поиска решения», следует нажать на кнопку Выполнить для поиска решения задачи (рис. 3) в окне «Поиск решения». Если решение найдено, то на экран выводится окно с соответствующим сообщением (рис. 7).

Полученные результаты отображаются на рабочем листе электронной таблицы, как это показано на рис. 8. В частности, значения переменных - в ячейках $B$2:$D$2, значение целевой функции – в ячейке E3.

Таким образом, получено оптимальное решение исходной задачи в виде вектора
, где
,
и
, для которого значение целевой функцииF максимально и составляет F * = 129825.

Результаты решения задачи линейного программирования также можно сохранить в виде отдельных рабочих листов с именами Отчет по результатам , Отчет по устойчивости и Отчет по пределам . Для сохранения результатов в виде отчетов необходимо предварительно в поле Тип отчета выделить требуемые типы отчетов (рис. 7). В этом же окне можно отказаться от полученных решений и восстановить исходные значения переменных.

Отчет по результатам для рассмотренной задачи показан на рис. 9.

В данном отчете представлены оптимальное решение задачи линейного программирования и его расположение в области допустимых решений. В графах Результат выводятся оптимальные значения целевой функции F * и переменных задачи
, а также их значения для исходного базисного решения, с которого начинался поиск оптимального решения (графаИсходное значение ). Состояние ограничений (графа Статус ) характеризует расположение точки
в области допустимых решений. ГрафаРазница показывает разности между значениями левых и правых частей ограничений (невязки). Для связанного ограничения невязка равна нулю, что свидетельствует о расположение точки
на границе области допустимых решений, которая задается этим ограничением. Если ограничение являются не связанным, то оно не влияет на оптимальное решение.

Замечание . В экономической интерпретации связанные ограничения соответствуют дефицитным ресурсам. Для не связанных ограничений графа Разница показывает оставшиеся объемы неиспользованных не дефицитных ресурсов. В рассмотренной задаче ограничения (1) и (3) соответствуют комплектующим изделиям и материалам, которые являются дефицитными ресурсами. Ограничение (2) является не связанным, т.е. не влияет на оптимальный план производства продукции по критерию максимальной прибыли. Это означает, что второй ресурс (сырье) не использован в объеме 292,5 ед.

В отчете по устойчивости (рис. 10) приведены границы устойчивости переменных задачи (графы Допустимое увеличение и Допустимое уменьшение коэффициентов целевой функции), а также границы устойчивости теневых цен (т.е. переменных двойственной задачи), в пределах которых оптимальное решение не изменяется. Большие значения пределов (1Е+30) означают фактическое отсутствие соответствующих границ, т.е. переменная может изменяться до бесконечности.

В графе Нормированная стоимость элемент во второй строке (-150) показывает, на сколько уменьшится значение функции, если в решении переменную x 2 увеличить на единицу. С другой стороны, при допустимом увеличении коэффициента функции при неизвестной x 2 на 150 единиц значение этой переменной не изменится, т.е. неизвестная x 2 будет равна нулю, а если выйти за пределы допустимого увеличения (коэффициент при x 2 увеличить более чем на 150), то неизвестная x 2 в решении будет больше нуля.

В отчете по пределам (рис. 11) показаны нижние и верхние пределы возможного изменения переменных (в пределах области допустимых решений) и соответствующие значения целевой функции (графа Целевой результат ) при этих изменениях. В частности, если x 1 = 0, а x 2 и x 3 остаются без изменений, то F = 2400 + 2100 + 180191,25 = 34425; при x 3 = 0 и неизменных x 1 и x 2 получим F = 240397,5 + 2100 + 1800 = 95400.

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

Если данная надстройка установлена, то Поиск реше­ния запускается из меню Сервис . Если такого пункта нет, следует выполнить команду Сервис → Надстройки... и вы­ставить флажок против надстройки
Поиск решения (рис.2.1).

Команда Сервис → Поиск решения открывает диалоговое окно «Поиск решения» .

В окне Поиск решения имеются следующие поля:

Установить целевую ячейку – служит для указания целевой ячейки, значение которой необходимо максими­зировать, минимизировать или установить равным за­данному числу. Эта ячейка должна содержать формулу .

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

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

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

Ограничения – служит для отображения списка граничных условий поставленной задачи.

Добавить - служит для отображения диалогового окна Добавить ограничение.

Изменить - Служит для отображения диалоговое окна Изменить ограничение.

Удалить - Служит для снятия указанного ограничения.

Выполнить – Служит для запуска поиска решения поставленной задачи.

Закрыть – Служит для выхода из окна диалога без запус­ка поиска решения поставленной задачи.

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

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

Для решения задачи оптимизации выполните следующие действия.

1. В меню Сервис выберите команду Поиск решения.

2. В поле Установить целевую ячейку введите адрес или имя ячейки, в которой находится формула оптимизируемой модели.

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

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

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

4. В поле Изменяя ячейки введите имена или адреса изменяемых ячеек, разделяя их запятыми. Изменяемые ячейки должны быть прямо или косвенно связаны с целевой ячейкой. Допускается установка до 200 изменяемых ячеек.

Чтобы автоматически найти все ячейки, влияющие на формулу модели, нажмите кнопку Предположить.

5. В поле Ограничения введите все ограничения, накладываемые на поиск решения.

6. Нажмите кнопку Выполнить.

Чтобы восстановить исходные данные, установите переключатель в положение

Этап С. Анализ найденного решения задачи оптимизации.

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

Диалоговое окно Результаты поиска решения содержит следующие поля:

Восстановить исходные значения – служит для восста­новления исходных значений влияющих ячеек моде­ли.

Отчеты – служит для указания типа отчета, размещаемого на отдельном листе книги.

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

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

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

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

2.4 Задача о планировании производства

Постановка задачи. Предприятие должно производить изделия n видов: и 1 ,и 2 ,...и п , причем количество каждого выпускаемого изделия не должно превысить спрос β 1 , β 2 ,..., β n и одновременно не должно быть меньше запланированных величин b 1 ,b 2 ,...,b n соответственно. На изготовление изделий идет m видов сырья s l ,s 2 ,...,s m , запасы которых ограничены соответственно величинами γ 1 , γ 2 ,..., γ m . Известно, что на изготовление i -го изделия идет а ij единиц j -го сырья. Прибыль, получаемая от реализации изделий u 1 , ,и 2 ,...и п равна соответственно с 1 ,с 2 ,...,с п. Требуется так спланировать производство изделий, чтобы прибыль была максимальной и при этом выполнялся план на производство каждого изделия, но не превышался спрос на него.

Математическая модель. Обозначим за х 1 ,х 2 ,...х n количества единиц изделий u 1 , ,и 2 ,...и п, выпускаемых предприятием. Прибыль, приносимая планом (целевая функция), будет равна:

z = z(x 1 ,x 2 ,...,x n) = с 1 x 1 + c 2 x 2 + ...+c n x n → max. Ограничения на выполнение плана запишется в виде: х i ≥β i для i = 1,2,...,n Чтобы не превысить спрос, надо ограничить выпуск изделий: x i ≤β i для i = 1,2,...n. И, наконец, ограничения на сырье запишутся в виде системы неравенств:

α 11 x 1 + α 12 x 2 +...+ α 1n x n ≤b 1

α 21 x 1 + α 22 x 2 +...+ α 2n x n ≤b 2

................................................

α m1 x 1 + α m2 x 2 +...+ α mn x n ≤b m

при условии, что х 1 ,х 2 ,...х п неотрицательны.

Пример 2.1:

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

Условие задачи. Предприятие выпускает два вида железобетонных изделий: лестничные марши и балконные плиты. Для производства одного лестничного марша требуется израсходовать 3,5 куб.м. бетона и 1 упаковку арматуры, а для производства плиты - 1 куб.м. бетона и 2 упаковки арматуры. На каждую единицу продукции при­ходится 1 человеко-день трудозатрат. Прибыль от прода­жи 1 лестничного марша составляет 200 руб., а одной плиты - 100 руб. На предприятии работает 150 человек, причем известно, что в день предприятие производит не более 350 куб.м. бетона и завозится не более 240 упаковок арматуры. Требуется составить такой производственный план, чтобы прибыль от производимой продукции была максимальной.

Решение.

1. На листе рабочей книги MS Excel заполните таблицу параметров задачи (рис. 2.2).

2. Создайте модель задачи и заполните ячейки для значений переменных (первоначально ячейки х { и х г заполняются произвольными числовыми значениями, например, значением 10), целевой функции (ячейка содержит формулу) и ограничений (ячейки содержат формулы)
(рис. 2.2)

3. Выполните команду Сервис Поиск решения и установите необходимые значения в полях диалогового окна Поиск решения, добавляя ограничения в окне Добавление ограничений.

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

4. Нажмите на кнопку Выполнить и установите параметры в окне Результаты поиска решения (переключатель Сохранить найденное решение или Восстановить исходные значения и Тип отчета).

Замечание: В случае ошибок в формулах, ограничениях или неверных параметрах модели в данном окне могут появиться следующие сообщения: «Значения целевой ячейки не сходятся», «Поиск не может найти решения» или «Условия линейной модели не выполняются». При этом переключатель следует установить в положение Восстановить исходные значения, проверить данные на листе и процедуру поиска решения проделать заново.

5. В результате в ячейках с переменными задачи по­явятся значения, соответствующие оптимальному плану (80 лестничных маршей и 70 плит перекрытия в день), а в ячейке для целевой функции - значение прибыли (23 000 руб.), соответствующее данному плану (рис. 2.3)

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

Упражнение:

Упр. 2.1. Предприятие выпускает телевизоры, стереосистемы и акустические системы, используя общий склад комплектующих. Запасы шасси на складе составляют 450 шт., кинескопов – 250 шт., динамиков – 800 шт., блоков питания – 450 шт., плат – 600 шт. На каждое изделие расходуется количество комплектующих, указанное в таблице:

Прибыль от производства одного телевизора составляет 90 у.е, одной стереосистемы – 50 и аудиосистемы – 45. Необходимо найти оптимальное соотношение объемов выпуска изделий, при котором прибыль от производства всей продукции будет максимальной.

Линейное программирование является разделом, с которого начала развиваться дисциплина «математическое программирование». Термин «программирование» в названии дисциплины ничего общего с термином «программирование (т.е. составление программ) для ЭВМ» не имеет, так как дисциплина «линейное программирование» возникла еще до того времени, когда ЭВМ стали широко применяться при решении математических, инженерных, экономических и других задач. Термин «линейное программирование» возник в результате неточного перевода английского «linear programming». Одно из значений слова «programming» - составление планов, планирование. Следовательно, правильным переводом «linear programming» было бы не «линейное программирование», а «линейное планирование», что более точно отражает содержание дисциплины. Однако, термин линейное программирование, нелинейное программирование и т.д. в нашей литературе стали общепринятыми. Задачи линейного программирования является удобной математической моделью для большого числа экономических задач (планирование производства, расходование материалов, транспортные перевозки и т.д.). Использование метода линейного программирования представляет собой важность и ценность - оптимальный вариант выбирается из достаточно значительного количества альтернативных вариантов. Также все экономические задачи, решаемые с применением линейного программирования, отличаются альтернативностью решения и определенными ограничивающими условиями.В электронных таблицах Excel с помощью функции поиска решения можно вести поиск значения в целевой ячейке, изменения значения переменных. При этом для каждой переменной можно задать ограничения, например верхнюю границу. Перед тем как запустить поиск решения, необходимо четко сформулировать в модели решаемую проблему, т.е. определить условия, выполняемые при оптимизации. Отправленной точкой при поиске оптимального решения является модель вычисления, созданная в рабочем листе. Программе поиска решения при этом необходимы следующие данные. 1. Целевая ячейка - это ячейка в модели вычисления, значения в которой должно быть максимизировано, минимизировано или же равняться определенному указанному значению. Она должна содержать формулу, которая прямо или косвенно ссылается на изменяемые ячейки, или же самой быть изменяемой. 2. Значения в изменяемых ячейках будут последовательно (методом итераций) изменяться до тех пор, пока не будет получено нужное значение в целевой ячейке. Эти ячейки, следовательно, прямо или косвенно должны влиять на значение целевой ячейки. 3. Вы можете задать как для целевой, так и для изменяемых ячеек, ограничения и граничные условия. Можно задать также ограничения для других ячеек. Прямо или косвенно присутствующих в модели. Программа предоставляет возможность задать специальные параметры, определяющие процесс поиска решения. После задания всех необходимых параметров можно запустить поиск решения. Функция поиска решения создаст по итогам своей работы три отчета, которые можно пометить в рабочую книгу.Ограничения - это условия, которые должны быть выполнены аппаратом поиска решения при оптимизации модели.

Изучение литературы показало, что:

1. Линейное программирование - это один из первых и наиболее подробно изученных разделов математического программирования. Именно линейное программирование явилось тем разделом, с которого начала развиваться сама дисциплина «математическое программирование».

Линейное программирование представляет собой наиболее часто используемый метод оптимизации. К числу задач линейного программирования можно отнести задачи:

• · рационального использования сырья и материалов; задачи оптимизации раскроя;
• · оптимизации производственной программы предприятий;
• · оптимального размещения и концентрации производства;
• · составления оптимального плана перевозок, работы транспорта;
• · управления производственными запасами;
• · и многие другие, принадлежащие сфере оптимального планирования.
• 2. Графический метод довольно прост и нагляден для решения задач линейного программирования с двумя переменными. Он основан на геометрическом представлении допустимых решений и ЦФ задачи.

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

Решение задач линейного программирования в MS Excel

Инструментом для решений задач оптимизации в MS Excel служит надстройка «Поиск решения». Процедура поис­ка решения позволяет найти оптимальное значение фор­мулы, содержащейся в ячейке, которая называется целе­вой. Эта процедура работает с группой ячеек, прямо или косвенно связанных с формулой в целевой ячейке. Чтобы получить по формуле, содержащейся в целевой ячейке, заданный результат, процедура изменяет значения во вли­яющих ячейках.

Если данная надстройка установлена, то «Поиск реше­ния»запускается из меню «Сервис». Если такого пункта нет, следует выполнить команду «Сервис - Надстройки...» и вы­ставить флажок против надстройки «Поиск решения».

Решение задачи оптимизации состоит из трёх этапов.

A. Создание модели задачи оптимизации.

B. Поиск решения задачи оптимизации.

C. Анализ найденного решения задачи оптимизации.

Рассмотрим подробнее эти этапы.

Этап А.

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

Этап В.

Команда «Сервис - Поиск решения» открывает диалоговое окно «Поиск решения», в котором, в свою очередь, имеются следующие поля:

«Установить целевую ячейку» - служит для указания целе­вой ячейки, значение которой необходимо максими­зировать, минимизировать или установить равным за­данному числу. Эта ячейка должна содержать форму­лу.

«Равной» - служит для выбора варианта оптимизации зна­чения целевой ячейки (максимизация, минимизация или подбор заданного числа). Чтобы установить чис­ло, введите его в поле.

«Изменяя ячейки» - служит для указания ячеек, значения которых изменяются в процессе поиска решения до тех пор, пока не будут выполнены наложенные огра­ничения и условие оптимизации значения ячейки, указанной в поле «Установить целевую ячейку».

«Предположить» - используется для автоматического поиска ячеек, влияющих на формулу, ссылка на которую дана в поле «Установить целевую ячейку». Результат поиска отображается в поле «Изменяя ячейки».

«Ограничения» - служит для отображения списка гранич­ных условий поставленной задачи.

«Добавить» - служит для отображения диалогового окна «Добавить ограничение».

«Изменить» - служит для отображения диалоговое окна «Изменить ограничение».

«Удалить» – служит для снятия указанного ограничения.

«Выполнить» – служит для запуска поиска решения по­ставленной задачи.

«Закрыть» - служит для выхода из окна диалога без запус­ка поиска решения поставленной задачи. При этом сохраняются установки сделанные в окнах диалога, появлявшихся после нажатий на кнопки «Парамет­ры, Добавить, Изменить или Удалить».

«Параметры» - служит для отображения диалогового окна «Параметры поиска решения», в котором можно загрузить или сохранить оптимизируемую модель и ука­зать предусмотренные варианты поиска решения.

«Восстановить» - служит для очистки полей окна диалога и восстановления значений параметров поиска ре­шения, используемых по умолчанию.

Для решения задачи оптимизации выполните следую­щие действия.

1. В меню «Сервис» выберите команду «Поиск решения».

2. В поле «Установить целевую ячейку» введите адрес или имя ячейки, в которой находится формула оптимизируемой модели.

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

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

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

4. В поле «Изменяя ячейки» введите имена или адреса изменяемых ячеек, разделяя их запятыми. Изменяемые ячейки должны быть прямо или косвенно связаны с целевой ячейкой. Допускается установка до 200 изменяемых ячеек.

Чтобы автоматически найти все ячейки, влияющие на формулу модели, нажмите кнопку «Предположить».

5. В поле «Ограничения» введите все ограничения, накладываемые на поиск решения.

6. Нажмите кнопку «Выполнить».

Чтобы восстановить исходные данные, установите пере­ключатель в положение «Восстановить исходные значения».

Этап С.

Для вывода итогового сообщения о результате решения используется диалоговое окно «Результаты поиска реше­ния».

Диалоговое окно «Результаты поиска решения» содер­жит следующие поля:

«Восстановить исходные значения» - служит для восста­новления исходных значений влияющих ячеек моде­ли.

«Отчеты» - служит для указания типа отчета, размещаемо­го на отдельном листе книги.

«Результаты» - используется для создания отчета, состоя­щего из целевой ячейки и списка влияющих ячеек модели, их исходных и конечных значений, а также формул ограничений и дополнительных сведений о наложенных ограничениях.

«Устойчивость» - используется для создания отчета, содер­жащего сведения о чувствительности решения к ма­лым изменениям в формуле (поле «Установить целе­вую ячейку», диалоговое окно «Поиск решения») или в формулах ограничений.

«Ограничения» - используется для создания отчета, состоя­щего из целевой ячейки и списка влияющих ячеек модели, их значений, а также нижних и верхних границ. Такой отчет не создается для моделей, зна­чения в которых ограничены множеством целых чи­сел. Нижним пределом является наименьшее значе­ние, которое может содержать влияющая ячейка, в то время как значения остальных влияющих ячеек фиксированы и удовлетворяют наложенным ограни­чениям. Соответственно, верхним пределом называ­ется наибольшее значение.

«Сохранить сценарий» - служит для отображения диало­гового окна Сохранение сценария, в котором мож­но сохранить сценарий решения задачи, чтобы ис­пользовать его в дальнейшем с помощью диспетчера сценариев MS Excel.

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

Предприятие должно производить изделия видов: , причем количество каждого выпускаемого изделия не должно превысить спрос и одновременно не должно быть меньше за­планированных величин соответственно. На изготовление изделий идет m видов сырья , за­пасы которых ограничены соответственно величинами Известно, что на изготовление i -ro изделия идет единиц j -го сырья. Прибыль, получаемая от реализации изделий равна соответственно . Требуется так спланировать производство из­делий, чтобы прибыль была максимальной и при этом выполнялся план на производство каждого изделия, но не превышался спрос на него.