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

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

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

2. 1.1 Составление штатного расписания

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

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

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

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

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

Внесем формулу модели в ячейку F12

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

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

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

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

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

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

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

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

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

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

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

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