Решение задачи в MS Excel.

Модели всех задач на оптимизацию состоят из следующих элементов:

1. Переменные - неизвестные величины, которые нужно найти при решении задачи.

2. Целевая функция - величина, которая зависит от переменных и является целью, ключевым показателем эффективности или оптимальности модели.

3. Ограничения - условия, которым должны удовлетворять переменные.

В качестве переменных х₁ и х₂ будем использовать ячейки E2 и E3 соответственно. Для значения целевой функции будем использовать ячейку E9:

 

Далее выбираем пункт меню Данные/Поиск решения:

 

Перед нами открывается диалоговое окно Поиск решения. В нём указываем, что нам необходимо установить ячейку $E$9 максимальному значению, изменяя ячейки $E$2:$E$3. Далее нажимаем кнопку Добавить для добавления ограничений. И добавляем следующие ограничения:

 

 

ограничения по фонду рабочего времени

 

ограничения по минимальному плану производства

 

количество изделий должно быть целым числом

 

После ввода каждого ограничения нажимаем кнопку Добавить. После ввода последнего ограничения нажимаем кнопку OK. И диалоговое окно Поиск решения принимает следующий вид:

 

Нажимаем кнопку Выполнить. И перед нами открывается диалоговое окно Результаты поиска решения:

 

Выбираем создание отчёта по результатам. Отчеты по устойчивости и пределам не создаются при использовании целочисленных ограничений на переменные. После нажатия кнопки OK в рабочей книге появляется новый лист с названием Отчет по результатам 1 содержащий отчёт по результатам, и получаем следующие результаты:

 

Деталь	Затраты времени на производсво одной детали, ч.	Прибыль от реализации одной детали, ден. ед.	Минимальный план выпуска, штук	Оптимальный план производства, штук
А
В
Фонд рабочего времени, человеко-часов
составляет
задействовано
Максимальная прибыль от реализации, ден. ед.

 

 

1.1.3 Отчёт по результатам.

Целевая ячейка (Максимум)
	Ячейка	Имя	Исходное значение	Результат
	$E$9	Максимальная прибыль от реализации, ден. ед. Оптимальный план производства, штук
Изменяемые ячейки
	Ячейка	Имя	Исходное значение	Результат
	$E$2	А Оптимальный план производства, штук
	$E$3	В Оптимальный план производства, штук
Ограничения
	Ячейка	Имя	Значение	Формула	Статус	Разница
	$C$7	задействовано Прибыль от реализации одной детали, ден. ед.		$C$7<=$C$6	связанное
	$D$2	А Минимальный план выпуска, штук		$D$2<=$E$2	связанное
	$D$3	В Минимальный план выпуска, штук		$D$3<=$E$3	не связан.
	$E$2	А Оптимальный план производства, штук		$E$2=целое	связанное
	$E$3	В Оптимальный план производства, штук		$E$3=целое	связанное

1.1.4

Анализ отчета показывает, что фонд рабочего времени задействован на 100%.

Электронная таблица в режиме формул.

 

 

Электронная таблица в режиме значений.

 

Пример 2. Компания «Атлант» хранит свою продукцию на трех складах (первом, втором и третьем), расположенных в разных частях города. На этих складах хранится продукция в количествах 1000, 3000 и 2500 штук соответственно. Продукцию необходимо доставить четырем оптовым покупателям «Урал», «Купец», «Гелиос» и «Меркурий» с минимальными затратами, заявки которых составляют 1300, 800, 2700 и 1700 штук соответственно. Склады оптовых покупателей также расположены в разных частях города. Стоимости (в рублях) доставки одной штуки продукции со складов компании на склады покупателей показаны в следующей таблице7.

Таблица 7

Стоимость доставки продукции

Склады компании	Оптовые покупатели
«Урал»	«Купец»	«Гелиос»	«Меркурий»
№1
№2
№3

1. Построим математическую модель задачи: определим переменные, целевую функцию и ограничения.

Пусть:

− x₁₁, x₁₂, x₁₃, x₁₄, x₂₁, x₂₂, x₂₃, x₂₄, x₃₁, x₃₂, x₃₃, x₃₄ – количество продукции, перевозимой со складов компании на соответствующие склады покупателей;

− z=50 x₁₁ + 150 x₁₂ + 60 x₁₃ + 75 x₁₄ + 100 x₂₁ + 30 x₂₂ +100 x₂₃ +40 x₂₄+ +70x₃₁+180 x₃₂ + 210 x₃₃ + 120 x₃₄ – целевая функция, общая стоимость доставки грузов покупателям;

− x₁₁ + x₁₂ + x₁₃ + x₁₄=1000,
x₂₁ + x₂₂ +x₂₃ +x₂₄=3000,
x₃₁+x₃₂ + x₃₃ + x₃₄=2500 – ограничения для складов компании;

− x₁₁+ x₂₁ + x₃₁=1300,
x₁₂ + x₂₂ + x₃₂=800,
x₁₃ + x₂₃ + x₃₃=2700,
x₁₄+ x₂₄+ x₃₄=1700 – ограничения для складов покупателей.

2. Имеем сбалансированную транспортную задачу, так как спрос покупателей (1300+800+2700+1700=6500) равен предложению производителей (1000+3000+2500=6500).

3. Запустите табличный процессор MS Excel. Переименуйте Лист 1 в Сбалансированная модель.

4. Составьте табличную модель Excel (рис. 65).

Рис. 65. Сбалансированная модель

5. Последняя таблица не обязательна. Целевую функцию можно было вычислить по формуле:

=СУММПРОИЗВ(В4:Е6;В13:Е15).

6. Выделите целевую ячейку и запустите надстройку Поиск решения (Данные 4 Анализ 4 Поиск решения).

7. В появившемся диалоговом окне Поиск решения укажите адреса целевой ячейки, диапазон изменяемых ячеек и ограничения (рис. 66). Целевую ячейку установите равной минимальному значению.

Рис. 66. Диалоговое окно «Поиск решения»

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

9. В диалоговом окне Поиск решения нажмите кнопку Выполнить.

10. Получаем оптимальное решение задачи (рис. 67).

Рис. 67. Оптимальное решение задачи

11. Скопируйте полученную табличную модель на Лист 2 рабочей книги и переименуйте его в Несбалансированная задача.

12. Решим эту же задачу, немного изменив условие.

13. Пусть на складе №1 хранится не 1000 штук продукции, а 500. В таком случае на трех складах компании хранится 6000 штук продукции, покупатели по-прежнему заказывают 6500 штук. Перед нами транспортная задача с дефицитом.

14. Несбалансированная задача решается аналогично сбалансированной. Изменения коснуться только ограничений. Причем в ограничениях для складов покупателей знак «=» заменяется знаком «≤».

15. После выполнения надстройки Поиск решения (рис. 68) получаем, что покупатель «Гелиос» недополучит 500 ед. продукции, а минимальные транспортные расходы составят 479 000 (рис. 69).

Рис. 68. Поиск решения

 

Рис. 69. Оптимальное решение задачи

16. Покажите работу преподавателю.

 

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

x₁₁ + x₁₂ + …+ x_1n=1,

x₂₁ + x₂₂ +… +x_2n=1,

…

x_n1+x_n2 + … + x_nn=1 – ограничения для работников (каждый работник может выполнять только один вид работ).

x₁₁ + x₂₁ + …+ x_n1=1,

x₁₂ + x₂₂ +… +x_n2=1,

…

x_1n+x_2n + … + x_nn=1 – ограничения для работ (каждый вид работ может быть выполнен только одним работником).

x_ij – это двоичные переменные, которые могут принимать только два значения: 1, если работник i назначается на выполнение работы j и 0, если не назначается.

Решение задачи о назначениях рассмотрим на примере.

Пример 3. В лингвистическом центре работают 4 преподавателя по следующим направлениям: «Английский для начинающих», «Деловой английский», «Подготовка к ЕГЭ» и «Английский для путешествий». Стоимость академического часа работы каждого преподавателя по каждому курсу представлена в таблице 8. Составьте оптимальное распределение нагрузки среди сотрудников таким образом, чтобы все курсы были проведены, каждый преподаватель был занят только на одном виде работ, а затраты на заработную плату были минимальными.

Таблица 8

Стоимость обучения

№ п/п	ФИО преподавателя	Название курса
Английский для начинающих	Деловой английский	Подготовка к ЕГЭ	Английский для путешествий
	Королев Д. А.
	Воробьева А. С.
	Соловьев Н. А.
	Павлова Р. Г.

1. Построим математическую модель задачи: определим переменные, целевую функцию и ограничения.

Пусть:

x₁₁, x₁₂, x₁₃, x₁₄, x₂₁, x₂₂, x₂₃, x₂₄, x₃₁, x₃₂, x₃₃, x₃₄ – двоичные переменные, которые могут принимать два значения: 1, если преподаватель i назначается на чтение курса j и 0, если не назначается.

z=100 x₁₁ + 300 x₁₂ + 110 x₁₃ + 250 x₁₄ + 120 x₂₁ + 180 x₂₂ +100 x₂₃ +150 x₂₄+ +200 x₃₁+200 x₃₂ + 80 x₃₃ + 170 x₃₄ +300 x₄₁+250 x₄₂ + 150 x₄₃ + 230 x₄₄ – целевая функция (общая стоимость работ).

x₁₁ + x₁₂ + x₁₃ + х₁₄=1,
x₂₁ + x₂₂ +x₂₃+ х₂₄=1,
x₃₁ + x₃₂ +x₃₃+ х₃₄=1,
x₄₁ + x₄₂ +x₄₃+ х₄₄=1,
x₁₁ + x₂₁ + x₃₁ + х₄₁=1,
x₂₁ + x₂₂ +x₂₃+ х₂₄=1,
x₁₃ + x₂₃ +x₃₃+ х₄₃=1,

x₁₄ + x₂₄ +x₃₄+ х₄₄=1 – ограничения (каждый преподаватель может быть задействован на чтении только одного курса и каждый курс должен быть проведен).

2. На основе математической модели на рабочем листе Excel создадим табличную модель (рис. 70).

Рис. 70. Задача о назначениях

3. Целевая функция в данном случае вычисляется по формуле =СУММПРОИЗВ(C6:F9;C15:F18).

4. Выделите целевую ячейку и запустите надстройку Поиск решения (Данные 4 Анализ 4 Поиск решения).

5. В появившемся диалоговом окне Поиск решения укажите адреса целевой ячейки, диапазон изменяемых ячеек и ограничения (рис. 71). Целевую ячейку установите равной минимальному значению. В диалоговом окне Параметры поиска решения установите флажки Линейная модель и Автоматическое масштабирование.

6. В диалоговом окне Поиск решения (рис. 71) нажмите кнопку Выполнить.

Рис. 71. Поиск решения

7. Получаем оптимальное решение задачи (рис. 72).

Рис. 72. Оптимальное решение задачи