Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология
Образование Политология Производство Психология Стандартизация Технологии


Решение задач оптимизации с использованием MS Excel



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

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

Контрольный пример линейной оптимизационной задачи  
  Для производства столов и шкафов мебельная фабрика использует необходимые ресурсы. Нормы затрат ресурсов на одно изделие данного вида, прибыль от реализации одного изделия и общее количество имеющихся ресурсов каждого вида приведены в табл. 1. Таблица 1
Ресурсы Нормы затрат ресурсов на одно изделие Общее количество ресурсов
Стол Шкаф
Древесина 1 вида 0, 2 0, 1
Древесина 2 вида 0, 1 0, 3
Трудоемкость (человеко-часов) 1, 2 1, 5 371, 4
Прибыль от реализации одного изделия (руб.)  

 

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

 
  Для решения этой задачи необходимо построить математическую модель. Процесс построения модели можно начать с ответа на следующие три вопроса: 1. Для определения каких величин строится модель? 2. В чем состоит цель, для достижения которой из множества всех допустимых значений переменных выбираются оптимальные? 3. Каким ограничениям должны удовлетворять неизвестные? В данном случае мебельной фабрике необходимо спланировать объем производства столов и шкафов так, чтобы максимизировать прибыль. Поэтому переменными являются: х1 – количество столов, х2 – количество шкафов Суммарная прибыль от производства столов и шкафов равна z=6× x1+8× x2. Целью фабрики является определение среди всех допустимых значений х1 и х2 таких, которые максимизируют суммарную прибыль, т.е. целевую функцию z. Ограничения, которые налагаются на х1 и х2: - объем производства шкафов и столов не могут быть отрицательным, следовательно х1, х2 ³ 0. - нормы затрат древесины на столы и шкафы не могут превосходить максимально возможный запас данного исходного продукта, следовательно 0, 2x1+0, 1x2£ 40, 0, 1x1+0, 3x2£ 60. Кроме того, ограничение на трудоемкость не превышает количества затрачиваемых ресурсов: 1, 2x1+1, 5х2£ 371, 4. Таким образом, математическая модель данной задачи имеет следующий вид: максимизировать функцию z=6х1+8х2 при следующих ограничениях: 0, 2x1+0, 1x2£ 40 0, 1x1+0, 3x2£ 60 1, 2x1+1, 5х2£ 371, 4. Данная модель является линейной, т.к. целевая функция и ограничения линейно зависят от переменных.  
    Решение задачи с помощью MS Excel
  1. Отвести ячейки A3 и ВЗ под значения переменных х1 и х2 (рис. 1). Рис. 1. Диапазоны, отведенные под переменные, целевую функцию и ограничения 2. В ячейку С4 ввести функцию цели: =6× АЗ+8× ВЗ, в ячейки А7: А9 ввести левые части ограничений: =0, 2× А3+0, 1× ВЗ =0, 1× А3+0, 3× ВЗ =1, 2× АЗ+1, 5× ВЗ, а в ячейки В7: В9 – правые части ограничений (рис. 2.1). 3. Выбрать команду Сервис/Поиск решения (Tools/Solver) и заполнить открывшееся диалоговое окно Поиск решения (Solver) так, как показано на рис. 2. Средство поиска решений является одной из надстроек Excel. Если в меню Сервис (Тоо1s) отсутствует команда Поиск решения (Solver), то для ее установки необходимо выполнить команду Сервис/ Надстройки/ Поиск решения (Tools/Add-ins/Solver). Для ввода ограничений нажмите кнопку Добавить. Рис. 2. Диалоговое окно Поиск решения задачи о максимизации прибыли на фабрике Внимание! В диалоговом окне Параметры поиска решения (Solver Options) необходимо установить флажок Линейная модель (Assume Linear Model) (рис. 3). Рис. 3. Диалоговое окно Параметры поиска решения 4. После нажатия кнопки Выполнить (Solve) открывается окно Результаты поиска решения (Solver Results), которое сообщает, что решение найдено (рис. 4). Рис. 4. Диалоговое окно Результаты поиска решения 5. Результаты расчета задачи представлены на рис. 5, из которого видно, что оптимальным является производство 102 столов и 166 шка­фов. Этот объем производства принесет фабрике 1940 руб. прибыли. Рис. 5. Результаты расчета с помощью средства поиска решений для задачи максимизации выпуска столов и шкафов  
  Индивидуальное задание  
1. Построить математическую модель задачи согласно вашему варианту. 2. Решить задачу с помощью средства MS Excel Поиск решения. 3. Сделать соответствующие выводы.  
Задача 1.  
Для производства двух видов изделий А и В используется токарное, фрезерное и шлифовальное оборудование. Нормы затрат времени для каждого из типов оборудования на одно изделие данного вида приведены в табл. 2. В ней же указан общий фонд рабочего времени каждого из типов оборудования, а также прибыль от реализации одного изделия.   Таблица 2
Тип оборудования Затраты времени (станко-часов) на обработку одного изделия Общий фонд полезного рабочего времени
А В
Фрезерное Токарное Шлифовальное 10 5 6 8 10 12 168 180 144
Прибыль от реализации одного изделия (руб.)  

 

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

 
Задача 2.  
На звероферме могут выращиваться черно-бурые лисицы и песцы. Для обеспечения нормальных условий их выращивания используется три вида кормов. Количество корма каждого вида, которое должны ежедневно получать лисицы и песцы, приведено в табл. 3. В ней же указаны общее количество корма каждого вида, которое может быть использовано зверофермой, и прибыль от реализации одной шкурки лисицы и песца. Найти оптимальное соотношение количества кормов и численности поголовья лис и песцов. Таблица 3
Вид корма Количество единиц корма, которое ежедневно должны получать Общее количество корма
А В
Вид 1 Вид 2 Вид 3 2 4 6 3 1 7 180 240 426
Прибыль от реализации одной шкурки (руб.)  

 

 
         

 

Контрольный пример транспортной задачи

Фирма имеет 4 фабрики и 5 центров распределения ее товаров. Фабрики фирмы располагаются в Денвере, Бостоне, Новом Орлеане и Далласе с производственными возможностями 200, 150, 225 и 175 еди­ниц продукции ежедневно соответственно. Центры распределения товаров фирмы располагаются в Лос-Анджелесе, Далласе, Сент-Луисе, Вашингтоне и Атланте с потребностями в 100, 200, 50, 250 и 150 единиц продукции ежедневно соответственно. Хранение на фабрике единицы продукции, не поставленной в центр распределения, обходится в $0, 75 в день, а штраф за просроченную поставку единицы продукции, заказанной потребителем в центре распределения, но там не находящейся, равен $2, 5 в день. Стоимость перевозки единицы продукции с фабрик в пункты распределения приведена в табл. 4.

Таблица 4

   
    Лос-Анджелес Даллас Сен-Луис Вашингтон Атланта
Денвер 1, 50 2, 00 1, 75 2, 25 2, 25
Бостон 2, 50 2, 00 1, 75 1, 00 1, 50
Новый Орлеан 2, 00 1, 50 1, 50 1, 75 1, 75
Даллас 2, 00 0, 50 1, 75 1, 75 1, 75

 

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

Поскольку данная модель сбалансирована (суммарный объем произведенной продукции равен суммарному объему потребностей в ней), то в этой модели не надо учитывать издержки, связанные как со складированием, так и с недопоставками продукции. В противном случае в модель нужно было бы ввести:

- в случае перепроизводства – фиктивный пункт распределения, стоимость перевозок единицы продукции в который полагается равной стоимости складирования, а объемы перевозок объемам складирования излишков продукции на фабриках;

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

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

Неизвестными в данной задаче являются объемы перевозок. Пусть xij – объем перевозок с i-й фабрики в j-й центр распределения. Функция цели – это суммарные транспортные расходы, т. е. где сij – стоимость перевозки единицы продукции с i-й фабрики j-й центр распределения.

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

- Объемы перевозок не могут быть отрицательными.

- Так как модель сбалансирована, то вся продукция должна быть вывезена с фабрик, а потребности всех центров распределения должны быть полностью удовлетворены.

В результате имеем следующую модель:

– минимизировать при ограничениях:

, j Î [1, 5]

xij ³ 0, iÎ [1, 4], jÎ [1, 5]

, iÎ [1, 4],

где aij – объем производства на i-й фабрике, bj – спрос в j-м центре распределения.

Решение задачи с помощью MS Excel  
1. Ввести данные, как показано на рис. 6. Рис. 6. Исходные данные транспортной задачи В ячейки А1: Е4 введены стоимости перевозок. Ячейки А6: Е9 отведены под значения неизвестных (объемы перевозок). В ячейки G6: G9 введены объемы производства на фабриках, а в ячейки А11: Е11 введена потребность в продукции в пунктах распределения. В ячейку F10 введена целевая функция =СУММПРОИЗВ(А1: Е4; А6: Е9). В ячейки А10: Е10 введены формулы =СУММ(А6: А9) =СУММ(В6: В9) =СУММ(С6: С9) =СУММ(D6: D9) =СУММ(Е6: Е9), определяющие объем продукции, ввозимой в центры распределения. В ячейки F6: F9 введены формулы =СУММ(А6: Е6) =СУММ(А7: Е7) =СУММ(А8: Е8) =СУММ(А9: Е9), вычисляющие объем продукции, вывозимой с фабрик. 2. Выбрать команду Сервис/Поиск решения (Tools/Solver) и заполнить открывшееся диалоговое окно Поиск решения (Solver), как показано на рис. 7. Внимание! В диалоговом окне Параметры поиска решения (Solver Options) необходимо установить флажок Линейная модель (Assume Linear Model). Рис. 7. Диалоговое окно Поиск решения для транспортной задачи 3. После нажатия кнопки Выполнить (Solve) средство поиска решений находит оптимальный план поставок продукции и соответствующие ему транспортные расходы (рис. 8). Рис. 8. Оптимальное решение транспортной задачи  
Индивидуальное задание  
1. Построить математическую модель задачи согласно вашему варианту. 2. Решить задачу с помощью средства MS Excel Поиск решения. 3. Сделать соответствующие выводы.  
Задача 3.  
Решить транспортную задачу со следующими условиями (табл. 5). Таблица 5
Пункты отправления Пункты назначения Запасы
В1 В2 В3 В4
А1
А2
A3
Потребности  

 

 
Задача 4.  
Для строительства трех объектов используется кирпич, изготовляемый на трех заводах. Ежедневно каждый из заводов может изготовлять 100, 150 и 50 уcл. ед. кирпича. Ежедневные потребности в кирпиче на каждом из строящихся объектах соответственно равны 75, 80, 60 и 85 усл. ед. Известны также тарифы перевозок 1 усл. ед. кирпича с каждого с заводов к каждому из строящихся объектов: . Составить такой план перевозок кирпича к строящимся объектам, при котором общая стоимость перевозок является минимальной.  
Задача 5.  
На трех железнодорожных станциях скопилось 120, 110 и 130 неза­груженных вагонов. Эти вагоны необходимо перегнать на железнодорожные станции В1, В2, ВЗ, В4 и В5. На каждой из этих станций потребность в вагонах соответственно равна 80, 60, 70, 100 и 50. Тарифы перевозок задаются матрицей . Составить такой план перегонок вагонов, при котором общая стоимость была бы минимальной.  

Решение логических задач

Для решения логических задач применяется алгебра логики или Булева алгебра.

В ее основу положено элементарное логическое высказывание, которое может быть только истинным или ложным.

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

Основные функции (логические операции) алгебры логики следующие:

Конъюнкция (логическое умножение): в естественном языке соответствует союзу «и», обозначается &.

Конъюнкция – это логическая операция, ставящая в соответствие каждым двум простым высказываниям составное высказывание, являющееся истинным тогда и только тогда, когда оба исходные высказывания истинны.

Дизъюнкция – (логическое сложение): в естественном языке соответствует союзу «или», обозначается V.

Дизъюнкция – это логическая операция, которая каждым двум простым высказываниям ставит в соответствие составное высказывание, являющееся истинным, когда хотя бы одно из двух образующих его высказываний истинно, и ложным.

Инверсия (отрицание): в естественном языке соответствует словам «неверно, что…» и частице не, обозначается Ā.

Инверсия – это логическая операция, которая каждому простому высказыванию ставит в соответствие составное высказывание, заключающееся в том, что исходное высказывание отрицается.

Контрольный пример

Задача 1.

В одной из горячих точек служили 5 офицеров: генерал, полковник, майор, капитан и лейтенант. Один из них сапер, другой – пехотинец, третий – танкист, четвертый – связист, пятый – артиллерист. У каждого из них есть сестра. И каждый из них женат на сестре своего однополчанина. Вот что еще известно об этих офицерах:

· По меньшей мере, один из родственников связиста старше его по званию.

· Капитан никогда не служил в Хабаровске.

· Оба родственника-пехотинца и оба родственника-танкиста служили раньше в Мурманске. Ни один родственник генерала в Мурманске не был.

· Танкист служил в Твери вместе с обоими своими родственниками, а лейтенант там не служил.

· Полковник служил в Махачкале вместе со своими родственниками.

· Танкист не служил в Махачкале. Там служил только один из его родственников.

· Генерал служил с обоими своими родственниками в Хабаровске, а в Махачкале он не бывал.

· Артиллерист не служил ни в Хабаровске, ни в Твери.

Определите, кто из офицеров имеет какое звание.

Решение задачи

Ясно, что каждый офицер имеет двух родственников. Один из них – брат жены, а другой – муж сестры. Обозначим для удобства каждого офицера буквой и расположим их так, чтобы соседом каждого были его родственники (рис.)

Рис. Расположение по порядку

Пусть пехотинец будет обозначен буквой А. Поскольку трое из офицеров служили в Мурманске, а двое там не были, то танкисту должна соответствовать либо буква В, либо Г. Допустим, что танкист – В. Отсюда следует (с учетом условия задачи), что А и В не служили в Мурманске и что Б – генерал. Продолжая рассуждать, приходим к выводу, что Б, В и Г служили в Твери. Поэтому лейтенантом должен быть А или Д и букве Д должен соответствовать артиллерист. Далее, либо В и Г, либо В и Б не служили в Махачкале. Следовательно, А, Д и Б либо А, Д и Г служили в Махачкале. А поскольку мы знаем, что Б не служил в Махачкале, это значит, что там служили А, Д и Г и что Д – полковник. Таким образом, А – лейтенант.

Переходим к следующему этапу решения. A, Б и В служили в Хабаровске, а Д там не служил. Нам известно, что капитан в Хабаровске не служил. Поскольку капитал не может быть Д, следовательно, ему соответствует буква Г. Далее приходим к заключению, что В – майор. Известно, что по меньшей мере один офицер должен быть старше по званию, чем связист. Следовательно, связист не может быть Б и должен быть Г, а саперу соответствует буква Б.

Таким образом, в итоге получается, что лейтенант – пехотинец, гене­рал – сапер, майор – танкист, капитан – связист, полковник – артиллерист.

Задача 2.

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

Главной новостью дня был состоявшийся накануне финал эстафеты 4´ 100 м для мужчин. В финал после упорной борьбы вышли команды шести стран: европейские команды А и B, африканские команды C и D и 2 команды-представительницы американского континента E и F.

Иван Михайлович охотно узнал бы, как распределились места среди участников финала, но сделать это оказалось непросто. В тот день Иван Михайловичу особенно не везло: стоило ему пристроиться к кому-ни­будь, чтобы заглянуть через плечо, как счастливый обладатель спортив­ной газеты тотчас переворачивал страницу, а доносившиеся со всех сто­рон реплики знатоков и ценителей спроса были маловразумительными.

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

1. Команда А одержала победу над командой В.

2. Африканская команда получила золотые медали.

3. Команда В одержала победу над командой D.

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

5. Африканская команда отстала от всех остальных участников финала.

6. Первыми финишировали 3 африканских бегуна.

7. Команда F одержала победу над командой В.

8. Команда Е одержала победу над командой F.

9. В составе европейских команд не было африканских спортсменов.

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

Наконец, после тщательного анализа Иван Михайлович понял, что одна из девяти перечисленных выше посылок ложная. Он что-либо не так понял, либо плохо разглядел, либо неправильно вспомнил.

Все остальные посылки истинны.

Как распределились места между шестью командами, принимавшими участие в финальном забеге?

Решение задачи

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

Итак, проанализируем данные утверждения. Если утверждение (9) заведомо верно (по условию задачи), то нетрудно установить, что утверждения (4), (5), и (6) не могут быть истинными одновременно.

Действительно, если истинно утверждение (6), то 3 первые места разделили между собой 2 африканские и 1 американская команды либо 1 африканская и 2 американские команды. Но по утверждению (5) 2 аф­риканские команды не могли быть среди тех, кто вышел на первые три места, а по утверждению (4) 2 американские команды могли занять лишь первое и третье места. Кроме того, из этого же утверждения (4) следует, что на второе место вышла европейская команда и, следовательно, среди обладателей трех первых мест не было ни одной африканской команды.

Таким образом, ложные сведения должны содержаться в каком-то из утверждений (4), (5) и (6), а остальные утверждения истинны, т.к. по условию задачи ложным является только одно утверждение. Воспользуемся сначала заведомо истинными утверждениями.

Объединим утверждения (1), (3) и (7) в одно, т. к. они взаимосвязаны между собой. Прочитав их в последовательности (1)-(7)-(3), приходим к следующему выводу: если склюючить команды С и Е, то представители остальных команд могли прийти к финишу лишь в последовательности A, F, В, D. Следовательно, среди команд, занявших 3 первые места, заведомо должна быть европейская команда А. В худшем случае, она могла выйти на третье место, но оказалась среди призеров. Это означает, что утверждение (6) ложно. Чтобы определить, какое место заняла каждая из шести команд, расположим истинные утверждения в следующем порядке: (2), (4), (5), (8), (1)-(7)-(3), (9).

Как видно из утверждений (2) и (1)-(7)-(3), первое место могла занять лишь команда С, поскольку команда D заведомо не вышла на первое место. По утверждению (5), команда D могла занять лишь последнее, шестое, место.

Утверждения (8) и (1)-(7)-(3) позволяют схематически изобразить распределение мест между четырьмя остальными командами так, как показано на рис. (острие стрелки направлено к команде, показавшей лучшее время, конец – к команде, занявшей последнее место).

Рис. Распределение мест
между четырьмя явно не лидирующими командами

Остается невыясненным, какая из команд – Е или А – показала лучший результат. Эту неопределенность помогает разрешить утверждение (4). Согласно схеме, между двумя американскими командами Е и F могла «вклиниться» только европейская команда А.

Следовательно, представители четырех команд, о которых идет речь, могли пересечь линию финиша лишь в следующей последовательности: Е, А, F, В. Это означает, что команда С заняла первое место, Е – второе, А – третье, F – четвертое, В – пятое и D – шестое.

 

Индивидуальное задание

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

Задача 1.

На острове живут два племени: молодцы, которые всегда говорят правду, и лжецы, которые всегда лгут. Путешественник встретил туземца, спросил его, кто он такой, и, когда услышал, что он из племени молодцов, нанял его в услужение. Они пошли и увидели вдали другого туземца, и путешественник послал своего слугу спросить его, к какому племени он принадлежит. Слуга вернулся и сказал, что тот утверждает, что он из племени молодцов.

Ответьте, был ли слуга молодцом или же лгуном.

Задача 2.

Четыре юных филателиста – Митя, Толя, Саша и Петя – купили почтовые марки. Каждый из них покупал марки только одной страны, причем двое из них купили российские марки, один – болгарские, а один – словацкие. Известно, что Митя и Толя купили марки двух разных стран. Марки разных стран купили Митя с Сашей, Петя с Сашей, Петя с Митей и Толя с Сашей. Кроме того, известно, что Митя купил не болгарские марки.

Какие марки купил каждый из мальчиков?

Задача 3.

Четыре человека взялись выполнять работу маляра, слесаря, кузнеца и штукатура – каждый будет делать что-то одно. Выяснилось, что Антон не будет маляром и не будет слесарем, Алексей не будет кузнецом и не будет маляром, Евгений не будет слесарем и не будет маляром, Дмитрий не будет кузнецом и не будет слесарем. Известно также, что если Антон не будет кузнецом, то Дмитрий не будет маляром.

Кто и какую работу будет выполнять?

Задача 4.

Пятеро девушек поехали в отпуск каждая на своей машине. Все машины были разного цвета. Первой ехала на белой машине американ­ка. За ней на «Тойоте» русская. За француженкой на синей машине ехал желтый «Ситроен». Замыкала колонну англичанка на фиолетовом «Фор­де». «Плимут» был новее «Бьюика», но менее мощный, поэтому он ехал в середине колонны, а полька восхитительно выглядела в своем брюч­ном костюме. Одна из машин была зеленого цвета.

Кто и на какой машине ехал (указать цвет и марку)?

 

Задача 5.

Вернувшись домой, Мегре позвонил на набережную Орфевр.

Говорит Мегре. Есть новости?

Да, шеф. Поступили сообщения от инспекторов. Торранс установил, что если Франсуа был пьян, то либо Этьен убийца, либо Франсуа лжет. Жульен считает, что или Этьен убийца, или Франсуа не был пьян, и убийство произошло после полуночи. Инспектор Люка просил передать вам, что если убийство произошло после полуночи, то либо Этьен убийца, либо Франсуа лжет. Затем позвонила…

Все. Спасибо. Этого достаточно.

Комиссар положил трубку. Он знал, что трезвый Франсуа никогда не лжет. Теперь он знал все.

Опишите, что знает Мегре?

Задача 6.

Семья состоит из пяти человек: Алексея, Веры, Даши, Глеба и Евгении. Когда семья смотрит телевизор, то соблюдаются следующие условия:

· Смотрят либо Даша, либо Евгения, либо обе вместе.

· Смотрят либо Глеб, либо Вера, но не вместе.

· Даша и Глеб либо смотрят вместе, либо вместе не смотрят.

· Если телевизор смотрит Алексей, то смотрит и Вера.

· Если телевизор смотрит Евгения, то смотрят Алексей и Даша.

Кто смотрит телевизор?

 


Поделиться:



Популярное:

Последнее изменение этой страницы: 2017-03-08; Просмотров: 1666; Нарушение авторского права страницы


lektsia.com 2007 - 2024 год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! (0.077 с.)
Главная | Случайная страница | Обратная связь