Задача линейного программирования

Решение уравнений

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

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

Решение таких задач можно искать методом перебора. Однако в лучшем случае на это уходит много времени.

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

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

Познакомимся с этой процедурой на примере составления штатного расписания.

Пусть известно, что в штате больницы состоит 6 санитарок, 8 медсестер, 10 врачей, 3 заведующих отделениями, главный врач, заведующий аптекой, заведующая хозяйством и заведующий больницей. Общий месячный фонд зарплаты составляет 10 000 грн. Необходимо определить, какими должны быть оклады сотрудников больницы.

Построим модель решения этой задачи. За основу возьмем оклад санитарки, а остальные оклады будем вычислять, исходя из него: во столько-то раз или на столько-то больше. Говоря математическим языком, каждый оклад является линейной функцией от оклада санитарки: Ai*С+В_i, где С - оклад санитарки; А_i и В_i - коэффициенты, которые для каждой должности определяют следующим образом:

• медсестра получает в 1,5 раза больше санитарки (А₂=1,5; В₂=0);
• врач - в 3 раза больше санитарки (В₃=0; А₃=3);
• заведующий отделением - на 30 грн. больше, чем врач (А₄=3; B4=30);
• заведующий аптекой - в 2 раза больше санитарки (А₅=2; В₅=0);
• заведующий хозяйством - на 40 грн. больше медсестры (А₆=1,5; В₆=40);
• главный врач - в 4 раза больше санитарки (А₇=4; В₇=0);
• заведующий больницей - на 20 грн. больше главного врача (А₈=4; В₈=20);

Зная количество человек на каждой должности, нашу модель можно записать как уравнение

N₁*A₁*C+N₂*(A₂*C+B₂)+...+N₈*(A₈*C+B₈) = 10000,

где N₁ - число санитарок, N₂ - число медсестер и т.д.

В этом уравнении нам известны A₁...A₈, B₁...B₈ и N₁... N₈, а С неизвестно.

Анализ уравнения показывает, что задача составления расписания свелась к решению линейного уравнения относительно С. Решим его.

Введите исходные данные в рабочий лист электронной таблицы, как показано ниже.

В столбце D вычислите заработную плату для каждой должности. Например, для ячейки D4 формула расчета имеет вид =B4*$H$8+C4.

В столбце F вычислите заработную плату всех рабочих данной должности. Например, для ячейки F4 формула расчета имеет вид =D4*E4.

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

Определите оклад санитарки так, чтобы расчетный фонд был равен заданному:

• активизируйте команду Подбор параметра из меню Сервис;
• в поле "Установить в ячейке" появившегося окна введите ссылку на ячейку F12, содержащую формулу;
• в поле "Значение" наберите искомый результат 10000;
• в поле "изменяя значение ячейки" введите ссылку на изменяемую ячейку H8 и щелкните на кнопке ОК.

Сохраните таблицу в личном каталоге под именем hospital.xls.

Анализ задачи показывает, что с помощью Excel можно решать линейные уравнения. Конечно, такое уравнение может решить любой школьник. Однако, благодаря этому простому примеру стало, очевидным, что поиск значения параметра формулы, удовлетворяющего ее конкретному значению, - это не что иное, как численное решение уравнений. Другими словами, используя Excel, можно решать любые уравнения с одной переменной.

Контрольное задание

7.1. Найти корень уравнения x²-sinx=0.

Указание
В качестве начального приближения возьмите х=0,5.
Обратите внимание, что уравнение имеет два корня: 0 и 0,87, однако Excel может находить только один.

Задачи оптимизации

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

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

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

Такие задачи в Excel решают с помощью Поиска решения.

Задача линейного программирования

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

Познакомимся с решением этих задач на следующем примере.

7.2.1.1 Составление штатного расписания

Усложним рассмотренную в предыдущей главе задачу. Пусть известно, что для нормальной работы больницы необходимо 5-7 санитарок, 8-10 медсестер, 10 врачей, 3 заведующих отделениями, главный врач, заведующий аптекой, заведующая хозяйством и заведующий больницей. Общий месячный фонд зарплаты должен быть минимален. Необходимо определить, какими должны быть оклады сотрудников больницы, при условии, что оклад санитарки не должен быть меньше прожиточного минимума 80 грн.

В качестве модели решения этой задачи возьмем, как и в первой главе, линейную. Запишем ее так:

N₁*A₁*C+N₂*(A₂*C+B₂)+...+N₈*(A₈*C+B₈) = Минимум.

В этом уравнении нам не известно число санитарок (N1), медсестер (N2), врачей (N3) и оклад санитарки (С).

Используя Поиск решения, найдем их.

Откройте созданный в предыдущей главе файл hospital.xls.

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

В окне Установить целевую ячейку укажите ячейку F12, содержащую модель.

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

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

Окончательно окно Поиска решения будет выглядеть так:

Опишите Параметры поиска, как показано на рис. 7.1.

Щелкните на кнопке ОК, а затем - Выполнить.

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

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

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

7.2.1.2 План выгодного производства

Предположим, что мы решили производить несколько видов конфет. Назовем их условно "A", "B" и "C". Известно, что реализация 10-и килограмм конфет "А" дает прибыль 9 грн., "В" - 10 грн. и "С" - 16 грн.

Рисунок 7. 1 - Описание параметров поиска решения

Рисунок 7. 2 - Решение задачи линейного программирования

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

Нормы расхода сырья на производство 10 кг конфет каждого вида приведены ниже.

Сырье	Нормы расхода сырья	Запас сырья
	А	В	С
Какао
Сахар
Наполнитель
Прибыль

Введите исходные данные и формулы в электронную таблицу, как указано ниже.

В меню Сервис активизируйте команду Поиск решения и опишите его параметры, как указано на рис 7.3.

Не забудьте указать в Параметрах на Линейность модели.

Запустите Поиск решения. Если Вы сделали все верно, то решение будет таким, как на рис 7.4.

Из решения видно, что оптимальный план выпуска предусматривает изготовление 80 кг конфет "В" и 20 кг конфет "С". Конфеты "А" производить не стоит. Полученная Вами прибыль составит 400 грн.

7.2.1.3 Задачи книги Solvsamp.xls

Книга Solvsamp.xls, входящая в состав Excel, в папке Examples\Solver содержит более сложные примеры использования средств процедуры Поиска решения.

Рисунок 7. 3 - Описание параметров поиска решения

Рисунок 7. 4 - План выгодного производства

Листы с примерами расчетов из этой книги можно использовать как образцы решения Ваших задач оптимизации. Чтобы изучить листы с задачами линейного программирования "Перевозка грузов"¹⁾, "График работы" и "Оборотный капитал", откройте книгу, перейдите на нужный лист, затем выполните команду Поиск решения из меню Сервис. Целевые ячейки, влияющие ячейки и ограничения на листах уже заданы.