Типовые задачи оптимизации и их решение средствами Excel

• в случае перепроизводства — фиктивный пункт распределения. Стоимость перевозок единицы продукции в этот фиктивный пункт полагается равным стоимости складирования, а объёмы перевозок в этот пункт равны объёмам складских излишек продукции на фабриках;
• в случае дефицита — фиктивную фабрику. Стоимость перевозок единицы продукции из фиктивной фабрики полагается равной стоимости штрафов за недопоставку продукции, а объём перевозок из этой фабрики равны объёмам недопоставок продукции в пункты распределения.

Для решения данной задачи постоим её математическую модель. Неизвестными здесь являются объёмы перевозок в пункты распределения. Пусть x_ij — объём перевозок с i-й фабрики в j-й центр распределения, а c_ij — стоимость перевозки единицы продукции с i-й фабрики в j-й центр распределения. Целевой функцией является суммарные транспортные расходы, т. е.

Кроме того, неизвестные  должны удовлетворять следующим  ограничениям:

• неотрицательность объёмов перевозок ( );
• т. к. модель сбалансирована, то вся продукция должна быть вывезена с фабрик, и потребность всех центров распределения должна быть полностью удовлетворена ( , ; , .)[11]

Таким образом, имеем следующую модель:

• минимизировать

;

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

, ,

, ,

где a_i — объём производства на i-ой фабрике, b_j — спрос в j-м центре распределения.

Решить транспортную задачу можно с помощью средства Поиск решения. Для этого нужно выполнить следующую подготовительную работу (рис. 12):

1. Ввести в диапазон B3:F6 стоимости перевозок.
2. Отвести диапазон ячеек B8:F11 под значения неизвестных (объёмов перевозок).
3. Ввести в ячейки диапазона H8:H11 объёмы производства на фабриках.
4. Ввести в ячейки диапазона B13:F13 потребность в продукции в пунктах распределения.
5. В ячейку B16 ввести целевую функцию

=СУММПРОИЗВ(B3:F6;B8:F11)

6. В ячейки диапазона G8:G11 ввести формулы, вычисляющие объёмы производства на фабриках, а в ячейки диапазона B12:F12 объёмы доставляемой продукции в пункты распределения. А именно:

Ячейка	Формула	Ячейка	Формула
G8	=СУММ(B8:F8)	B12	=СУММ(B8:B11)
G9	=СУММ(B9:F9)	C12	=СУММ(C8:C11)
G10	=СУММ(B10:F10)	D12	=СУММ(D8:D11)
G11	=СУММ(B11:F11)	E12	=СУММ(E8:E11)
		F12	=СУММ(F8:F11)

 

Рис 12. Исходный вид таблицы

7. Выбрать последовательно пункты меню Сервис, Поиск решения и заполнить диалоговое окно Поиск решения, как показано на рис 12.

Рис 12. Диалоговое окно Поиск решения с заполненными данными

8. Щёлкнуть на кнопке Выполнить. Средство Поиск решения найдёт оптимальный план поставок продукции и соответствующие ему транспортные расходы (рис. 14).

Рис 14. Результат поиска оптимального решения, минимизирующий транспортные расходы

3.2. Задача  о назначении.

Имеются четыре рабочих  и четыре вида работ. Стоимости c_ij выполнения i-м рабочим j-й работы приведены в табл. 3, где под строкой понимается рабочий, а под столбцом — работа.

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

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

Таблица 3

Задача о  назначениях

Стоимость выполненных  работ
Рабочий 1	1	4	6	3
Рабочий 2	9	10	7	9
Рабочий 3	4	5	11	7
Рабочий 4	8	7	8	5
Виды работ

Для решения данной задачи сначала нужно построить её математическую модель. Обозначим символом x_ij переменную, имеющую только два допустимых значения: 0 и 1 (двоичная переменная). Будем считать, что:

• x_ij = 1, если i-м рабочим выполняется j-я работа;
• x_ij =0, если i-м рабочим не выполняется j-я работа.

Целевая функция:

 — стоимость всех выполненных  работ всеми рабочими.

Ограничения:

• , , — переменная двоичная;
• , — работу может выполнять только один рабочий;
• , — рабочий может выполнять только одну работу.

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

1. В ячейки диапазона F2:D5 вести стоимости работ.
2. Диапазон ячеек F2:I5 отвести под результат решения.
3. В ячейку J1 ввести целевую функцию, вычисляющую суммарную стоимость производимых работ всеми рабочими

=СУММПРОИЗВ (A2:D5; F2:I5)

4. В ячейки диапазонов J2:J5 и F6:I6 ввести формулы, задающие левые части ограничений:

Ячейка	Формула	Ячейка	Формула
J2	=СУММ (F2:I2)	F6	=СУММ (F2:F5)
J3	=СУММ (F3:I3)	G6	=СУММ (G2:G5)
J4	=СУММ (F4:I4)	H6	=СУММ (H2:H5)
J5	=СУММ (F5:I5)	I6	=СУММ (I2:I5)

 

Выбрать команду Сервис, Поиск решения и заполнить окно Поиск решения соответствующими данными.

Исходное состояние  таблицы и окно Поиск решения представлены на рис. 15.

Рис. 15. Исходное состояние таблицы и окно Поиск решения

Щёлкнуть на кнопке Выполнить — средство Поиск решения рассчитывает оптимальный план назначений на работы (рис. 16)[10].

Рис. 16. Результат поиска оптимального плана назначений на работы

 

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

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

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

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

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

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

Сырье	Нормы расхода  сырья			Запас сырья
	А	В	С
Какао	18	15	12	360
Сахар	6	4	8	192
Наполнитель	5	3	3	180
Прибыль	9	10	16

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

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

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

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

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

 

ЗАКЛЮЧЕНИЕ

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

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

 Также были рассмотрены  технологии и алгоритм решения задач. Было детально расписаны команды, которые чаще всего применяются при решении задач оптимизации. Это такие как:

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

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

3. Диспетчер сценариев, помогающий работать с несколькими моделями «что – если».

На основе этих технологий и алгоритмов были решены задачи: о  назначение, транспортную задаче и  задачу о выгодном плане производства.

 

СПИСОК ЛИТЕРАТУРЫ

1. Веденеева, Е.А. Функции и формулы Excel 2007. Библиотека пользователя [текст]/ Е.А. Веденеева. – СПб. : Питер, 2008. – 384с.: ил.
2. Использование Excel для решения задач [текст]/  Г.В. Гутовская, Н.И.Шалинова // Информатика и образование. – 2003. - №3. – С. 15-21
3. Решение задач в Excel[текст]/ Н.Л. Ивинская // Информатика и образование. – 2003. - №6. – С. 62-64
4. Левин, А. Самоучитель работы на компьютере [текст]/ А. Левин. – 3-е изд., испр. и доп. – М.: Ноулидж, 1997. – 40 с.
5. Левин, А. Ш. Excel – это очень просто [текст]/ А.Ш. Левин. – СПб.: Питер, 2006. – 73 с
6. Хелворсон, М. Эффективная работа с Microsoft Office [текст]/ М. Хелворсон. – М.: Янг. – СПб.: Питер, 1999. – 153 с.
7. Уокенбах, Дж. Microsoft Office: Библия пользователя [текст]/ Дж. Уокенба<