2. Formulation and Solution of Binary Optimization Problems

Loading...

Do curso por University of Colorado Boulder

Business Analytics for Decision Making

140 classificações

University of Colorado Boulder

Business Analytics for Decision Making

140 classificações

Curso 3 de 5 em Specialization Advanced Business Analytics

In this course you will learn how to create models for decision making. We will start with cluster analysis, a technique for data reduction that is very useful in market segmentation. You will then learn the basics of Monte Carlo simulation that will help you model the uncertainty that is prevalent in many business decisions. A key element of decision making is to identify the best course of action. Since businesses problems often have too many alternative solutions, you will learn how optimization can help you identify the best option. What is really exciting about this course is that you won’t need to know a computer language or advanced statistics to learn about these predictive and prescriptive analytic models. The Analytic Solver Platform and basic knowledge of Excel is all you’ll need. Learners participating in assignments will be able to get free access to the Analytic Solver Platform.

Na lição

Decision Analytics

At the end of this module students should be able to: 1. Given a business situation, apply an appropriate technique to identify the best solution alternatives 2. Formulate and solve models for business problems that requires yes/no decisions and logical constraints 3. Create models that mix techniques and tools such as simulation and optimizationAnalyze and interpret results to make informed decisions

1. Business Problems with Yes/No Decisions5:42

2. Formulation and Solution of Binary Optimization Problems7:48

3. Metaheuristic Optimization8:22

Conheça os instrutores

Manuel Laguna
Professor
Leeds School of Business

In this video we're going to develop models for

one of the decision problems that we described in the last video.

Recall that we discussed three decision problems that require yes or no decisions.

These decisions are modeled with binary variables.

For the first of the three problems,

we will create a mathematical model before developing Excel and Solver models.

This is an approach that I showed to you in module three of this course.

Then we kind of forgot about it, and went directly to Excel and

all the other examples that we have worked together.

So I want to go back to the idea of creating the math model first, and

then translating it to Excel.

The problem consists of a company that wants to select magazine publishers for

an advertising campaign.

The data that the company has collected is shown in this table.

The company also knows that it costs $250 to engage a publisher.

This is a fixed cost than needs to be paid to each publisher that is selected.

Also, the advertising budget has been set at $25,000.

Since the company is considering seven publishers labeled A to G,

the model will have seven binary variables.

We're going to use the publisher labels for the binary variables.

In this way A = 1 will indicate that Publisher A is selected,

B = 1 will indicate that Publisher B is selected, and so on.

The model also needs seven interior variables

to choose the number of groups to purchase from each publisher.

Let's go over those variables GA to GG.

So GA will be the number of groups purchased from Publisher A.

We're now ready to formulate the problem.

Let's just start with the objective function.

It is reasonable to think that the company will like to maximize total

exposure while not exceeding its advertising budget.

The total exposure is the number of subscribers

reached by the advertising campaign.

The exposure from engaging a publisher is the number of

groups bought from the publisher multiplied by the size of the group.

The exposure from engaging publisher A, for example,

is 460 subscribers times GA, the groups bought from publisher A.

The total exposure is the sum of all these products as shown in here.

The model has ten constraints.

The first seven constraints restrict the purchasing of groups

only from those publishers that have been selected.

What this means in terms of the decision variables is that if A =

0 then GA must be = 0.

However if A = 1 then GA can take any value between 0 and 5.

The reason for the upper limit to B at 5 is

that this is the maximum number of groups that can be bought from Publisher A.

This is the set of seven constraints that model this part of the problem.

Note how the form of the constraint enforces the logic that

the groups from a publisher can be bought only when the publisher is selected.

The next two constraints are related to what we mentioned in the last video

about publishers being competitors.

We have B and D, in that situation, and also C and G.

We want constraints that will produce solutions that do not include

the selection of both B and D or the selection of both C and G.

There is a fairly simple way to create a constraint to deal with this situation.

If B and D are selected then the sum of these variables is 2.

Then, all we need to do is to restrict this sum to be no more than 1.

If B + D is forced to be less than or equal to 1,

then only one of them can be selected.

We do the same for C and G, as shown here.

Now we need to add the budget constraints to complete the model.

There are two sources of cost.

The fixed cost of engaging a publisher, and

the variable cost of purchasing groups.

A fixed cost of $250 is paid for each publisher that is selected.

Therefore, these costs can be calculated

as the sum of all the binary variables multiplied by 250.

The variable cost depends on the number of groups bought from each publisher.

Since there is a cost per group for each publisher,

then the variable cost is the product of the number of groups and the group cost.

The sum of all these products is the total variable cost.

The constraint is that the sum of the fixed and

the variable cost should be less than or equal to $25,000.

And this completes the model.

Now locate and open the Excel file Advertising Campaign so

you can see how the mathematical model can be translated into a spreadsheet model.

The spreadsheet has four tables.

The first small table contains the fixed cost and the budget data.

The table just below has the publisher data with the number of groups.

The subscriber per group, the cost per group, and

the block of decision variables that are highlighted in light gold.

There are two more tables in the right side,

one with the objective function and one with the constraints.

Let's clear all the values of the decision variables, and

enter the following solution.

Choose A, B, E, and F.

We buy 5 groups from A and B, 3 groups from E, and 1 group from F.

We can verify that this solution is feasible since it meets

all the constraints.

The total exposure of the solution is 761,000.

This spreadsheet contains an optimization model for this problem.

Let's take a look at it by clicking on the ASP tab of the ribbon.

The objective function is to maximize $J$4, that is total exposure.

The decision variables are in the block from cell $E$9 to cell $F$15.

All the constraints in this model are of the less than or equal type.

The left-hand sides are in cells $I$9 to $I$18,

the right-hand sides are in $K$9 to $K$18.

Finally, the model forces the variables in $E$9 to $E$15 to be binary,

and the variables in $F$9 to $F$15 to be integer.

Before solving, we verify that the engine is set to the standard LP.

Click the green play button to solve.

The optimal solution engages publishers A, B, E and G.

It prescribes the purchase 13 groups which result

in a total exposure of 876,200.

I know that with practice and intuition it is possible to

create Excel models without ever formulating the mathematical model.

However, I wanted to show to you a mathematical formulation of a binary

problem, to give you a mental picture of these models.

This should help you keep in mind the three elements of an optimization

problem as you work on your Excel and Solver models.

Explore nosso catálogo

Registre-se gratuitamente e obtenha recomendações, atualizações e ofertas personalizadas.

O Coursera proporciona acesso universal à melhor educação do mundo fazendo parcerias com as melhores universidades e organizações para oferecer cursos on-line.

© 2018 Coursera Inc. Todos os direitos reservados.

Baixar na App Store

Baixar no Google Play