Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:

CKT_l.r.03_Optimizacija / Excel и задачи линейного программирования

.pdf
Скачиваний:
77
Добавлен:
29.02.2016
Размер:
623.95 Кб
Скачать

Теоретическая справка

шения отдельных типов задач линей-

 

зационных задач является надстрой-

 

ного программирования. Как прави-

 

ка «Поиск решения» [2–4]; проиллю-

разнообразных экономиче-

ло, специальные методы проще уни-

 

стрировать, как относительно легко

ских моделях планирования

версальных, но применимы не для

 

такие задачи могут быть решены даже

Впроизводства в качестве оп-

всех задач. Такими являются методы

 

пользователем, не владеющим глубо-

тимального принимается план, обес-

решения транспортной задачи, среди

 

кими знаниями линейного програм-

печивающий заданный производст-

которых можно отметить распредели-

 

мирования. Подчеркнем, что в надст-

венный результат при минимальных

тельный метод и его модификации,

 

ройке «Поиск решения» реализован

затратах или максимальный произ-

метод разрешающих слагаемых

 

универсальный метод решения задач

водственный эффект при заданном

А.Л. Лурье, метод дифференциальных

 

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

объеме ресурсов. Решением подобных

рент А.Л. Брудно, венгерский метод.

 

симплексный метод.

 

 

 

 

задач занимается математическое про-

К особой группе методов линейного

 

В качестве примера взята задача оп-

граммирование, наиболее изученным

программирования относятся прибли-

 

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

разделом которого является линейное

женные методы, отличающиеся от ос-

 

венного плана предприятия.

 

программирование [1]. Методы, кото-

тальных тем, что они не гарантируют

 

Условие задачи

 

 

 

рые используются в нем? можно раз-

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

 

 

 

 

делить на две группы.

хотя, как правило, дают довольно хо-

 

Фирма производит изделие трех мо-

К первой группе относятся универ-

рошее приближение к оптимальному.

 

дификаций (I, II, III). Затраты, свя-

сальные методы, с помощью которых

Алгоритмы приближенных методов от-

 

занные с выполнением каждой опера-

можно решить любую задачу ли-

носительно просты и легко реализуют-

 

ции в процессе изготовления одного

нейного программирования. Из уни-

ся для расчетов на компьютере. К этой

 

изделия, приводятся в таблице.

 

версальных методов наибольшее рас-

группе принадлежат метод аппрокси-

 

Таблица

 

 

 

 

пространение получил симплексный

мации Фогеля, индексный метод и др.

 

 

 

 

 

 

 

 

 

 

 

метод, предложенный Дж. Данцигом.

Следует отметить, что в этой статье

 

Операция

Затраты, грн.

 

I

II

 

III

В эту группу входит также метод раз-

авторы не ставили целью излагать

 

 

 

 

Изготовление комплектующих

20

10

 

10

решающих множителей академика

курс линейного программирования с

 

 

 

 

 

 

 

 

 

Сборка изделия

30

20

 

10

Л.В. Канторовича. Среди методов ре-

той или иной степенью полноты. Ос-

 

 

 

Тестирование и упаковка

20

30

 

20

шения задач целочисленного линей-

новная цель — на конкретном приме-

 

 

 

 

 

 

 

 

ного программирования можно отме-

ре показать возможности пакета Excel

 

Максимальные недельные затраты

тить метод Гомори.

для решения задач оптимизации; про-

 

фирмы, связанные с выполнением

Ко второй группе относятся специ-

демонстрировать, каким эффектив-

 

работ по изготовлению комплектую-

альные методы, применяемые для ре-

ным инструментом решения оптими-

 

щих, по сборке изделий, по тестиро-

 

 

 

ванию и упаковке изделий, составля-

 

 

 

ют 3600 грн., 2400 грн., 1800 грн. со-

 

 

 

ответственно.

 

 

 

 

 

 

 

Прибыль от продажи одного изде-

 

 

 

лия модификации I, II, III составляет

 

 

 

соответственно 15, 22, 19 грн.

 

 

 

 

В этой статье мы предлагаем вам рас-

 

 

 

смотреть последовательно решение

 

 

 

трех постепенно усложняющихся задач.

 

 

 

1. Определить оптимальный недель-

 

 

 

ный план производства продукции,

 

 

 

то есть план выпуска изделий, при

 

 

 

котором фирма получит макси-

Рис. 1. Подготовленные данные на рабочем листе Excel

 

мальную прибыль.

 

 

 

 

46

Компьютеры + Программы № 12 (86) 2001

2.Для удовлетворения потребностей постоянного клиента фирма обязана выпускать в неделю не менее 30 изделий модификации III. Как повлияет это условие на оптимальный план выпуска изделий?

3.Хотя рынок сбыта неограничен, возможности хранения изделий на фирме ограничены 140 экземплярами. Как влияет это ограничение на оптимальный план производства продукции?

Решение

Пусть x1, x2, x3 — количество изделий модификации I, II, III соответственно в плане производства.

Так как затраты, связанные с выполнением работ по изготовлению комплектующих для изделий модификаций I, II, III, по сборке этих изделий, по их тестированию и упаковке, не превосходят 3600, 2400 и 1800 грн. соответственно, получаем следующие ограничения:

 

20 x1 + 30 x2 + 20 x3

3600;

 

10 x1 + 20 x2 + 30 x3

2400;

10 x1 + 10 x2 + 20 x3 1800.

Кроме того, x1, x2, x3 могут прини-

мать только неотрицательные и целочисленные значения, то есть: x10;

x20; x30; x1; x2; x3 — целые.

Таким образом, приходим к следующей системе ограничений:

 

20 x1

+ 30 x2

+ 20 x3

3600;

 

 

10 x

1

+ 20 x

2

+ 30 x

3

2400;

 

 

 

 

 

 

 

 

 

 

10 x1

+ 10 x2

+ 20 x3

1800.

(1)

 

xj

— целые, j=1;2;3;

 

 

 

 

 

 

 

 

xj

0, j=1;2;3;

 

 

 

 

 

Недельная прибыль фирмы от реализации произведенного товара определяется целевой функцией

Z = 15 x1 + 22 x2 + 19 x3.

(2)

Следовательно, решение сформулированной задачи оптимизации сводится к решению задачи целочисленного линейного программирования, а именно, к определению таких значений x1, x2, x3, удовлетворяющих систему ограничений (1), при которых целевая функция (2) достигает максимума.

За дело — Excel

Продемонстрируем, как легко реализуется решение такого рода задач в среде электронных таблиц Excel.

SOFT –> ТЕОРИЯ

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

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

Рис. 4. Результаты расчетов на рабочем листе Excel

Сначала заполняем таблицу исход-

 

Затем в ячейку A8 заносим значение

 

ных данных (рис.1). В диапазон ячеек

 

целевой функции. Это значение оп-

В2:B4 вводим произвольные начальные

 

ределим с использованием встроен-

значения переменных x1, x2, x3, напри-

 

ной математической функции

мер, нулевые значения. В диапазон яче-

 

СУММПРОИЗВ(1-й массив; 2-й мас-

ек H2:H4 вводим значения прибыли от

 

сив). Первый массив состоит из значе-

реализации каждого изделия модифи-

 

ний прибыли от реализации каждого

кации I, II, III. В диапазон ячеек C2:E4

 

изделия модификации I, II, III (диа-

вводим значения затрат, связанных с

 

пазон ячеек H2:H4), второй массив —

выполнением каждой операции в про-

 

из значений переменных x1, x2, x3 (ди-

цессе изготовления одного изделия. В

 

апазон ячеек В2:B4). Таким образом,

диапазон ячеек C5:E5 вводим значения

 

в ячейке A8 будем иметь формулу

максимальных недельных затрат фир-

 

=СУММПРОИЗВ(H2:H4;B2:B4).

мы в процессе изготовления изделий,

 

В диапазон ячеек C8:E8 вводим ле-

связанных с выполнением каждой опе-

 

вые части неравенств системы (1).

рации соответственно.

 

В ячейку же C8 вводим формулу

№ 12 (86) 2001 Компьютеры + Программы

47

=СУММПРОИЗВ(C2:C4;$B$2:$B$4).

 

Задача 1

гового окна: адрес ячейки целевой

Для случаев II, III модификаций ко-

 

Дальнейшие действия: в меню Сер0

функции (целевой ячейки), тип опти-

пируем эту формулу в ячейки D8:E8,

 

вис выбираем команду Поиск решения.

мизации (искать максимум или ми-

используя маркер заполнения.

 

Заполняем поля появившегося диало-

нимум), адреса ячеек с переменными,

 

 

 

 

ограничения. При задании системы

 

 

 

 

ограничений используется кнопка

 

 

 

 

 

 

 

 

Добавить. При ее нажатии появляется

 

 

 

 

вспомогательное диалоговое окно, в

 

 

 

 

поля которого вводятся ссылки на

 

 

 

 

ячейки и ограничения, накладывае-

 

 

 

 

мые на переменные в рассматривае-

 

 

 

 

мой задаче. Как видно из рис. 2, сфор-

 

 

 

 

мированную систему ограничений

 

 

 

 

в дальнейшем можно редактировать.

 

 

 

 

Для этого служат кнопки Изменить

 

 

 

 

и Удалить. Далее следует нажать кноп-

 

 

 

 

ку Выполнить, после чего будет осуще-

 

 

 

 

ствлена процедура Поиск решения,

 

 

 

 

по результатам которой выводится со-

 

 

 

 

общение о найденном решении или о

 

 

 

 

невозможности его определить (рис. 3).

 

 

 

 

Как видно из рис. 3, полученные ре-

 

 

 

 

зультаты можно сохранить (кнопка

 

 

 

 

ОК), изменив содержимое ячеек с пе-

 

 

 

 

ременными (рис. 4); можно также от-

 

 

 

 

казаться от сохранения результатов

 

 

 

 

(кнопка Отмена).

 

 

 

 

Совсем несложно сформировать от-

Рис. 5. Отчет по результатам на рабочем листе Excel

чет с более подробной информацией

 

 

 

 

о том, как проходил процесс поиска

 

 

 

 

решения (рис. 5). В разделе отчета Ог0

 

 

 

 

раничения указывается состояние всех

 

 

 

 

ограничений. Тип связанный означа-

 

 

 

 

ет, что данное ограничение удовлетво-

 

 

 

 

рено, но при этом соответствующий

 

 

 

 

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

 

 

 

 

чение, которое уже дальше некуда из-

 

 

 

 

менять.

 

 

 

 

Следует отметить, что если в резуль-

 

 

 

 

тате выполнения процедуры Поиск ре0

 

 

 

 

шения решение не будет найдено, хо-

 

 

 

 

тя известно, что такое решение долж-

 

 

 

 

но существовать, то часто подобную

 

 

 

 

проблему удается решить, изменив од-

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

 

 

ну или несколько опций в диалоговом

 

 

окне Параметры поиска решения и по-

 

 

 

 

 

 

 

 

вторно запустив процедуру Поиск ре0

 

 

 

 

шения. Чтобы появилось диалоговое

 

 

 

 

окно Параметры поиска решения,

 

 

 

 

щелкните в диалоговом окне Поиск

 

 

 

 

решения на кнопке Параметры. С по-

 

 

 

 

мощью диалогового окна Параметры

 

 

 

 

поиска решения можно контролиро-

 

 

 

 

вать многие аспекты процесса реше-

 

 

 

 

ния задачи.

 

 

 

 

Таким образом, на рис. 4 получили

 

 

 

 

искомое решение сформулированной

Рис. 7. Результаты расчетов на рабочем листе Excel

задачи оптимизации: максимальную

 

 

 

 

 

48

Компьютеры + Программы № 12 (86) 2001

прибыль в 2760 грн. фирма может получить в случае, если изготовит изделия модификации I, II, III в количестве 100, 40, 20 экземпляров соответственно.

Задача 2

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

 

20 x1 + 30 x2 + 20 x3

3600;

 

10 x1 + 20 x2 + 30 x3

2400;

 

10 x1 + 10 x2 + 20 x3

1800;

 

x3 і 30;

 

(3)

 

 

 

xj

— целые, j=1;2;3;

 

 

 

xj

0, j=1;2;3;

 

 

Решение данной задачи сводится к определению таких значений x1, x2, x3, удовлетворяющих систему ограничений (3), при которых целевая функция (2) будет иметь максимальное значение.

Решение этой задачи легко получить с помощью надстройки Поиск ре0 шения, используя решение предыдущей задачи, причем в диалоговом окне Поиск решения (рис. 2) следует добавить лишь одно новое ограничение (рис. 6). В итоге получаем решение новой задачи оптимизации (рис. 7), откуда следует: для получения максимальной в этом случае прибыли (2580 грн.) фирма должна изготовить изделия модификации I, II, III в количестве 90, 30, 30 экземпляров соответственно.

Задача 3

Если производство фирмы сдерживается возможностями хранения изделий 140 экземплярами, хотя рынок сбыта неограниченный, то будем иметь дополнительное ограничение x1 + x2 + x3 140. В этом случае приходим к следующей системе ограничений:

 

20 x1 + 30 x2

+ 20 x3

3600;

 

10 x1 + 20 x2

+ 30 x3

2400;

 

10 x1 + 10 x2

+ 20 x3

1800;

 

x1

+ x2 + x3 Ј 140;

 

 

 

x3

і 30;

 

 

(4)

 

xj

— целые, j=1;2;3;

 

 

 

xj

0, j=1;2;3.

 

 

SOFT –> ТЕОРИЯ

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

Рис. 9. Результаты расчетов на рабочем листе Excel

Решение этой задачи сводится к определению значений x1, x2, x3 удовлетворяющих систему ограничений (4), при которых целевая функция (2) будет иметь максимум.

По аналогии решение данной задачи легко получаем с помощью надстройки Поиск решения, используя решение предыдущей задачи, причем в диалоговом окне Поиск решения (рис. 6) добавляется одно новое ограничение (рис. 8). В результате получаем решение задачи оптимизации (рис. 9): фирма в этом случае получит максимальную прибыль (2500 грн.), если изготовит изделия модификации I, II, III в количестве 70, 40, 30 экземпляров соответственно.

Сравнительная таблица результатов

 

Задача 1

Задача 2

Задача 3

I

100

90

70

 

 

 

 

II

40

30

40

III

20

30

30

 

 

 

 

Макс. прибыль

2760 грн.

2580 грн.

2500 грн.

 

 

 

 

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

Литература

1.Терехов Л.Л. Экономико-математи- ческие методы.— М.: Статистика, 1968.— 300 с.

2.Дж.Уокенбах. Excel 97. Библия пользователя.К.: Диалектика, 1997.— 624 с.

3.П.Дж. Бернс, Дж.Р. Николсон. Секреты Excel для Windows 95.— К.: Диалектика, 1996.— 576 с.

4.Толбатов Ю.А. Економетрика: Підручник для студентів.— К.: Четверта хвиля, 1997.— 320 с.

Валерий Владимирович ГАВРИЛЕНКО,

докт. физ. мат. наук, доцент,

Любовь Михайловна ПАРОХНЕНКО,

ассистент (Национальный транспортный университет)

№ 12 (86) 2001 Компьютеры + Программы

49