Operation Research 2013 Edition
Setyabudi Indartono, Ph.D Assistant Professor at Faculty of Economy Yogyakarta State University
Course Module Series
2
Table of Contents Preface ................................................................................................................................ 6 Syllabi .................................................................................................................................. 7 Course Components ......................................................................................................... 7 Class Procedures .............................................................................................................. 8 Assessment ...................................................................................................................... 8 Course Schedule............................................................................................................... 9 Grading Systems ............................................................................................................ 10 Chapter 1: Introduction to Operations Research Concept .................................................. 11 Definition and origin ...................................................................................................... 11 Essential features of the OR approach ............................................................................ 12 Chapter 2: Introduction to Foundation mathematics and statistics Modeling ..................... 21 LP definition, .................................................................................................................. 21 Quantification of factors ................................................................................................ 26 LP and allocation of resources ........................................................................................ 33 Linearity requirement .................................................................................................... 40 Assignment-1 (Homework) ............................................................................................. 45 chapter 3: Expressing Linier programming problems .......................................................... 46 Limitations or constraints ............................................................................................... 46 Types of Constraints in Linear Programming Problems ................................................... 47 Chapter 4: Inventory Model ............................................................................................... 52 Pentingnya pengendalian persediaan ............................................................................. 53 Keputusan Persediaan .................................................................................................... 54 EOQ, mendifinisikan berapa banyak pemesanan ............................................................ 54 Inventory Cost ................................................................................................................ 55 Menentukan EOQ........................................................................................................... 56 ROP, Menentukan kapan dilakukan pemesanan ............................................................. 57 EOQ dengan asumsi tanpa penerimaan yang tak tentu................................................... 57
3
Menentukan annual caarrying cost ................................................................................ 58 Menentukan annual setup cost atau Annual ordering cost ............................................. 58 Model Diskon jumlah ..................................................................................................... 60 Pemakaianan safety stock .............................................................................................. 62 Reorder point dengan biaya ketidaktersediaan yang telah diketahui. ............................. 63 Biaya ketidaktersediaan (stockout). ................................................................................ 63 Carrying cost .................................................................................................................. 64 Safety stok dengan biaya yang tidak diketahui................................................................ 64 ABC Analisys................................................................................................................... 65 Analysis sensitivitas ........................................................................................................ 65 Assignment-2 (Homework) ............................................................................................. 65 Chapter 5: TRANSPORTAtion model ................................................................................... 66 Pendahuluan .................................................................................................................. 66 Seting up transportation problems ................................................................................. 66 Nortwest corner rule ...................................................................................................... 66 Stepping stone method: mencari biaya terkecil .............................................................. 67 MODI method ................................................................................................................ 72 Vogels approximation metod (VAM) .............................................................................. 73 Supply > demmand = dummy destination....................................................................... 77 Perhitungan total biaya adalah: ...................................................................................... 77 Supply < demmand = dummy source .............................................................................. 78 Degeneracy in transportation ......................................................................................... 79 Degeneracy during later solution stage. ......................................................................... 79 Pilihan solusi yang lebih dari satu pilihan ........................................................................ 79 Analisis Lokasi fasilitas.................................................................................................... 80 Chapter 6: Assignment Model ............................................................................................ 84 Minimization .................................................................................................................. 84 Dummy Row dan Dummy Colums .................................................................................. 89 MAKSIMALISASI PENUGASAN ......................................................................................... 89
4
Chapter 7: Project Analysis................................................................................................. 93 Pendahuluan .................................................................................................................. 93 PERT............................................................................................................................... 93 CPM ............................................................................................................................... 97 Diskusi Kasus.....................................................................................................................106 Case #1 CUSTOM VANS INC ...........................................................................................106 Case #2 Haygood Company ...........................................................................................111 Case #3 MANAGEMENT VIDEO PROFESIONAL ...............................................................114 Paper ................................................................................................................................117 Paper-1: Presentation of a New and Beneficial Method Through Problem Solving Timing of Open Shop by Random Algorithm Gravitational Emulation Local Search....................117 Paper-2: Inverse Optimization for Linear Fractional Programming .................................118 Paper-3: A multi-objective model for designing a group layout of a dynamic cellular manufacturing system ...................................................................................................118 Paper-4: Integrating truck arrival management into tactical operation planning at container terminals .......................................................................................................119 Paper-5: Pharmaceutical Inventory Management Issues in Hospital Supply Chains ........120 Paper-6: Improving a Flexible Manufacturing Scheduling using Genetic Algorithm ........120 Contoh Soal Quiz, UTS dan UAS .........................................................................................122 Quiz ..............................................................................................................................122 UTS ...............................................................................................................................124 UAS ...............................................................................................................................125 Penulis ..............................................................................................................................126 refferences .......................................................................................................................133
5
PREFACE
Operations research helps in solving problems in different environments that needs decisions. The module covers topics that include: linear programming, Transportation,
Assignment,
and
CPM/ MSPT
techniques.
Analytic
techniques and computer packages will be used to solve problems facing business managers in decision environments. This module aims to introduce students to use quantitative methods and techniques
for
effective
decisions–making;
model
formulation
and
applications that are used in solving business decision problems. The Learning Outcomes of this course included: 1. Knowledge
and
understanding: Be
able
to
understand
the
characteristics of different types of decision-making environments and the appropriate decision making approaches and tools to be used in each type. 2. Cognitive skills (thinking and analysis): Be able to build and solve Transportation Models and Assignment Models. 3. Communication skills (personal and academic): Be able to design new simple models, like: CPM, MSPT to improve decision –making and develop critical thinking and objective analysis of decision problems. 4. Practical and subject specific skills (Transferable Skills): Be able to implement practical cases, by using TORA, WinQSB
6
SYLLABI Course Components 1. Operations
Research:
Applications
and
Algorithms
Author: Wayne L Winston 2. Introduction to Operations Research (OR) 3. Introduction to Foundation mathematics and statistics 4. Linear Programming (LP), LP and allocation of resources, LP definition, Linearity requirement 5. Maximization and Minimization problems. 6. Graphical LP Minimization solution, Introduction, Simplex method definition, formulating the Simplex model. 7. Linear Programming – Simplex Method for Maximizing. 8. Simplex maximizing example for similar limitations, Mixed limitations 9. Example containing mixed constraints, Minimization example for similar limitations. 10. Sensitivity Analysis: Changes in Objective Function, Changes in RHS, The Transportation Model 11. Basic Assumptions 12. Solution Methods: a. Feasible Solution: The Northwest Method, The Lowest Cost Method; b. Optimal Solution: The Stepping Stone Method, Modified; Distribution (MODI) Method. 13. The Assignment Model: a. Basic Assumptions b. Solution Methods: Different Combinations Method, c. Short-Cut Method (Hungarian Method)
7
14. MSPT:- The Dijkestra algorithm, and Floyd’s Algorithm {Shortest Route Algorithm}
Class Procedures 1. Presence. Students are required to attend lectures at least 80% of total lectures held. Any violation against this rule may cause the ineligibility to get a final grade. 2. Class participation. Students are highly expected to contribute ideas, thoughts, experiences, and arguments to the class discussion. Although overviews of key points and issues are provided, we require that students comprehend the materials in details, raise questions and ideas, and create a “lively” class, meaning that students must read and prepare readings assigned prior to coming to the class. 3. An experiential approach. Continuously and consistently, students are assigned to do assignment and report the findings to the lecturer. Students will be randomly distributed into groups that consist of four members. 4. Internet exploration. Students are encouraged to harness the advancement of information and communications technology (ICT) in exploring knowledge and opportunities. Remember that in current circumstances, a clever person is not she who can answer all questions; rather, it is she who knows where to find answers.
Assessment •
Class participation/Discussion 15%
•
Presentations 20%
•
Mid-term examination (UTS) 30%
•
Final examination (UAS) 35%
8
Course Schedule Class 1.
Introduction to Operations Research (OR) Course: Assignment and Assessment
Class 2.
Introduction to Operations Research concept: Definition and origin. Essential features of the OR approach.
Class 3.
Introduction to Foundation mathematics and statistics modeling a. Quantification of factors and Linearity requirement b. Expressing linier programming problems: Minimization and maximization
Class 4.
Inventory Model
Class 5.
Transportation Model a. MODI b. Northwest corner rule c. Stepping stone method: mencari biaya terkecil d. VAM
Class 6.
Assignment Model a. Minimization (Hungarian/Floods’ technique) b. Maximization
Class 7.
Project Analysis (PERT – CPM)
Class 8.
Mid Exam
Class 9.
Case Study #1
Class 10. Case Study #2 Class 11. Case Study #3 Class 12. Quiz Class 13. Paper Discussion #1 - #2 Class 14. Paper Discussion #3 - #4 Class 15. Paper Discussion #5 - #6 Class 16. Final Examination
9
Grading Systems •
E~F means at least one of assignment and test found plagiarism
•
D (50-59) means that you are able to summarize and order readings relevant to the topic.
•
C (60-69) means that you do this with some greater precision and flair or more comprehensively and/or accessibly.
•
B (70-79) indicates that you have shown evidences of substantial and well argued independence of thoughts, insightful evaluation, or original research.
•
A (80-100) indicates that you have added significant new values to existing knowledge or understanding through logic or evidence of some ingenuity,creativity, or excellence
10
CHAPTER 1: INTRODUCTION TO OPERATIONS RESEARCH CONCEPT Definition and origin Operations research/management science is the development and application of mathematical techniques and models, for the purpose of solving problems in a wide array of fields, and producing better quality decisions. It is applied to Identifies better methods to coordinate financial, material, equipment, and human resources toward achievement of an organization’s goals, drawing from mathematics, science, and engineering. The use of techniques such as statistical inference and decision theory, mathematical programming, probabilistic models, network and computer science to solve complex operational and strategic issues. describe Operations research in several ways. Winston:
Scientists “a scientific
approach to decision making, which seeks to determine how best to design and operate a system, usually under conditions requiring the allocation of scarce resources.” Kimball & Morse:
“a scientific method of providing
executive departments with a quantitative basis for decisions regarding the operations under their control. Operation researchers use the technique to solve problems in different ways, propose alternative solutions to management for consideration, and responsible for monitoring the implementation of the selected solution, and working with others to ensure its success. Various issues are analyzed using the concept of operation research included High-level Strategy, Short-Term Planning, Intermediate-Term Planning, Forecasting, Resource Allocation, Performance Measurement, Scheduling, Supply Chain Management, Pricing, Design of Facilities and Systems, Transportation and Distribution, Analysis of
11
Large Data Bases, Statistical Quality Control, Project Management, Waiting Lines, Artificial Intelligence, and Risk Assessment.
Essential features of the OR approach In many large corporations, OR reports directly to the CEO. It is related to Organizational Structure. Some firms centralize OR in one department and or within each division. Other firms contract for OR services with an independent consulting firm and Analysts may also work closely with senior managers to identify and solve a variety of
operational problems.
Presentation to Management process of operation research application included: Analyst presents management with first recommendations based on the model results. Additional computer runs of the model may be needed to consider different assumptions. The O.R. analyst presents the final recommendation. Once management reaches a selection decision, the O.R. analyst will usually work with others in the organization to ensure the plan’s successful implementation. The Mathematical Model used by scientist Attempts to describe the system or problem being studied, enables the analyst to assign values to the various components and to clarify the relationships between them, Values can be altered in order to examine what may happen to the system or solution under different circumstances. Concept of Operations research provides rational basis for decision making include: •
Solves the type of complex problems that turn up in the modern business environment
•
Builds mathematical and computer models of organizational systems composed of people, machines, and procedures
12
•
Uses analytical and numerical techniques to make predictions and decisions based on these models It is believed that concept of Operations research draws upon
engineering, management, mathematics, and closely related to the "decision sciences" applied mathematics, computer science, economics, industrial engineering and systems engineering. The using of operational research concept, Managers describe the symptoms of the problem to the operations analyst who then formally defines the problem. Then The analyst breaks the problem down into its major components, and gathers information about each of them from many sources, both internal and external. The analyst that in turn selects the most appropriate analytical model or technique. Winston, Wayne L (1996) draws a basic methodology of Operations Research at The Seven Steps to a Good OR Analysis. It is included: 1. Identify the Problem or Opportunity: What are the objectives? Is the proposed problem too narrow? Is it too broad? 2. Understand the System: What data should be
be collected? How will data
collected? How do different components of the system interact with
each other? 3. Formulate a Mathematical Model: What kind of model should be used? Is the model accurate? Is the model too complex? 4. Verify the Model : Do outputs match current observations for current inputs? Are outputs reasonable? Could the model be erroneous? 5. Select the Best Alternative : What if there are conflicting objectives? Inherently the most difficult step. This is where software tools will help us! 6. Present the Results of the Analysis: Must communicate results in layman’s terms and System must be user friendly! 7. Implement and Evaluate: Users must be trained on the new system. System must be observed over time to ensure it works properly.
13
Various technique used in the application of operation research are Markov Processes, Econometric Models, Game Theory, Forecasting, Inventory Control, Assignment Algorithms, Goal Programming, Quality Control Models, Network Models, Simulation, Linear Programming, Queuing Models,
Dynamic
Programming,
Nonlinear
Programming,
Integer
Programming, Neural Networks, Expert Systems, and Decision Analysis. Sample of the used of the concept of operation researches is to make a decision on employment. O.R. analysts held 64,000 jobs in 2012 such as in Telecommunications
Company,
Aerospace
manufacturers,
Computer
systems design firms, Engineering, Higher education, Financial institutions, Insurance carriers, Airline industry, Management service firms, and State and federal governments. At least a masters degree in OR, engineering,
computer science,
math, information systems, or business, coupled with a
bachelors degree in any of the above, or economics or statistics need have Required Credentials of operation research concept. Concept of operation researches for employment decision is used to job outlook.
It is good,
because firms will strive to improve their productivity, effectiveness, and competitiveness, or perish! And because firms are sitting on hugh data bases that need to be analyzed by professionals who have the skills to do so. The number of professionals needed to support the growing demand, together with those needed to replace retirees, are expected to exceed the number of graduates for decades to come For first career position for routine work under the supervision of experienced analysts, Eventual assignment of more complex tasks and greater autonomy to design models and solve problems, Analysts advance by assuming positions as technical specialists and supervisors. Furthermore, for Long-Term Prospects, The skills acquired by O.R. analysts are useful for a variety of higher level management jobs, consequently, experienced analysts can leave the profession to assume non-
14
technical managerial or administrative positions, Analysts with significant experience may become professors and consultants. Related occupation that closely need operation research approaches are Systems analyst, Defense analyst, Database administrator, Computer scientist, Computer programmer, Engineers, Mathematician, Forecaster, Materials manager, Quality & Reliability manager, Statistician, Economist, Market researcher, IT manager, Consultant, Logistician, Technology director, Financial analyst, Risk analyst, and Project manager. Table 1 shows a result of
operation
research
concept
analysis
on
Sample
Job
Titles
&
Compensation.
Table 1 Sample Job Titles & Compensation. Title
Median Salary
Experience
Analyst – Level I
$50,913.00
0-3 years
Analyst – Level III
$80,472.00
4-7 years
Analyst – Level V
$130,772.00
8-10 years
Manager
$143,451.00
10+ years
Operation management Specialist – Level I
$32,886.00
0-2 years
Opns Unit Manager
$46,154.00
5+ years
Opns Manager
$81,527.00
8+ years
Opns Director
$141,591.00
10+ years
Top Opns Executive
$232,865.00
15+ years
Specialist – Level I
$32,886.00
0-2 years
Source: http://swz.salary.com/salarywizard - Spring 2009
15
Operations research has been applied to a wide variety of situations, and has had a dramatic impact on the effectiveness of many organizations A small sampling of the many successful applications include the following. Burger King uses linear programming to determine how
different cuts of
meat should be blended together to produce hamburger patties at minimum cost while still meeting certain specifications such as fat content, texture, freshness, and shrinkage. As the cost of different cuts of meat changes, the firm reevaluates its model to determine whether its recipe should be modified. Scheduling aircraft crews is a complex problem involving such factors as the type of aircraft to be flown, the cities of origination and termination for the flight, the intermediary cities visited by the aircraft, and the length of the flight. Federal and union rules govern the placement of personnel on the aircraft. To address these issues, American Airlines has developed an integer linear programming model that allows the company to quickly determine an optimal flight schedule for its personnel. The marriage of the microprocessor with the Global Positioning Satellite System has enabled Sony Corporation to develop an onboard navigation system capable of giving directions to a car’s driver. This information is especially valuable during traffic conditions such as rush hour congestion. The software is based on an operations research model known as a shortest path network. Following the California earthquake in January 1994, Interstate 10, a main freeway serving the Los Angeles area, needed to be rebuilt quickly. The project prime contractor was given a fairly short reopen the roadway. To encourage
5 month deadline to
the work to be done as quickly as
possible, the contractor was offered a bonus of $500,000.00 for each day by which it was able to beat the deadline. Using a project scheduling technique known as the critical path method , the contractor was able to schedule work crews so as to be able to complete the repair work a month earlier than the project deadline. As a result, the contractor collected a $15 million dollar
16
bonus. Mrs. Fields operates a nationwide chain of cookie shops specializing in fresh-baked chocolate chip cookies. The chain has equipped each shop with a PC-based information system to aid personnel in deciding when additional cookies should be baked and the amounts that should be produced. This system relies on the operations research techniques of demand forecasting and inventory modeling. Lines form as visitors of Disneyland & Disneyworld await their turn to ride or view the most popular attractions.
Disney incorporates waiting
overall design plans for the park.
line or queuing models into its
These models mirror customer behavior
and tolerance for waiting in line. As a result, Disney developed an entirely new “industry” of waiting line entertainment to maintain customer satisfaction levels and enhance the value and excitement of the ride or attraction. NYC handles over 20,000 tons of garbage per day. To dispose of this trash, the city operates 3 incinerators. Refuse is also sent by barge from marine transfer stations to the Fresh Kills Landfill. To determine future operational plans for this landfill, the Department of Sanitation undertook an operations research analysis. The result was development of the BOSS (barge operation systems simulation) model. This simulation model enabled the department to determine the number of additional barges that should be purchased to handle future demands. It also helped plan the dispatching of these barges. During the 1970s, U.S. automobile manufacturers saw a steady decline in their market share due to competition from Japanese and European manufacturers. In response, Ford Motor Co. embarked on a “Quality Is Job One” campaign. Suppliers were held to tighter standards, and new quality control procedures were developed. As a result of these quality management activities, the firm was able to reverse its decline in market share and profitability. Concept of operation research shows successfully applied at work. Table 2 shows that various big companies have successfully make a big deal of annual saving.
17
Table 2 Successful companies applied concept of operation research Company
Year
Hewlett Packard
1998
Taco Bell
1998
Proctor & Gamble
1997
Delta Airlines
1994
AT&T
1993
Yellow Freight Systems, Inc. San Francisco Police Dept. Bethlehem Steel North American Van Lines
1992 1989
Designing buffers into production line Employee scheduling Redesign production & distribution system Assigning planes to routes
Techniques Used Queuing models IP, Forecasting, Simulation Transportation models
Integer Programming Queuing models, Call center design Simulation Network models, Design trucking network Forecasting, Simulation Patrol Scheduling Linear Programming
1989
Design an Ingot Mold Stripper Integer Programming
1988
Assigning loads to drivers Network modeling
Citgo Petroleum
1987
United Airlines
1986
Dairyman's Creamery Phillips Petroleum
Problem
Refinery operations & Linear Programming, distribution Forecasting Scheduling reservation LP, Queuing, Forecasting personnel
Annual Savings $280 million $13 million $200 million $100 million $750 million $17.3 million $11 million $8 million $2.5 million $70 million $6 million
1985
Optimal production levels Linear Programming
$48,000
1983
Equipment replacement Network modeling
$90,000
18
Operations Research Time Line: 1.
1890s: Frederick Taylor applies the scientific approach to improving operations in production (industrial engineering)
2.
1900s: Henry Gantt develops control charts for minimizing machine job completion times (project scheduling) Andre Markov studies how systems change over time.
3.
1910s: Ford Harris develops approaches to determine the optimal inventory quantity to order (inventory theory) E.K. Erlang develops a formula for determining the average waiting time for telephone callers (queuing theory)
4.
1920s: William Shewhart introduces the concept of control charts. Dodge and Romig develop the technique of acceptance sampling (quality control)
5.
1930s: John von Neuman and Oscar Morgenstern develop strategies for evaluating competitive situations (game theory)
6.
1940s: World War II provides the impetus for the application of Mathematical modeling for solving military problems. George Dantzig develops the simplex method for solving Problems with a linear objective and constraints (linear programming)
7.
1950s: a. Harry Kuhn determines required conditions for optimality for problems with a nonlinear structure (nonlinear programming) b. Ralph Gomory develops a solution procedure for problems in which some
variables
are
required
to
be
integer
valued
(integer
programming) PERT and CPM are developed (project scheduling) c. Richard Bellman develops a methodology for solving
multistage
decision problems (dynamic programming)
19
8.
1960s: John Little proves a theoretical relationship between the average length of a waiting line and the average time a customer spends in line (queuing theory) Specialized simulation languages such as SIMSCRIPT and GPSS are developed (simulation)
9.
1970s: The microcomputer is developed
10. 1980s: N. Karmarkar develops a new procedure for solving large-scale linear programming problems (LP). The personal computer is developed Specialized OR software packages that can run on microcomputers are developed 11. 1990s: Spreadsheet packages begin to play a major role in modeling and solving management science models TIMS and ORSA merge to form the Institute for Operations Research and Management Science (INFORMS) As the 21st century begins, there is overwhelming evidence that major organizations are looking for individuals in all disciplines who have strong quantitative, computer, and communications skills. Operations research, with its emphasis on all these areas, as well as its direct application to problems of optimization and efficiency, is recognized as an important element in a wellrounded business education.
20
CHAPTER 2: INTRODUCTION TO FOUNDATION DATION MATHEMATICS AND STAT STATISTICS MODELING
LP definition, Linear programming (LP, or linear optimization) is a mathematical method for determining a way to achieve the the best outcome (such as maximum profit or lowest cost) in a given mathematical model for some list of requirements represented as linear relationships. Linear programming is a specific case of mathematical programming (mathematical optimization). More formally, mally, linear programming is a technique for the optimization of a linear objective function, subject to linear equality and linear inequality constraints. Its feasible region is a convex polyhedron, which is a set defined as the intersection of finitely many many half spaces, each of which is defined by a linear inequality. Its objective function is a real-valued real valued affine function defined on this polyhedron. A linear programming algorithm finds a point in the polyhedron where this function has the smallest (or largest) largest) value if such a point exists. Linear programs are problems that can be expressed in canonical form
: where x represents the vector of variables (to be determined), c and b are vectors of (known) coefficients, A is a (known) matrix of coefficients, and (.)T is the matrix transpose. The expression to be maximized or minimized is called the objective function (cTx in this case). The inequalities Ax ≤ b and x ≥
21
0 are the constraints which specify a convex polytope over which the objective function is to be optimized. In this context, two vectors are comparable when they have the same dimensions. If every entry in the first is less-than or equal-to the corresponding entry in the second then we can say the first vector is less-than or equal-to the second vector. The mathematical technique LP is used for analysing optimum decisions subject to certain constraints in the form of linear inequalities. Mathematically it applies to those problems which require the solution of maximisation problems subject to a system of linear inequalities stated in terms of certain variables. If and b, the two variables are the function of c, the value of c is maximised when any movement from that point results in a decreased value of c. The value of c is minimised when even a small movement results in an increased value of c. An illustration could explain us the model of linear programming. Let us consider a linear programming problem and solve it by algebraic method. An important thing that has to be understood is to ascertain the given problem as linear programming, is to write the objective function and the constraints in the form of equations or inequalities.
Illustration 1 Presume an industry manufactures two commodities M1 and M2. Each unit of commodity M1 supplies $30 to profit and each unit of commodity M2 donates $40 to profits. The manufacture of these commodities requires inputs X, Y and Z and their available volume are 14, 10 and 4 relatively. Assumed that the manufacture of one commodity M1 procures 2 units of input X, 1 unit of input Y and does not require input Z and the manufacture of one unit of commodity M2 requires 2 units of input X, 2 units of Y and 4 units of Z. Derivate the above problem into linear programming and solve it with algebraic method.
22
Solution First we shall convert the above write-up as linear equations in order to determine solution. 1. Objective Function –> π = 30M1 + 40M2 2. Input X Constraint –> 2M1 + 2M2 ≤ 14 3. Input Constraint Y –> M1+ 2M2 ≤ 10 4. Input Constraint Z –> M2 ≤ 4 5. Non- Negative Constraint –> M1, M2 ≥ 0 With respect to solve these linear equation problems by algebraic method we first ascertain possible area and its intense points. This is represented in the below diagram which could give us a graphical solution to the equation.
Three constraint lines XY, ZI and JL denotes input constraints have been constructed to obtain the region JKPY as the possible area. There are three J, K, P and Y corner points or intense points of this possible area. The intense point J is ascertained by only one constraint of input Z and according to it 4 units of commodity M2 and no amount of M1 are produced. Substituting this in profit function we get profits at intense point J.
23
Thus profits at intense point J = 30 x 0 + 40 x 4 = $160 Hence J =160 At intense point Y, 7 units of commodity M1 and no unit of commodity M2 are manufactured. Thus π at intense point Y = 30 x 7 + 40 x 0 = $210 Hence Y = 210 The intense point K is ascertained by the intersections constraints of inputs Y and Z. As will be noted from the possible area, according to the intense point K, 4 units of commodity M2 are manufactured. To get the quantity manufactured of commodity M1, we substitute M2 = 4 in the constraint equation of input Y. Thus M1 + 2 x 4 = 10 M1 = 10 – 8 = 2 Now with M1 = 2, and M2 = 4, at the intense point K, profits are π = 30 M1 + 40 M2 = 30 x 2 + 40 x 4 = 60 +160 = 220
Hence K = 220
Let us take the intense point P, which is ascertained by intersection of the constraints of inputs X and Y. The productivity of two commodities at intense point be got by solving the constraints equation of input X and Y. Thus we get, 2M1 + 2M2 = 14
…………….Equation (1)
1M1 + 2M2 = 10
…………….Equation (2)
If we deduct the Equation (2) from Equation (1), we get the following, M1 = 4 Now we have to substitute the value of M1 in the Equation (2), we obtain 4 + 2M2 = 10 2M2 = 6 M2 = 3
24
Thus at intense point P, 4 units of commodity M1 and 3 units of commodity M2 are manufactured. With these productivities of M1 and M2 profits are: π = 30 M1 + 40 M2 = 30 x 4 + 40 x 3 = 120 + 120 = 240;
Hence, P = 240
Now after ascertaining the profits earned in the intense points, we are going to present the tablet containing productivities at intense points with their respective profits.
Productivities and Revenue Earned at Different Intense points of the Possible Area Intense Points
Productivities of
Revenue earned
Commodities M1 and
Value in $
M2 P
M1 = 4; M2 = 3
240
Y
M1 = 7; M2 = 0
210
K
M1 = 2; M2 = 4
220
J
M1 = 0; M2 = 4
160
Intense P represents the optimum or profit maximising productivities of two commodities, such as 4 units of commodity M1 and 3 units of Commodity M2. Intense Y represents the optimum or profit maximising productivities of two commodities, such as 7 units of commodity M1 and 0 units of Commodity M2. Intense K represents the optimum or profit maximising productivities of two commodities, such as 2 units of commodity M1 and 4 units of Commodity M2. Intense J represents the optimum or profit maximising productivities of two commodities, such as 0 units of commodity M1 and 4 units of Commodity M2.
25
Quantification of factors
Linear programming can be applied to various fields of study. It is used in business and economics, but can also be utilized for some engineering problems.
Industries
that
use
linear
programming
models
include
transportation, energy, telecommunications, and manufacturing. It has proved useful in modeling diverse types of problems in planning, routing, scheduling, assignment, and design. Linear programming is a considerable field of optimization for several reasons. Many practical problems in operations research can be expressed as
linear
programming
problems.
Certain
special
cases
of
linear
programming, such as network flow problems and multicommodity flow problems are considered important enough to have generated much research on specialized algorithms for their solution. A number of algorithms for other types of optimization problems work by solving LP problems as sub-problems. Historically, ideas from linear programming have inspired many of the central concepts of optimization theory, such as duality, decomposition, and the importance of convexity and its generalizations. Likewise, linear programming is heavily used in microeconomics and company management, such as planning, production, transportation, technology and other issues. Although the modern management issues are ever-changing, most companies would like to maximize profits or minimize costs with limited resources. Therefore, many issues can be characterized as linear programming problems.
Standard form Standard form is the usual and most intuitive form of describing a linear programming problem. It consists of the following three parts: •
A linear function to be maximized
26
e.g. •
Problem constraints of the following form e.g.
•
Non-negative negative variables
e.g.
The problem is usually expressed in matrix form,, and then becomes:
Other forms, such as minimization problems, problems with constraints on alternative forms, as well as problems involving negative variables can always be rewritten into an equivalent problem in standard form. form
Example Suppose that a farmer has a piece of farm land, say L km2, to be planted with either wheat or barley or some combination of the two. The farmer has a limited amount of fertilizer, F kilograms, and insecticide, P kilograms. Every square kilometer of wheat requires F1 kilograms of fertilizer, and P1 kilograms of insecticide, while every square kilometer of barley requires F2 kilograms of fertilizer, and P2 kilograms of insecticide. Let S1 be the selling price of wheat per square kilometer, and S2 be e the selling price of barley. If we denote the area of land planted with wheat and barley by x1 and x2 respectively, then profit can be maximized by choosing optimal values for x1 and x2. This
27
problem can be expressed with the following linear programming problem in the standard form: (maximize the revenue— —revenue is the Maximize:
"objective function")
Subject
(limit on total area)
to:
(limit on fertilizer) (limit on insecticide) (cannot plant a negative area). Which in matrix form becomes: become
maximize
subject to
Augmented form (slack form) Linear programming problems must be converted into augmented form before being solved
by
the simplex
algorithm.
This
form
introduces
nonnon
negative slack variables to replace inequalities with equalities in the constraints. The problems can then be written in the following block matrix form: Maximize Z:
x, xs ≥ 0
28
where xs are the newly introduced slack variables, and Z is the variable to be maximized. Example The example above is converted into the following augmented form: for Maximize: S1x1 + S2x2
(objective function)
Subject to: x1 + x2 + x3 = L
(augmented constraint)
F1x1 + F2x2 + x4 = F (augmented constraint) P1x1 + P2x2 + x5 = P (augmented constraint) x1, x2, x3, x4, x5 ≥ 0. where x3, x4, x5 are (non-negative) (non slack lack variables, representing in this example the unused area, the amount of unused fertilizer, and the amount of unused insecticide. In matrix form this becomes: Maximize Z:
Duality Every linear programming problem, referred to as a primal problem, can be converted into a dual problem, problem, which provides an upper bound to the optimal
29
value
of
the
primal
problem.
In
matrix
form,
we
can
express
the primal problem as: Maximize cTx subject to Ax ≤ b, x ≥ 0; with
the
corresponding symmetric dual
problem,
Minimize bTy subject
to ATy ≥ c, y ≥ 0. An alternative primal formulation is: Maximize cTx subject to Ax ≤ b;
with
the
corresponding asymmetric dual
problem,
Minimize bTy subject to ATy = c, y ≥ 0. There are two ideas fundamental to duality theory. One is the fact that (for the symmetric dual) the dual of a dual linear program is the original primal linear program. Additionally, every feasible solution for a linear program gives a bound on the optimal value of the objective function of its dual. The weak duality theorem states that the objective function value of the dual at any feasible solution is always greater than or equal to the objective function value of the primal at any feasible solution. The strong duality theorem states that if the primal has an optimal solution, x*, then the dual also has an optimal solution, y*, such that cTx*=bTy*. A linear program can also be unbounded or infeasible. Duality theory tells us that if the primal is unbounded then the dual is infeasible by the weak duality theorem. Likewise, if the dual is unbounded, then the primal must be infeasible. However, it is possible for both the dual and the primal to be infeasible (See also Farkas' lemma). Example Revisit the above example of the farmer who may grow wheat and barley with the set provision of some L land, F fertilizer and P insecticide. Assume now that unit prices for each of these means of production (inputs) are set by a planning board. The planning board's job is to minimize the total cost of procuring the set amounts of inputs while providing the farmer with a floor on the unit price of each of his crops (outputs), S1 for wheat and S2 for barley. This corresponds to the following linear programming problem:
30
(minimize ze the total cost of the Minimize:
means of production as the "objective function")
Subject
(the farmer must receive no less
to:
than S1 for his wheat) (the farmer must receive no less than S2 for his barley) (prices cannot be negative). Which in matrix form becomes:
Minimize:
Subject to: The primal problem deals with physical quantities. With all inputs available in limited quantities, and assuming the unit prices of all outputs is known, what quantities of outputs to produce so as to maximize total revenue? The dual problem deals with economic values. With floor guarantees on all output unit prices, and assuming the available quantity of all inputs is known, what input unit pricing scheme to set so as to minimize total expenditure? To each variable in in the primal space corresponds an inequality to satisfy in the dual space, both indexed by output type. To each inequality to satisfy in the primal space corresponds a variable in the dual space, both indexed by input type. The coefficients that bound the inequalities in the primal space are used to compute the objective in the dual space, input quantities in this
31
example. The coefficients used to compute the objective in the primal space bound the inequalities in the dual space, output unit prices in this example. Both the primal and the dual problems make use of the same matrix. In the primal space, this matrix expresses the consumption of physical quantities of inputs necessary to produce set quantities of outputs. In the dual space, it expresses the creation creation of the economic values associated with the outputs from set input unit prices. Since each inequality can be replaced by an equality and a slack variable, this means each primal variable corresponds to a dual slack variable, and each dual variable corr corresponds esponds to a primal slack variable. This relation allows us to speak about complementary slackness. Another example Sometimes, one may find it more intuitive to obtain the dual program without looking at the program matrix. Consider the following linear pr program: minimize
subject to
,
, , We have m + n conditions and all variables are non-negative. non negative. We shall define m + n dual variables: yj and si. We get: minimiz e subject to
,
32
, , , Since this is a minimization problem, problem, we would like to obtain a dual program that is a lower bound of the primal. In other words, we would like the sum of all right hand side of the constraints to be the maximal under the condition that for each primal variable the sum of its coefficients do not exceed its coefficient in the linear function. For example, x1 appears in n + 1 constraints. If we sum its constraints' coefficients we get a1,1y1 + a1,2y2 + ... + a1,nyn + f1s1. This sum must be at most c1. As a result we get: maximize
subject to
,
, , Note that we assume in our calculations steps that the program is in standard form. However, any linear program may be transformed to standard form and it iss therefore not a limiting factor.
LP and allocation of resources Linear programming is a widely used model type that can solve decision problems with many thousands of variables. Generally, the feasible values of the decisions are delimited by a set of constraints that are described by
33
mathematical functions of the decision variables. The feasible decisions are compared using an objective function that depends on the decision variables. For a linear program the objective function and constraints are required to be linearly related to the variables of the problem. The examples in this section illustrate that linear programming can be used in a wide variety of practical situations. We illustrate how a situation can be translated into a mathematical model, and how the model can be solved to find the optimum solution.
Resource Allocation Problem (will be discussed in detail in the next chapter) The type of problem most often identified with the application of linear program is the problem of distributing scarce resources among alternative activities. The Product Mix problem is a special case. In this example, we consider a manufacturing facility that produces five different products using four machines. The scarce resources are the times available on the machines and the alternative activities are the individual production volumes. The machine requirements in hours per unit are shown for each product in the table. With the exception of product 4 that does not require machine 1, each product must pass through all four machines. The unit profits are also shown in the table. The facility has four machines of type 1, five of type 2, three of type 3 and seven of type 4. Each machine operates 40 hours per week. The problem is to determine the optimum weekly production quantities for the products. The goal is to maximize total profit. In constructing a model, the first step is to define the decision variables; the next step is to write the constraints and objective function in terms of these variables and the problem data. In the problem statement, phrases like "at least," "no greater than," "equal to," and "less than or equal to" imply one or more constraints.
34
Machine data and processing requirements (hrs./unit) Machine
Quantity Product 1 Product 2 Product 3 Product 4 Product 5
M1
4
1.2
1.3
0.7
0.0
0.5
M2
5
0.7
2.2
1.6
0.5
1.0
M3
3
0.9
0.7
1.3
1.0
0.8
M4
7
1.4
2.8
0.5
1.2
0.6
Unit profit, $
——
18
25
10
12
15
Variable Definitions
Pj : quantity of product j produced, j = 1,...,5 Machine Availability Constraints The number of hours available on each machine type is 40 times the number of machines. All the constraints are dimensioned in hours. For machine 1, for example, we have 40 hrs./machine ¥ 4 machines = 160 hrs. M1 : 1.2P1 + 1.3P2 + 0.7P3 + 0.0P4 + 0.5P5 < 160 M2 : 0.7P1 + 2.2P2 + 1.6P3 + 0.5P4 + 1.0P5 < 200 M3 : 0.9P1 + 0.7P2 + 1.3P3 + 1.0P4 + 0.8P5 < 120 M4 : 1.4P1 + 2.8P2 + 0.5P3 + 1.2P4 + 0.6P5 < 280
Non negativity Pj > 0 for j = 1,...,5 Objective Function The unit profit coefficients are given in the table. Assuming proportionality, the profit maximization criterion can be written as: Maximize Z = 18P1+ 25P2 + 10P3 + 12P4 + 15P5
35
Solution The model constructed with the Math Programming add-in is shown below. The model has been solved with the Jensen LP add-in. We note several things about the solution. 1. The solution is not integer. Although practical considerations may demand that only integer quantities of the products be manufactured, the solution to a linear programming model is not, in general, integer. To obtain an optimum integer answer, one must specify in the model that the variables are to be integer. The resultant model is called an integer programming model and is much more difficult to solve for larger models. The analyst should report the optimal solution as shown, and then if necessary, round the solution to integer values. For this problem, rounding down the solution to: P1 = 59, P2 = 62, P3 = 0, P4 = 10 and P5 = 15 will result in a feasible solution, but the solution may not be optimal. 2. The solution is basic. The simplex solution procedure used by the Jensen LP add-in will always return a basic solution. It will have as many basic variables as there are constraints. As described elsewhere in this site, basic variables are allowed to assume values that are not at their upper or lower bounds. Since there are four constraints in this problem, there are four basic variables, P1, P2, P4 and P5. Variable P3 and the slack variables for the constraints are the nonbasic variables. 3. All the machine resources are bottlenecks for the optimum solution with the hours used exactly equal to the hours available. This is implied by the fact that the slack variables for the constraints are all zero. 4. This model does not have lower or upper bounds specified for the variables. This is an option allowed with the Math Programming add-in. When not specified, lower bounds on variables are zero, and upper bounds are unlimited.
36
The sensitivity analysis amplifies the solution. The analysis shows the results of changing one parameter at a time. While a single parameter is changing, all other problem parameters are held constant. For changes in the limits of tight constraints, the values of the basic variables must also change so that the equations defining the solution remain satisfied.
Variable Analysis •
The "reduced cost" column indicates the increase in the objective function per unit change in the value of the associated variable. The reduced costs for the basic variables are all zero because the values of these variables are uniquely determined by the problem parameters and cannot be changed.
•
The reduced cost of P3 indicates that if this variable were increased from 0 to 1 the objective value (or profit) will decrease by $13.53. It is not surprising that the reduced cost is negative since the optimum value of P3 is zero. When a non basic variable changes, the basic variables change so that the equations defining the solution remain satisfied. There is no information from the sensitivity analysis on how the basic variables
37
change or how much P3 can change before the current basis becomes infeasible. Note that the reduced costs are really derivatives that indicate the rate of change. For degenerate solutions (where a basic variable is at one of its bounds) the amount a nonbasic variable may change before a basis change is required may actually be zero. •
The ranges at the right of the display indicate how far the associated objective coefficient may change before the current solution values (P1 through P5) must change to maintain optimality. For example, the unit profit on P1 may assume any value between 13.26 and 24.81. The "---" used for the lower limit of P3 indicates an indefinite lower bound. Since P3 is zero at the optimum, reducing its unit profit by any amount will make it even less appropriate to produce that product.
Constraint Analysis •
A shadow price indicates the increase in the objective value per unit increase of the associated constraint limit. The status of all the constraints are "Upper" indicating that the upper limits are tight. From the table we see that increasing the hour limit of 120 for M3 increases the objective value by the most ($8.96), while increasing the limit for M4 increases the objective value by the least ($0.36). Again, these quantities are rates of change. When the solution is degenerate, no change may actually be possible.
•
The ranges at the right of the display indicate how far the limiting value may change while keeping the same optimum basis. The shadow prices remain valid within this range. As an example consider M1. For the solution, there are 160 hours of capacity for this machine. The capacity may range from 99.35 hours to 173 hours while keeping the same basis optimal. Changes above 120 cause an increase in profit of $4.82 per unit,
38
while changes below 120 cause a reduction in profit by $4.82 per unit. As the value of one parameter changes, the other parameters remain constant and the basic variables change to keep the equations defining the solution satisfied.
General Resource Allocation Model It is common to describe a problem class with a general algebraic model where numeric values are represented by lower case letters usually drawn from the early part of the alphabet. Variables are given alphabetical representations generally drawn from the later in the alphabet. Terms are combined with summation signs. The general resource allocation model is below. When the parameters are given specific numerical values the result is an instance of the general model.
39
Linearity requirement
A system is called linear if it has two mathematical properties: homogeneity and additivity. If you can show that a system has both properties, then you have proven that the system is linear. Likewise, if you can show that a system doesn't have one or both properties, you have proven that it isn't linear. A third property, shift invariance, is not a strict requirement for linearity, but it is a mandatory property for most DSP techniques. When you see the term linear system used in DSP, you should assume it includes shift invariance unless you have reason to believe otherwise. These three properties form the mathematics of how linear system theory is defined and used. Later in this chapter we will look at more intuitive ways of understanding linearity. For now, let's go through these formal mathematical properties.
40
As illustrated in Fig. 5-2, homogeneity means that a change in the input signal's amplitude results in a corresponding change in the output signal's amplitude. In mathematical terms, if an input signal ofx[n] results in an output signal of y[n], an input of kx[n] results in an output of ky[n], for any input signal and constant, k
A simple resistor provides a good example of both homogenous and non-homogeneous systems. If the input to the system is the voltage across the resistor, v(t), and the output from the system is the current through the resistor, i(t) , the system is homogeneous. Ohm's law guarantees this; if the voltage is increased or decreased, there will be a corresponding increase or decrease in the current. Now, consider another system where the input signal is the voltage across the resistor, v(t), but the output signal is the power being
41
dissipated in the resistor, p(t). Since power is proportional to the square of the voltage, if the input signal is increased by a factor of two, the output signal is increase by a factor of four. This system is not homogeneous and therefore cannot be linear. The property of additivity is illustrated in Fig. 5-3. Consider a system where an input of x1[n] produces an output of y1[n]. Further suppose that a different input, x2[n], produces another output, y2[n]. The system is said to be additive, if an input of x1[n] + x2[n]results in an output of y1[n] + y2[n], for all possible input signals. In words, signals added at the input produce signals that are added at the output.
The important point is that added signals pass through the system without interacting. As an example, think about a telephone conversation with your Aunt Edna and Uncle Bernie. Aunt Edna begins a rather lengthy story about how well her radishes are doing this year. In the background, Uncle Bernie is
42
yelling at the dog for having an accident in his favorite chair. The two voice signals are added and electronically transmitted through the telephone network. Since this system is additive, the sound you hear is the sum of the two voices as they would sound if transmitted individually. You hear Edna and Bernie, not the creature, Ednabernie. A good example of a nonadditive circuit is the mixer stage in a radio transmitter. Two signals are present: an audio signal that contains the voice or music, and a carrier wave that can propagate through space when applied to an antenna. The two signals are added and applied to a nonlinearity, such as a pn junction diode. This results in the signals merging to form a third signal, a modulated radio wave capable of carrying the information over great distances. As shown in Fig. 5-4, shift invariance means that a shift in the input signal will result in nothing more than an identical shift in the output signal. In more formal terms, if an input signal of x[n] results in an output of y[n], an input signal of x[n + s] results in an output of y[n + s], for any input signal and any constant, s. Pay particular notice to how the mathematics of this shift is written, it will be used in upcoming chapters. By adding a constant, s, to the independent variable, n, the waveform can be advanced or retarded in the horizontal direction. For example, when s = 2, the signal is shifted left by two samples; when s = -2, the signal is shifted right by two samples.
43
Shift invariance is important because it means the characteristics of the system do not change with time (or whatever the independent variable happens to be). If a blip in the input causes a blop in the output, you can be assured that another blip will cause an identical blop. Most of the systems you encounter will be shift invariant. This is fortunate, because it is difficult to deal with systems that change their characteristics while in operation. For example, imagine that you have designed a digital filter to compensate for the degrading effects of a telephone transmission line. Your filter makes the voices sound more natural and easier to understand. Much to your surprise, along comes winter and you find the characteristics of the telephone line have changed with temperature. Your compensation filter is now mismatched and doesn't work especially well. This situation may require a more sophisticated algorithm that can adapt to changing conditions.
44
Why do homogeneity and additivity play a critical role in linearity, while shift invariance is something on the side? This is because linearity is a very broad concept, encompassing much more than just signals and systems. For example, consider a farmer selling oranges for $2 per crate and apples for $5 per crate. If the farmer sells only oranges, he will receive $20 for 10 crates, and $40 for 20 crates, making the exchange homogenous. If he sells 20 crates of oranges and 10 crates of apples, the farmer will receive: . This is the same amount as if the two had been sold individually, making the transaction additive. Being both homogenous and additive, this sale of goods is a linear process. However, since there are no signals involved, this is not a system, and shift invariance has no meaning. Shift invariance can be thought of as an additional aspect of linearity needed when signals and systems are involved.
Assignment-1 (Homework) A Manufacture of five products i.e.: P1 to P5. Each unit of commodity P1 supplies $50 to profit, P2 supplies $40, P3 supplies $60, P4 Supplies 20 and each unit of product P5 donates $40 to profits. The manufacture of these products requires inputs A, B, C and D and their available volume are 80, 15, 50, and 20 relatively. Assumed that the manufacture of one product P1 procures 5 units of input A, 2 unit of input B, 2 unit of input C, and 2 unit of input D. Product P2 procures 7 units of input A, 3 unit of input B, 2 unit of input C, and 3 unit of input D. Product P3 procures 1 units of input A, 0 unit of input B, 5 unit of input C, and 5 unit of input D. Product P4 procures 0 units of input A, 0 unit of input B, 9 unit of input C, and 11 unit of input D. and product P5 procures 15 units of input A, 2 unit of input B, 0 unit of input C, and 5 unit of input D. Derivate the above problem into linear programming and solve it with algebraic method.
45
CHAPTER 3: EXPRESSING LINIER PROGRAMMING PROBLEMS Limitations or constraints Linear programming has turned out to be a highly useful tool of analysis for the business executives. It is being increasingly made use of in theory of the firm, in managerial economics, in inter regional trade, in general equilibrium analysis, in welfare economics and in development planning.
However, there are limitations and they are discussed below. 1. It is complex to determine the particular objective function 2. Even if a particular objective function is laid down, it may not be so easy to find out various technological, financial and other constraints which may be operative in pursuing the given objective. 3. Given a Specified objective and a set of constraints it is feasible that the constraints may not be directly expressible as linear inequalities. 4. Even if the above problems are surmounted, a major problem is one of estimating relevant values of the various constant co-efficient that enter into a linear programming mode, i.e. prices etc. 5. This technique is based on the hypothesis of linear relations between inputs and outputs. This means that inputs and outputs can be added, multiplied and divided. But the relations between inputs and outputs are not always clear. In real life, most of the relations are non-linear. 6. This technique presumes perfect competition in product and factor markets. But perfect competition is not a reality.
46
7. The LP technique is based on the hypothesis of constant returns. In reality, there are either diminishing or increasing returns which a firm experiences in production. 8. It is a highly mathematical and complicated technique. The solution of a problem
with
linear
programming
requires
the
maximisation
or
minimisation of a clearly specified variable. The solution of a linear programming problem is also arrived at with such complicated method as the simplex method which comprises of a huge number of mathematical calculations. 9. Mostly, linear programming models present trial and error solutions and it is difficult to find out really optimal solutions to the various economic complexities.
Types of Constraints in Linear Programming Problems This handout describes the most common types on constraints found in linear programming problems. It should help you in developing your modeling skills. Due to the wide range of applications, any or all of these constraints might appear in a given problem. While most constraints fall into one of these broad classes, exceptions do occur. For all constraints, make sure the left-hand-side units (e.g., pounds, dollars, etc.) are consistent with the right-hand-side units. If the units do not agree, the constraint cannot be correct. 1. Lower and upper bounds on the values of the decision variables. Example: x1 ≥ 10 (lower limit) x2 ≤ 25 (upper limit) Note: The standard non-negativity conditions (≥0) are a special case of lower bounds.
47
2. Limitation constraints (usually ≤ constraints). These are often used to model limited resources, such as time, units of material, money, etc. Example:
3x1 + 5x2 + 2x3 ≤ 50
Description: 50 units of the resource are available. Product 1 requires 3 units of the resource, product 2, 5 units, and product 3, 2 units. 3. Requirement constraints (usually ≥ or = constraints).
These are
sometimes referred to as covering constraints. They are used to model a requirement which much be satisfied, such as satisfying the requirements of a contract, forcing the investment of all money in a portfolio, or requiring an advertising campaign to reach a certain number of viewers. Examples: a. x1 + x2 + x3 = 10 Total production must equal 10 units, in any combination of product 1, 2, and 3. b. 300x1 + 500x2 ≥ 60,000 Advertising campaign must reach 60,000 people, where medium 1 reaches 300 people per ad, and medium 2, 500 people. 4. Ratio
constraints.
Also,
weighted
average
and
percentage
constraints are very similar. Relationship can be ≤, =, or ≥. These are used to model situations where the value of one (or more) variable, compared with the value of another (one or more) variable, must satisfy some relationship. Examples: a. x1/x2 ≥ 2 That is, the ratio of x1 to x2 must be at least 2. This constraint can occur when a certain product mix ratio is desired between
48
two products. This is the same as the constraint x1≥2x2; that is, the value of x1 must be at least twice the value of x2. The constraint can also be written as x1 – 2x2 ≥ 0. b. x1/(x1+x2+x3) ≤ 0.25 That is, the ratio of x1 to the sum of x1, x2, and x3 must be no more than 0.25. Another way of thinking of this is that x1 can comprise at most 25% of the total of x1, x2, and x3. This situation is very common in blending problems, where "recipes" may have a certain amount of flexibility. This type of constraint is also very useful in portfolio investment problems, where one wants to stay within certain asset allocation guidelines (for example, at most 25% of total portfolio should be invested in bonds). c. (15x1+35x2)/(x1+x2) ≥ 20 This is a constraint on the weighted average of x1 and x2, where the weights are 15 and 35, respectively. Suppose car 1 gets 15 miles per gallon (mpg) and car 2, 35 mpg. There is an EPA requirement that the weighted average mpg of all cars sold by a company be at least 20. This constraint models this requirement. Note: Avoid the common error of dividing by the number of variables (2, in this case) instead of the sum of the variables (x1+x2). Caution. Be careful implementing ratio, weighted average, and percentage constraints in Excel. The reason is that these constraints can be written in different forms, some which are linear and some which are nonlinear. Even though they are algebraically equivalent, the nonlinear form will
49
cause problems with Solver's "Assume Linear Model option.
If one
implements a constraint in a nonlinear form, the Solver message "The conditions for Assume Linear Model are not satisfied" will be received. Therefore, decide how you're going to implement these constraints before constructing the spreadsheet model. Taking each example in turn, a. x1/x2 ≥ 2 is nonlinear because x1 is divided by x2, another decision variable. The linear forms of this constraint are x1 ≥ 2x2 and
x1 - 2x2 ≥ 0
Either one of these can be implemented in Excel/Solver. b. x1/(x1+x2+x3) ≤ 0.25 is nonlinear. The linear forms are: x1 ≤ 0.25*(x1 + x2 + x3) x1 ≤ 0.25x1 + 0.25x2 + 0.25x3 or
0.75x1 - 0.25x2 - 0.25x3 ≤ 0
c. (15x1+35x2)/(x1+x2) ≥ 20 is nonlinear. The linear forms are: 15x1 + 35x2 ≥ 20*(x1+x2) or
-5x1 + 15x2 ≥ 0
Keep in mind that two main purposes of a spreadsheet model are to facilitate analysis, and to enhance communication. Choose an implementation of these constraints which provides the best balance of these two sometimes conflicting objectives. 5. Balance Constraints. These are used to model processes where the "inputs" must equal the "outputs." For example, the process of carrying inventory is modeled with a balance constraint. The process of a warehouse receiving product from several sources and sending product out to multiple destinations is another process which must be balanced. Example: I1 + P2 - S2 = I2 Beginning inventory (end of month 1) plus current (month 2) production, less month 2 sales, equals ending month 2 inventory.
50
Often (but not always), balance constraints can be implemented directly in the spreadsheet as formulas, and do not have to be explicitly stated to Solver.
51
CHAPTER 4: INVENTORY MODEL Persediaan merupakan aset yang sangat mahal dan penting dalam sebuah perusahaan yang mewakili sekitar 50%total investasi. Oleh karenanya
pengengalian
persediaan
manajerial
yang
krusial.
sangat
merupakan
Pengendalian
sebuah persediaan
keputusan ini
akan
mempengaruhi pengendalianefektifitas dan efisiensi keuangan. Persediaan (inventory) merupakan sumberdaya cadangan yang digunakan untuk memenuhi kebutuhan saat ini maupun waktu yang akan datang. Contoh inventory misalnya adalah raw material, work in proces dan barang jadi. Level persediaan untuk barang jadi merupakan fungsi langsung dari adanya permintaan. Berbagai macam perusahaan memiliki sistem persediaan yang berbeda. Misalnya persediaan Bank dalam bentuk cash, Rumah sakit dalam bentuk persediaan darah atau obat misalnya.
Sistem perencanaan dan pengendalian persediaan:
Rencana persediaan yang harus disediakan dan bagaimana mendapatkannya
Perhitungan permintaan (Demand)
Pengnedalian level persediaan
Feedback
52
Pentingnya pengendalian persediaan 1.
The
Decopupling
Function.
Jika
kita
tidak
mempersiapkan
persediaan maka akan terjadi keterlambatan (delay) dan in efisiensi dalam sebuah proses, kaarena proses akan berhenti menunggu raw material –misalnya- tersedia untuk diproses. 2.
Storing Resources. Bahan makanan atau hasil bumi biasanya ada yang memiliki musim panen tertentu. Padahal kebutuhan atau permintaan pasar tidak musiman. Oleh karenanya dibutuhkan persediaan
sumberdaya.
Sumberdaya
itu
ity
sendiri
dapat
terseimpan dalam bentuk proses kerja. Misalnya di sebuah gudang terdapat 100 mobil dan 1000 roda. Maka persediaan roda sejumlah 100x4 ditambah dengan 1000. 3.
Irregular Supply and Demand. Jika permintaan dan persediaan tidak tetap, maka menyediakan sejumlah barang permintaan sangatlah penting.
Misalnya adanya perbedaan perbedaaan
permintaan ssatu barang di musim hujan yang berbeda dengan ketika musim kemarau. 4.
Quantity Discount. Jika sebuah pemesanan barang dalam jumlah tertentu akan mendapatkan diskon, maka melakukan pemesanan barang sejumlah tertentu yang tidak harus sesuai dengan kebutuhan saat ini harus diperhitungkan dengan baik.
5.
Avoiding Stockout and Shortages. Memiliki persediaan untuk permintaan costumer adalah hal yang sangat mahal. Oleh karenanya jangan sampai customer kehilangan kepercayaan ketika kita tidak bisa memberikan kebutuhannya.
53
Keputusan Persediaan How much to Order When to order Tujuan model persediaan adalah untu meminimalisasikan biaya persediaan yang terdiri dari: 1. Cost of item 2. cost of ordering 3. cost of carrying or holding inventory 4. cost of safety stock 5. cost of stockout
EOQ, mendifinisikan berapa banyak pemesanan Teknik ini di dipublikasikan oleh Ford W. Harris tahun 1915 dan masih digunakan banyak organisasi saat ini. Teknik ini mudah dalam pemakaiannya namun harus memiliki asumsu tertentu yaitu: 1. Permintaan diketahui dan konstan 2. The Lead time, yaitu waktu penempatan dan penerimaan order diketahui dan konstan 3. persediaan dari saat kedatangan dalam satu angkutan dan dalam satu waktu tertentu. 4. tidak ada diskon 5. biaya variabelnya terdiri dari placing cost, ordering cost dan carrying cost. 6.
jika permintaan datang pada waktu yang tepat, maka tidak terjadi kekosongan persediaan.
54
Inventory Level
Inventory Cost Tujuan model persediaan adalah untuk meminimalisasi biaya persediaan. Hal ini didapatan pada pemesanan sejumlah order tertentu time (optiomal) yang terjadi saat kurva ccarrying cost sama dengan ordering cost.
Biaya
Total Cost Carrying cost Ordering Cost Jumlah order
55
Menentukan EOQ
2.D.Co Ch
Q* =
Q* = Jumlah optimal pemesanan D = Demand Co = Ordering Cost of pieces per order Ch = Carrying cost per unit per year Jika carrying cost (Ch) diketahui dalam bentuk prosentase (I)
dari harga
barang (P)maka Ch = IP
Contoh: Sebuah perusahaan manufacture tiap tahun memiliki permintaan sejumlah 1000 unit. Biaya order sebesar $10 per order dan rata-rata caarrying costnya sebesar $0,50 per tahun. Berapa biaya inventori tiap tahunnya? Jumlah optimal pemesanan untuk 1000 unit adalah:
Q* =
Q* =
2.D.Co Ch 2.1000.10 0.50
= 200 unit
Biaya inventory untuk 1000 unit adalah:
TC =
D Co + Q Ch Q 2
56
TC =
1000 200 10 + 0 . 50 200 2
= $100
Jika Q yang diambil lebih atau kurang darri 200 unit maka Total Costnya akan lebih besar dari $100.
ROP, Menentukan kapan dilakukan pemesanan ROP = Demand per day x Leadtime untuk order baru (dalam hari) ROP = d x L Contoh . Sebuah perusahaan komputer memiliki permintaan 8000 chips tiap tahun. Permintaah
hariannya
adalah
40
unit.
Rata-rata
pengiriman
order
membutuhkan waktu 3 hari kerja. Maka ROPnya adalah ROP = d x L = 40 x 3 = 120 unit.
EOQ dengan asumsi tanpa penerimaan yang tak tentu
Inventory Level
t
time
57
Menentukan annual caarrying cost = ½ maximum inventory level x Ch = ½ x Q(1-d/p) x Ch Q = number of pieces per order or production run Ch = carrying cost per year p= daily production rate d= daily demand rate t = lenght of production run in day Q = pt
Menentukan annual setup cost atau Annual ordering cost
Annual setup cost =
D Cs Qp
D Co Annual Ordering cost = Q D = Annual Demand in units Qp = Quantity produce in one batch Cs = Setup cost per setup
Menentukan Optimal Order Quantity dan Production quantity
Optimal Order Quantity =
2.D.Co d Ch 1 − p
58
Production quantity =
2.D.Cs d Ch 1 − p
Contoh: Perusahaan manufacture memproduksi mesin pendingin dalam satu satuan. Perusahaan memprediksikan menghasilkan 10.000 unit dalam setahun. Biaya pembuatannya $100 dan carrying cost sebesar 50 sen per unit per tahun. Hasil yang diperoleh dari proses adalah 80 unit sehari. Selama proses produksi
mampu
menghasilkan
60
unit
tiap
hari.
Perusahaan
ini
memproduksi 167 hari tiap tahun. Berapa produksi yang dihasilkan tiap satu satuan? Berapa lama putaran produksi tiap produknya?
Production quantity =
Qp =
2.D.Cs d Ch 1 − p
2.10000unit.$100 60unit $0.51 − 80unit
= 4.000 unit
Lama putaran produksi = Q/p = 4000/80 = 50 hari. Oleh karenanya alat produksi harus di set untuk menghasilkan 50 hari produksi.
59
Model Diskon jumlah Rumusan Total cost = Material cost + ordering cost + carrying cost
TC = DC +
Total Biaya
D Q Co + Ch Q 2
Diskon 2
Diskon 1
Diskon 3 Q* untuk Diskon 2
Contoh: Sebuah toko menjual mainan dengan harga $5. jika pembelian 1000-1999 unit maka akan mendapat diskon sehingga harganya $4.8 per unit. Dan untuk pembelian lebih dari 2000 harga per unit menjadi $4.75 per unit. Biaya order $49 per order. Permintaah mainan tiap tahun sebanyak 5000 unit. Carrying cost adalah 20% harga barang. Berapa total cost minimum untuk mendapatkan EOQ?
Q1=
2.D.Co IP
=
2.5000.49 0.2(5) =700 mainan per order
60
Q2=
Q3=
2.D.Co IP 2.D.Co IP
=
=
2.5000.49 0.2(4.8) =714 mainan per order
2.5000.49 0.2(4.75) =718 mainan per order
Penyesuaian dengan diskon. Maka: Q1 = 700 unit. (tidak ada penyesuaian) Q2 = 1000 unit. (penyesuaian diskon 1) Q3 = 2000 unit. (penyesuaian diskon 2)
Annual Material cost (DC) Dx C1 = 5000 x $5.00 = $ 25,000 Dx C2 = 5000 x $4.80 = $ 24,000 Dx C3 = 5000 x $4.75 = $ 23,750
Annual Ordering Cost =
D Co Q1 D Co Q2
D Co Q
=
5000 49 =350 700
=
5000 49 1000 =245
61
D Co Q3
=
5000 49 2000 =122.5
Annual Carrying Cost =
Q Ch 2
700 Q Ch 1 = (0.2 x$5) = $ 350 2 2 Q 700 Ch 2 = (0.2 x$4.8) = $ 48 2 2 Q 700 Ch 3 = (0.2 x$4.7) = $ 950 2 2
Total Cost = Annual Material cost (DC) + Annual Ordering Cost
Annual Carrying Cost
D Co Q
+
Q Ch 2
TC1= $25,000 + $350.0 + $350 = $25,700,0 TC2= $24,000 + $245.0 + $480 = $24,725,0 TC3= $23,750 + $122.5 + $950 = $24,822.5
Pemakaianan safety stock Dengan saaafety stock akan menghilangkan ketidaktersediaan barang, sehingga ada ekstra stok dimiliki.
62
Penganan safety stok terbaik adalah dipergunakan untuk menentukan reorder poin. ROP = d x L Sehingga dengan adanya safeaty stok ini maka ROP = d x L + SS dimana SS = Safety stok
Reorder point dengan biaya ketidaktersediaan yang telah diketahui. •
penting diketahui probabilitas demand
•
biaya ketersediaan dihitung per unit
•
targetnya meminimalisir total cost
contoh: Carrying cost $5, stockout cost per unit $40. Optomal order per year 6. Number of units 30 40 50 60 70
Probability 0.2 0.2 0.3 0.2 0.1 1.0
Biaya ketidaktersediaan (stockout). Jika ROP 30 unit. Pada demand 40 unit = (40unit-30unit)x$40x6 order per year = $2,400 Pada demand 50 unit = (50unit-30unit)x$40x6 order per year = $4,800 Pada demand 60 unit = (60unit-30unit)x$40x6 order per year = $7,200 Pada demand 70 unit = (70unit-30unit)x$40x6 order per year = $9,600
63
Carrying cost Jika ROP 30 unit. Pada demand 40 unit = (40unit-30unit)x$5 = $50 Pada demand 50 unit = (50unit-30unit)x$5 = $100 Pada demand 60 unit = (60unit-30unit)x$5 = $150 Pada demand 70 unit = (70unit-30unit)x$5 = $200
EMV =
{(probabilitas)i x (alternatives result)i}
4320 = 0.2x0 + 0.2x2400 + 0.3x4800 + 0.2x7200 + 0.1x9600 Probability Alternatives 30 40 50 60 70
$ $ $ $ $
0,20 30 50 100 150 200
0,20 40 $ 2.400 $ $ 50 $ 100 $ 150
0,30 50 $ 4.800 $ 2.400 $ $ 50 $ 100
0,20 60 $ 7.200 $ 4.800 $ 2.400 $ $ 50
0,10 70 $ 9.600 $ 7.200 $ 4.800 $ 2.400 $ -
$ $ $ $ $
EMV 4.320,00 2.410,00 990,00 305,00 110,00
Safety stok dengan biaya yang tidak diketahui Untuk menentukan safety stok digunakan servis level dan distribusi normal. Service level = 1 – probability of a stockout Contoh: Sebuah perusahaan diketahui data statistik demand dalam periode tertentu adalah 350 unit untuk rata-rata demand dengan standar deviasi 10 Berapa safety stok yang harus di kendalikan?
64
Jika dipakai kurva normal 5% maka nilai service level, Z pada titik 1-5% = 0.95 adalah 1.65
SS Z=
σ
=1.65
Maka SS = 1.65 x 10 = 16.5 unit = 17 unit (pembulatan) ABC Analisys Tujuan analysis ABC adalah untuk membedakan perusahaan seluruh jenis persediaan perusahaan dalam 3 grup, A, B dan C. Kemudian sesuai dengan masing-masing grup ditentukan level persediaan yang akan di kendalikan secara umum. Analisis ini untuk membedakan tingkat kepentingan masingmasing item persediaan yang di kelola. Misal: Grup
Dolar usage (%)
A B C
70 20 10
Inventory item (%) 10 20 70
Quantitaitive control used? Yes In some cases no
Analysis sensitivitas Perhitungan ini digunakan jika terjadi perubahan variable dalam perhitungan EOQ
Assignment-2 (Homework) An Operation Research text book is sold at $5 price. When student buys for 200-299 pieces, he/she will get a discount of $5 each, and buy more than 300 pieces will have $5.5 discount each. The ordering cost is $.5 each ordered. This book store has to supply 1500 pieces yearly with carrying cost 20% of prices. Count for minimum cost gaining EOQ?
65
CHAPTER 5: TRANSPORTATION MODEL
Pendahuluan Metode
ini
adalah
sebuah
metode
yang
dapat
memberikan
penyelesaian lebih efisien dalam hal prosedur perhitungan dari pada model simplex. Perhitungan ini adalah bagian dari network flow problem. Model transportasi dapat diartikan sebagai distribusi dari sebuah barang ke tujuan-tujuan tertentu. Tujuan perhitungan ini adalah untuk penjadwalan
pengiriman
ke
masing-masing
tujuan
sehingga
biaya
transportasi dan produksi dapat diminimalkan. Sedang model assignment dapat diartikan sebagai penugasan seseorang pada proyek tertentu, sales ke wilayah tertentu, kontrak ke penawar tertentu, dan lain sebagainya, dengan tujuan meminimalisir total cost atau total waktu yang diperlukan dalam penyelesaian tugas. Karakteristik yang dimiliki oleh model assignment adalah satu orang hanya untuk satu pekerjaan tertentu, dst.
Seting up transportation problems Problem transportasi dapat dideskripsikan dengan “bagaimana untuk memilih rute pengiriman dan jumlah bagian yang dikirim tiap rute” untuk meminimalisasi biaya total transportasi.
Nortwest corner rule Contoh: Biaya transportasi dan kapasitas
66
Pabrik (Kapasitas) D (100) E (300) F (300)
Gudang tujuan (Kapasitas) A (300) B (200) C (200) $5 $4 $3 $8 $4 $3 $9 $7 $5
Distribusi barang
Pabrik (Kapasitas) D (100) E (300) F (300)
Gudang tujuan (Kapasitas) A (300) B (200) C (200) 100 200 100 100 200
Jumlah biaya D-A
100 unit x $5 = $ 500
E-A
200 unit x $8 = $1,600
E-B
100 unit x $4 = $ 400
F-B
100 unit x $7 = $ 700
F-C
200 unit x $5 = $1,000
Total
$4,200
Stepping stone method: mencari biaya terkecil Jumlah rute dilalui = jumlah kolom + jumlah baris – 1 Contoh diatas jumlah rute dilalui 5 = 3 + 3+ 1 Jika jumlah rute kurang dari jumlah rute yang dilalui maka solusinya dinamakan dengan degenerate.
67
Menguji hasil untuk peningkatan yang memungkinkan. Langkah: 1.
pilih
kotak/jalur
yang
tidak
digunakan
(DB-DC-EC-FA)
untuk
dievaluasi 2.
dengan dimulai dari jalur ini, telusuri jalur dengan jalur tertutup melewati jalur yang sebenarnya/terpakai.
3.
Di jalur yang tidak terpakai, berilah tanda plus. Kemudian jalur selanjutnya tanda minus dan seterusnya sesuai dengan jalur yang di kalkulasikan.
4.
hitung improvement index dengan menambahkan unit cost sesuai jalur dengan tanda plus atau minus.
5.
Ulangi tahap 1-4 untuk tiap jalur kosong yang ada. Jika dihasilkan nilai sama atau lebih dari nol, maka solusi optimalnya dapat diketahui. Namun jika ada yang kurang dari nol maka memungkinkan untuk meningkatkan hasil sebelumnya dan mengurangi total shipping cost.
Contoh:
Pabrik (Kapasitas) D(100) E(300) F(300)
Gudang tujuan (Kapsitas) A(300) B(200) C(200) 100 200 100 100 200
+ DB-DA+EA-EB = +4-5+8-4 = +$3
68
Pabrik (Kapasitas) D(100) E(300) F(300)
Gudang tujuan (Kapsitas) A(300) B(200) C(200) 100 200 100 100 200
+EC-EB+FB-FC = +3-4+7-5 = +$1
Pabrik (Kapasitas) D(100) E(300) F(300)
Gudang tujuan (Kapsitas) A(300) B(200) C(200) 100 200 100 100 200
+DC-DA+EA-EB+FB-FC = +3-5+8-4+7-5 = +$4
Pabrik (Kapasitas) D(100) E(300) F(300)
Gudang tujuan (Kapsitas) A(300) B(200) C(200) 100 200 100 100 200
+FA-FB+EB-EA = +9-7+4-8 = -$2
Dengan adanya nilai improvement index kurang dari nol ini, maka cost saving mungkin akan bisa didapat dari FA. Dalam kasus ini indek negatif terdapat dalam satu rute, jika terdapat lebih dari satu indek maka diambil nilai indek negatif terbesar.
69
Langkah selanjutnya adalah menentukan jumlah unit maksimum yang akan melalui rute baru ini (nilai indek minimal terbesar) Untuk itu ditentukan terlebih dahulu cell FA dengan tanda plus, dst. Dalam kasus diambil nilai pengiriman terkecil, karena kita menginginkan pengirian dalam jumlah besar oleh karena itu cell FA dengan nilai -100 dihilangkan dan ditambahkan (yang memungkinkan) ke cell EB. Sehingga hasilnya didapat:
Pabrik (Kapasitas) D(100) E(300) F(300)
Gudang tujuan (Kapsitas) A(300) B(200) C(200) 100 100 200 100 200
maka indek yang terjadi
Pabrik (Kapasitas) D(100) E(300) F(300)
Gudang tujuan (Kapsitas) A(300) B(200) C(200) $5 $4 $3 $8 $4 $3 $9 $7 $5
D ke B = Indek DB = +4-5+8-4=+$3 D ke C = Indek DC = +3-5+9-5=+$2 E ke C = Indek EC = +3-8+9-5= -$1 F ke B = Indek FB = +7-4+8-9=+$2
Sehingga dapat dilakukan improvement pada jalur EC. Jalur EC diberikan 100 unit. Sehingga FA mendapat tambahan 100 unit. Dan terjadi pengurangan 100 unit di FC.
70
Pabrik (Kapasitas) D(100) E(300) F(300)
Gudang tujuan (Kapsitas) A(300) B(200) C(200) 100 200 100 200 100
maka indek yang terjadi
Pabrik (Kapasitas) D(100) E(300) F(300)
Gudang tujuan (Kapsitas) A(300) B(200) C(200) $5 $4 $3 $8 $4 $3 $9 $7 $5
D ke B (jalur DB-DA-FA-FC-EC-EB-DB) Indek DB = +4-5+9-5+3-4=+$2 D ke C (jalur DC-DA-FA-FC-FC) Indek DC = +3-5+9-5=+$2 E ke A (jalur EA-FA-FC-EC-EA) Indek EA = +8-9+5-3=+$1 F ke B (jalur FB-FC-EC-EB-FB) Indek FB = +7-5+3-4=+$1
Sampai langkah ini didapat seluruh indek lebih besar dari nol, sehingga posisi jalur ini sudah merupakan hasil yang optimal.
Total Cost yang didapat. Rute DA 100 unit x $5 = $ 500
71
Rute EB 200 unit x $4 = $ 800 Rute EC 100 unit x $3 = $ 300 Rute FA 200 unit x $9 = $ 1,800 Rute FC 100 unit x $5 = $ 500 Total
$ 3,900
MODI method Langkah: Jika R adalah row atau baris dan K adalah kolom dan C adalah biaya yang terjadi di jalur tersebut, maka: 1.
Ri + Kj = Cij, dimana hanya dihitung pada jalur yang terpakai
2.
kemudian anggap R1 = 0
3.
Hitung sistem rumusan pada semua nilai R dan K
4.
hitung indek pada tiap jalur tidak terpakai dengan rumusan I(ij) = C(ij)-RiKj
5.
Pilih indek negatif terbesar, dan teruskan dengn perhitungan seperti rumusan metode stepping stone.
Contoh: Distribusi barang
Pabrik (Kapasitas) D(100) E(300) F(300)
Gudang tujuan (Kapsitas) A(300) B(200) C(200) 100 200 100 100 200
72
Pabrik (Kapasitas) D(100) E(300) F(300)
Gudang tujuan (Kapsitas) A(300) B(200) C(200) $5 $4 $3 $8 $4 $3 $9 $7 $5
maka: R1+K1 = 5 R2+K1 = 8 R2+K2 = 4 R3+K2 = 7 R3+K3 = 5 Jika R1=0, maka K1=5, R2=3, K2=1,R3=6,K3=-1.
Kemudian indek yang didapat pada jalur kosong: Jalur DB (R1K2) = C12-R1-K2 = $4-$0-$1=+$3 Jalur DC (R1K3) = C13-R1-K3 = $3-$0-$1=+$2 Jalur EC (R2K3) = C23-R2-K3 = $3-$3-$1=+$2 Jalur FA (R3K1) = C31-R3-K1 = $9-$6-$5 =-$2
Hasil ini sama dengan perhitungan dengan metode pendekatan stepping stone.
Vogels approximation metod (VAM) Metode Vogels approximation metod (VAM) merupakan metode yang tidak sesimpel nortwest corner namun dapat memberikan solusi yang optimal.
73
Metode ini dapat memberikan gambaran biaya tiap alternati rute. Langkah perhitungan VAM:
1.
tentukan perbedaan antara biaya pengiriman terendah. Perbedaan ini menggambarakan perbedaan antara biaya distribusi pada ruter terbaik dalam kolom atau baris dengan rute terbaik keduanya. Misalnya dari tabel dibawah diketahui untuk baris E, 2 biaya terendah adalah $3 dan $4, sehingga memilki perbedaan $1. Kolom A, 2 biaya terendah adalah $8 dan $5, sehingga memilki perbedaan $3.
Pabrik (Kapasitas) D(100) E(300) F(300)
2.
3 0 0 Gudang tujuan (Kapsitas) A(300) B(200) C(200) $5 $4 $3 $8 $4 $3 $9 $7 $5
1 1 2
identiikasikan baris atau kolom dengan peluang biaya terbesar, dalam tabel diatas maka kolom A memiliki perbedaan terbesar, yaitu 3
3.
berilah tanda dengan unit, untuk kolom atau baris termurah. Misal kolom A memiliki biaya termurah di baris B, $5, diberikan 100 unit sesuai dengan kapasitas pabrik D.
4.
Beri tanda X pada baris yang kolom pada baris yang sudah terisi.
Pabrik (Kapasitas) D(100) E(300) F(300)
Gudang tujuan (Kapsitas) A(300) B(200) C(200) 100 x x
74
5.
Menghitung kembali perbedaan biaya dengan pertimbangan hasil eliminasi kolom atau baris terisi
Pabrik (Kapasitas) D(100) E(300) F(300)
6.
1 3 2 Gudang tujuan (Kapsitas) A(300) B(200) C(200) 100 x x $8 $4 $3 $9 $7 $5
1 2
hitung kembali dari langkah ke-2.
Kapasitas Gudang tujuan (Kapasitas) A(300) B(200) C(200) Pabrik D(100) 100 X X x 200 100 E(300) 200 X 100 F(300) a. Seperti dalam kasus ini,maka peluang biaya terbesar di kolom B (3). Masukkan berapa unit yang akan dikirim pada baris yang memungkinkan yaitu pada baris dengan biaya termurah (baris E, $4, lebih kecil dari baris F, $7), yaitu di baris E, dengan kapasitas maksimal (kolom B(200), baris E(300)), yaitu 200 unit,yaitu kapasitas maksimal gudang B.
Kapasitas Pabrik D(100) E(300) F(300)
1 3 2 Gudang tujuan (Kapasitas) A(300) B(200) C(200) 100
X
X
8 9
200
3 5
X
1 5 4
b. Tentukan kembali perbedaan biaya yang terjadi (Baris E, $5) . kemudian pada kolom termurah, yaitu kolom C, $3.
75
masukan kapasitas maksimal pada kolom dan baris ini yaitu 100 unit, dari 300unit kapasitas pabrik E-200 unit yang tersalur ke gudang B.
Kapasitas Pabrik D(100) E(300) F(300)
Gudang tujuan (Kapasitas) A(300) B(200) C(200) 100
X
X
8 9
200
100
X
5
c. Dari tabel diatas maka akan diketahui sell FA (300-100) dan FC (20-100) serta FB (300-200-100)
Sehingga dapat diketahui biaya penugasan VAM sebesar : Kapasitas Pabrik D(100) E(300) F(300)
Kapasitas Pabrik D(250) E(300) F(300)
Gudang tujuan (Kapasitas) A(300) B(200) C(200) 5 4 3 8 4 3 9 7 5
Gudang tujuan (Kapasitas) A(300) B(200) C(200) Dummy $5 $4 $3 $0 $8 $4 $3 $0 $9 7 $5 $0
-
100 unit x $5 = $500
-
200 unit x $4 = $800
-
100 unit x $3 = $300
-
200 unit x $9 = $1,800
-
100 unit x $5 = $500
-
Total $ 3,900
76
unbalance transportation problems Hal ini terjadi jika permintaan tidak sama dengan supply. -
Supply > demmand = dummy destination (warehouse/surplus)
-
Supply < demmand = dummy source (factory)
Kasus ini akan mengakibatkan koeisien biaya pengiriman akan nol.
Supply > demmand = dummy destination
Contoh. Jika kapasitas pabrik D menjadi 250 unit, sehingga total supply menjadi 850 unit. Sedangkan kapasitas gudang tetap, 700 unit. Untuk menseimbangkan permasalahan ini maka dibuat dummy column, dengan kapasitas 850 unit – 700 unit = 150 unit.
Kapasitas Pabrik D(250) E(300) F(300)
Kapasitas Pabrik D(250) E(300) F(300)
Gudang tujuan (Kapasitas) A(300) B(200) C(200) $5 $4 $3 $8 $4 $3 $9 7 $5
Gudang tujuan (Kapasitas) A(300) B(200) C(200) Dummy 250 50 200 50 150 150
Perhitungan total biaya adalah: 250 unit x $ 5 = $1,250 50 unit x $ 8 = $ 400 200 unit x $ 4 = $800 50 unit x $ 3 = $150 150 unit x $ 5 = $750
77
150 unit x $ 0 = $0 Total $ 3,350
Supply < demmand = dummy source Untuk mengantisipasi hal ini dibutuhkan dummy plant. Contoh: Jika terjadi jumlah permintaan (500 unit) lebih dari supply (400 unit) maka dibutuhkan dummy plant dengan kapasitas 50 unit. Kapasitas Pabrik D(200) E(175) F(75) Dummy (50)
Gudang tujuan (Kapasitas) A(250) B(100) C(150) $6 $4 $9 $10 $5 $8 $12 $7 $6 $0 $0 $0
Kapasitas Pabrik D(200) E(175) F(75) Dummy (50)
Gudang tujuan (Kapasitas) A(250) B(100) C(150) 200 50 100 25 75 50
sehingga total costnya sebesar: 200 unit x $ 6 = $1,200 50 unit x $ 10 = $ 500 100 unit x $5 = $500 25 unit x $ 8 = $200 75 unit x $ 6 = $450 50 unit x $ 0 = $0 Total $ 2,850
78
Degeneracy in transportation problem ini muncul jika rute<ΣK+ΣR-1. Untuk perhitungannya maka kita harus meletakkan angka nol pada sel yang tidak terpakai dalam jalur, sehingga seolah-olah jalur tersebut dipakai/dilalui. Contoh kasus:
Kapasitas Pabrik D(100) E(120) F(80)
Gudang tujuan (Kapasitas) A(100) B(100) C(100) 100 100 20 80
Dalam tabel terlihat, rute<ΣK+ΣR-1 4<3=3-1 dari tabel maka sel DB atau EA dapat dianggap sebagai jalur. Kemudian dihitung seperti hitungan sebelumnya.
Degeneracy during later solution stage. Permasalahan transportasi dapat terjadi penurunan jika eliminasi dua rute yang dilalui ditambahkan pada jalur yang tidak terpakai. Seperti dalam soal 2 jalur yang diberi tanda minus pada satu jalur tertutup (sel DB dab DE) memiliki jumlah unit yang sama (nol)
Pilihan solusi yang lebih dari satu pilihan Permasalahan transportasi memmungkinkan memberikan beberapa solusi dalam arti bahwa jalur transportasi yang didapatkan bisa lebih daru satu alternatif untuk satu total biaya yang sama.
79
Analisis Lokasi fasilitas Model transportasi bisa digunakan untuk membantu menentukan lokasi gudang atau pabrik baru yang akan dibangun untuk memenuhi kebutuhan perusahaan.
Contoh: Sebuah perusahaan memiliki tiga lokasi pabrik dan 4 lokasi gudang. Gudang Tujuan (Kapasitas) Pabrik A B C D 10000 12000 15000 9000 (Kapasitas) E 15000 25 55 40 60 F 6000 35 30 50 40 G 14000 36 45 26 66 Lokasi pabrik alternatif 60 38 65 27 H 35 30 41 50 I
Production Cost 48 50 52 53 49
jawaban Gudang Tujuan (Kapasitas) Pabrik
A
B
C
D
(Kapasitas)
10000
12000
15000
9000
E
15000
73
103
88
108
F
6000
85
80
100
90
G
14000
88
97
78
118
H
113
91
118
80
I
84
79
90
99
Lokasi pabrik alternatif
80
11
10
10
Gudang Tujuan (Kapasitas) Pabrik
A
B
C
(Kapasitas)
10000
12000
15000
9000
10000
103
88
108
E
15000
D
F
6000 x
80
100
90 10
G
14000 x
97
78
118 19
H
x
91
118
80 11
11
10
Gudang Tujuan (Kapasitas) Pabrik
A
B
C
(Kapasitas)
10000
12000
15000
9000
10000
103
88
108
80
100
E
15000
F
6000 x
G
14000 x
H
x
D
90 10
14000 x
x 91
80 11
118
Gudang Tujuan (Kapasitas) Pabrik
A
B
C
(Kapasitas)
10000
12000
15000
9000
10000
103
88
108
E
15000
F
6000 x
G
14000 x
H
x
D
6000 x
x
14000 x
x 91
118
80 11
81
Gudang Tujuan (Kapasitas) Pabrik
A
B
C
(Kapasitas)
10000
12000
15000
10000
103
1000
E
15000
F
6000 x
G
14000 x
H
x
6000 x
D 9000 108 5 x
14000 x
x
80 11
91 x
Gudang Tujuan (Kapasitas) Pabrik
A
B
C
(Kapasitas)
10000
12000
15000
10000
4000
E
15000
F
6000 x
G
14000 x
H
x
D 9000
1000 x
6000 x
x
14000 x
x
9000
2000 x
Alternatif ke 2 Gudang Tujuan (Kapasitas) Pabrik
A
B
C
D
(Kapasitas)
10000
12000
15000
9000
1000
4000
E
15000
F
6000
G
14000
H
10000 6000
14000 2000
9000
82
Total Cost dari kedua alternatif adalah Alternatif 1 $ 3.704.000 Alternatif 2 $ 3.741.000 Sehingga dipilih lokasi alternatif pertama untuk pembuatan pabrik baru.
83
CHAPTER 6: ASSIGNMENT MODEL Minimization
Permasalahan penugasan ini biasanya ditunjukkan dalam sebuah matrik dimana kolom yang ada menggambarkan tujuan dari sebuah penunjukan dan baris yang ada menunjukkan penunjukkan subyek yang mendapatkan penugasan tersebut.
Contoh: Ada tiga buah proyek yang akan dikerjakan oleh tiga orang
Petugas
Biaya Proyek Gudang Tujuan (Kapasitas) Typing Editing Printing A $11 $14 $6 B $8 $10 $11 C $9 $12 $7
Alternatif Biaya yang muncul denganberbagai alternatif penugasan: Gudang Tujuan Gudang Tujuan (Kapasitas) (Kapasitas) Typing Editing Printing Typing Editing Printing A B C $11 $10 $7 A C B $11 $12 $11 B A C $8 $14 $7 B C A $8 $12 $6 C A B $9 $14 $11 C B A $9 $10 $6
$28 $34 $29 $26 $34 $25
Dalam contoh diatas kemungkinanyang muncul adalah 6 kemungkinan. Atau 6 kemungkinan ini diadapat dari tiga penugasan, yaitu 3! (tiga faktorial),
84
3!=3x2x1. bisa dibayangkan jika matrik yang terjadi ada 10 baris – 10 kolom, maka kemungkinan yang muncul adalah 10!=10x9x8x7x6x5x4x3x2x1 atau akan terjadi kemungkinan sebanyak 3.628.800 kemungkinan! Untuk mempermudah perhitungn dan mendapatkan kemungkinan penugasan yang menghasilkan biaya yang paling rendah, dengan metode hungarian (Flood’s technique)
Langkah-langkah perhitungan: 1. Menyusun tabel biaya dari permasalahan yang disajikan 2. mencari biaya peluang a. kurangkan nilai terendah untuk tiap baris b. kurangkan nilai terendah untuk tiap kolom 3. menguji tabel biaya untuk melihat penugasan yang paling optimal dengan menggambarkan garis minimum yang memungkinkan dalam kolom atau baris yang di kover nilai nol 4. jika hasilnya optimal (jumlah garis = jumlah baris atau jumlah kolom). Solusi yang optimal terletak pada nilai nol a. uji tiap barus dan kolom untuk nilai nol dan berilah penugasan pada persilangan tersebut b. eliminasi kolom dan baris pada nilai nol yang lain, buat penugasan selanjutnya 5. jika hasil tidak optimal. Revisi peluan biaya pada langkah kedua a. kurangkan nilai terendah untuk yang tidak terkover oleh garis dari tempat tersebut untuk setiap bilai yang tidak terkover b. tambahkan nomor ini pada tiap persimpangan dari dua garis
85
contoh:
Petugas
Biaya Proyek Gudang Tujuan (Kapasitas) Typing Editing Printing A $11 $14 $6 B $8 $10 $11 C $9 $12 $7
Langkah 1 pengurangan dalam setiap baris, dengan nilai terendah pada tiap baris
Petugas
Biaya Proyek Gudang Tujuan (Kapasitas) Typing Editing Printing A $6 $11 $14 B $8 $10 $11 C $7 $9 $12
Petugas
Hasil pengurangan Gudang Tujuan (Kapasitas) Typing Editing Printing A $0 $5 $8 B $0 $2 $3 C $2 $5 $0
Petugas
Kemudian dikurangkan dengan nilai terendah masing-masing kolom Gudang Tujuan (Kapasitas) Typing Editing Printing A $0 $5 $6 B $0 $0 $3 C $2 $3 $0
86
Dari nilai nol diatas diartikan sebagai: -
C ditugaskan menangani proyek 3 (C3=0)
-
B ditugaskan menangani proyek 1 (B1=0) atau ditugaskan menangani proyek 2 (B2=0)
-
A ditugaskan menangani proyek 3 (A3=0)
Dari perhitungan ini kita belum bisa memberikan penugasan kepada ketiga orang tersebut. Untuk itu dari tabel diatas dibuat garis melalui seluruh nilai nol yang ada dalam tabel. Jika jumlah garis yang terjadi sama dengan jumlah baris atau jumlah kolom, maka hal ini manunjukkan penugasan yang paling optimal (menghasilkan biaya yang paling rendah).
Sehingga dari permasalah diatas garis pemotong yang terjasi adalah:
Ternyata garis yang memotong nilai nol hanya berjumlah 2 garis (kurang dari jumlah baris atau jumlah kolom), sehingga komposisi seperti ini belum menghasilkan penugasan yang optimal. Sehingga perlu dilakukan revisi tabel, dengan cara mengurangkan semua nilai yang terkover pada tabel terakhir (A1, A2, C1, C2) dengan nilai terkecil dari nilai yang tidak terkover tersebut (nilai 2 di C1) dan menambahkan nilai terkecil tersebut pada nilai yang tidak terkover (nilai 3 di B3).
87
Petugas
Gudang Tujuan (Kapasitas) Typing Editing Printing A $0 $3 $4 B $0 $0 $5 C $0 $1 $0 Kemudian dibuat garis yang memotong nilai nol yang ada:
Garis yang memotong ini jumlahnya ada 3 garis (sama dengan jumlah baris atau jumlah kolom). Posisi seperti ini menunjukkan bahwa penugasan yang terjadi (nilai nol menunjukkan adanya kemungkinan penugasan) akan menghasilkan biaya terendah (penugasan optimal), yaitu: •
A ditugaskan menangani proyek 3 (A3=0)
•
B ditugaskan menangani proyek 1 (B1=0) atau ditugaskan menangani proyek 2 (B2=0)
•
C ditugaskan menangani proyek 3 (C3=0) atau ditugaskan menangani proyek 1 (C1=0)
Sehingga kesimpulannya adalah A menangani proyek 3, C menangani proyek 1 dan B menangani proyek 2, sehingga biaya yang dikeluarkan:
Petugas
Biaya Proyek Gudang Tujuan (Kapasitas) Typing Editing Printing A $11 $14 $6 B $8 $10 $11 C $9 $12 $7
88
A3 = $6, B2 = $10, dan C1 = $9 sehingga jumlahnya adalah $25
Dummy Row dan Dummy Colums Hal ini terjadi jika jumlah kolom tidak sama dengan jumlah baris. Hal ini dapat dijembatani dengan menambahkan kolom baru atau menambahkan baris baru untuk menyamakan jumlah kolom dan jumlah baris dalam matrik yang ada.
MAKSIMALISASI PENUGASAN
Kasus yang terjadi dilapangan tidak hanya meminimalisir biaya, namun juga kasus memaksumalkan keuntungan ateu meningkatkan efisiensi. Oleh karenanya perhitungan ini diperlukan untuk menentukan hasil yang dimaksudkan. Tahap perhitungan dimulai dengan menentukan nilai tertinggi dari seluruh nilai dalam tabel. Nilai ini digunakan untuk mencari selisih dengan seluruh nilai yang ada dalam tabel tersebut.
Contohnya. Jika beberapa proyek dikerjakan oleh beberapa petugas akan mendatangkan keuntungan tertentu. Maka untuk mendapatkan total keuntungan terbesar, langkah yang dilakukan adalah menentukan nilai tertinggi dalam tabel tersebut, kemudian mengurangkannya dengan nilai-nilai yang ada di setiap
Petugas
sel tabel tersebut.
1 2 3 4
A $20 $60 $80 $65
Proyek B C $60 $50 $30 $80 $100 $90 $80 $75
D $55 $75 $80 $70
89
Petugas
Petugas
1 2 3 4
1 2 3 4
A $20 $60 $80 $65
A $80 $40 $20 $35
Proyek B C $60 $50 $30 $80 $100 $90 $80 $75 Proyek B C $40 $50 $70 $20 $0 $10 $20 $25
D $55 $75 $80 $70
D $45 $25 $20 $30
Kemudian setiap baris diambil nilai yang paling kecil, yang kemudian
Petugas
Petugas
digunakan untuk mengurangi semua nilai dalam baris tersebut.
1 2 3 4
1 2 3 4
A $80 $40 $20 $35
Proyek B C $40 $50 $70 $20 $0 $10 $20 $25
A $40 $20 $20 $15
Proyek B C D $0 $10 $5 $50 $0 $5 $0 $10 $20 $0 $5 $10
D $45 $25 $20 $30
Selanjutnya dibuat garis yang memotong nilai nol (jika jumlah garis yang terjadi sama dengan jumlah baris atau jumlah kolom, akan menunjukkan perhitungan yang optimal/menghasilkan penugasan maksimal)
90
Jika jumlah garis tidak sama dengan jumlah baris atau jumlah kolom, dilakukan proses eliminasi dengan cara mengurangkan nilai terendah pada masing-masing kolom dengan nilai terendah pada masing-masing kolom
Petugas
Petugas
tersebut.
1 2 3 4
A $40 $20 $20 $15
Proyek B C $0 $10 $50 $0 $0 $10 $0 $5
D $5 $5 $20 $10
Proyek A B C D 1 $25 $0 $10 $0 2 $5 $50 $0 $0 3 $5 $0 $10 $15 4 $0 $0 $5 $5
Kemudian diuji lagi dengan membuat garis yang memotong nilai nol dalam tabel tersebut. Jumlah garis yang sama dengan jumlah baris atau jumlah kolom yang terjadi menunjukkan adanya penugasan yang paling optimal untuk mendapatkan nilai maksimal dari perhitungan yang dilakukan.
91
Petugas
Sehingga penugasan yang terjadi adalah
1 2 3 4
A $25 $5 $5 $0 1
Proyek B C $0 $10 $50 $0 $0 $10 $0 $5 1 3
D $0 $0 $15 $5 2
2 2 1 2
Petugas 1 mengerjakan proyek D $ 55 Petugas 2 mengerjakan proyek C $ 80 Petugas 3 mengerjakan proyek B $ 100 Petugas 4 mengerjakan proyek A $65 Sehinga total keuntungan yang didapat sebesar $ 300
92
CHAPTER 7: PROJECT ANALYSIS Pendahuluan The Program Evaluation and review Technique (PERT) dan Critical Path Method (CPM) adalah teknik analisis yang paling populer dalam membantu manajer
untuk
merencanakan,
penjadwalan
dan
memonitor
serta
mengendalikan proyek-proyek besar dan komplek.
Kerangka PERT dan CPM mendifinisikan proyek dan aktivitas-aktivitas yang signifikan dalam sebuah proyek mengembangkan hubungan antar aktivitas, menetukan aktivitas mana yang mendahului dan aktivitas yang didahului menggambarkan hubungan jaringan antar aktivitas menentukan biaya dan waktu untuk tiap aktivitas Menghitung waktu paling panjang pada suatu jalur dalam jaringan aktivitas tersebut yang disebut critical path menggunakan jaringan untuk membantu perencanaan, penjadwalan monitoring dan pengendalian proyek.
PERT Metode ini dapat menjawab pertanyaan-pertanyaan: 1. kapan sebuah proyek diselesaikan 2. apa
saja
aktivitas
kritis
dalam
proyek,
yang
harus
diperhatikan/didahulukan 3. aktivitas mana yang tidak kritis dalam proyek yang dapat ditunda 4. kemungkinan penyelesaian proyek dalam satuan waktu tertentu
93
5. melihat kapan sebuah proyek dapat dikatakan sesuai jadwal, mendahului atau terlambat 6. biaya yang terjadi jika ada keterlambatan, percapatan sebuah penyelesaian proyek 7. apakan sumber daya yang dimiliki mencukupi penyelesaian proyek tepat waktu 8. jika menginginkan percepatan penyelesaian proyek, apa yang harus dilakukan.
Contoh. Aktivitas A B C D E F G H
Aktivitas yang mendahului A B C C D-E F-G
Waktu Aktivitas: -
Waktu optimis (a), terjadi jika keseluruhan aktivias berjalan sebaik mungkin
-
Waktu Pesimis (b) terjadi jika menghadapi kondisi yang tidak mendukung
94
-
Waktu realistik (m), waktu yang realistis dalam penyelesaian proyek, dengan memperhatikan berbagai kemungkinan yang terjadi.
Waktu yang diharapkan memiliki rumusan: T=
a + 4m + b 6
b−a Dengan variance 6
2
Contoh menentukan Critical path method (CPM) Waktu T= Aktivitas Waktu Waktu optimis Realistis Pesimis(b) a + 4 m + b (a) (m) 6 A B C D E F G H
1 2 1 2 1 1 3 1
2 3 2 4 4 2 4 2
3 4 3 6 7 9 11 3
2 3 2 4 4 3 5 2
variance
b−a 6
2
4/36 4/36 4/36 16/36 36/36 64/36 64/36 4/36
95
Earliest Start (ES) dan Earliest finish (EF)
latest Start (LS) dan Latest finish (LF)
96
CPM Aktivitas A B C D E F G H
ES 0 0 2 3 4 4 8 13
EF 2 3 4 7 8 7 13 15
LS 0 1 2 4 4 10 8 13
LF 2 4 4 8 8 13 13 15
LS-ES 0 1 0 1 0 6 0 0
CP Y N Y N Y N Y Y
Project Variance Aktivitas variance
b−a 6
2
A C E G H
4/36 4/36 36/36 64/36 4/36 112/36 3.11
97
Project standar deviation
3.11 = 1.76 pekan Jika proyek ini memiliki batas penyelesaian selama 16 pekan, maka kemungkinan dapat terselesaikan Z=
16 − 15 =0.57 1.75
Sehingga kemungkinan penyelesaiannya adalah (Z = 0.57) = 71.6%
PERT/COST Aktivitas A B C D E F G H
ES 0 0 2 3 4 4 8 13
EF LS 2 0 3 1 4 2 7 4 8 4 7 10 13 8 15 13
LF 2 4 4 8 8 13 13 15
LS-ES 0 1 0 1 0 6 0 0
CP Y N Y N Y N Y Y
Budget 22.000 30.000 26.000 48.000 56.000 30.000 80.000 16.000
Cost/week 11.000 10.000 13.000 12.000 14.000 10.000 16.000 8.000
98
Anggaran Berdasarkan Earliest Start Aktivitas 1 11 10
A B C D E F G H komulatif
21 21
2 11 10
21 42
3 10 13
23 65
4
13 12
25 90
5
6
7
8
12 14 10
12 14 10
12 14 10
14
36 126
36 162
36 198
14 212
9
10
11
12
13
16
16
16
16
16
16 16 228 244
16 260
16 276
16 292
14
15
8 8 300
8 8 308
Anggaran Berdasarkan Latest Start Aktivitas 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 A 11 11 B 10 10 10 C 13 13 D 12 12 12 12 E 14 14 14 14 F 10 10 10 G 16 16 16 16 16 H 8 8 21 21 23 25 26 26 26 14 16 16 26 26 26 8 8 komulatif 21 42 65 90 116 142 168 182 198 214 240 266 292 300 308
99
Kurve S 350 300 250 200 Anggaran Berdasarkan ES
150 100
Anggaran Berdasarkan ES
50
15
13
11
9
7
5
3
1
0
Pengendalian Anggaran Aktivitas
Budget
A B C D E F G H
22.000 30.000 26.000 48.000 56.000 30.000 80.000 16.000
% Completed 100 100 100 10 20 20 0 0
Value
Actual
Slack
22.000 30.000 26.000 4.800 11.200 6.000 0 0
20.000 36.000 26.000 6.000 20.000 4.000 0 0
-2.000 6.000 0 1.200 8.800 -2.000 0 0
Contoh soal
100
Jika diketahui sebuah proyek dengan waktu dan biaya seperti dibawah, carilah CP-nya dan buatlah kurve S-nya Akt A B C D E F G H I J K L M N
Mod
B A A E D C D I-H C F-G K J-L-M
T 3 5 4 3 2 1 6 3 2 1 4 2 1 7
$ 900 100 200 300 800 200 300 300 100 200 800 400 200 700
Jawaban. Mencari jalur kritis Akt Mod T $ $/T ES EF A 3 900 300 0 3 B 5 100 20 0 5 C B 4 200 50 5 9 D A 3 300 100 3 6 E A 2 800 400 3 5 F E 1 200 200 5 6 50 G D 6 300 6 12 H C 3 300 100 9 12 I D 2 100 50 6 8 J I-H 1 200 200 12 13 K C 4 800 200 9 13 L F-G 2 400 200 12 14 M K 1 200 200 13 14 N J-L-M 7 700 100 14 21 CP A-B-C-D-G-K-L-M-N
LS 0 0 5 3 9 11 6 10 11 13 9 12 13 14
LF 3 5 9 6 11 12 12 13 13 14 13 14 14 21
LS-ES 0 0 0 0 6 6 0 1 5 1 0 0 0 0
CP Y Y Y Y N N Y N N N Y Y Y Y
101
Berdasarkan ES
Akt A B C D E F G H I J K L M N
Mod
B A A E D C D I-H C F-G K J-L-M
T 3 5 4 3 2 1 6 3 2 1 4 2 1 7
1
2
3
300
300
300
20
20
20
4
5
20
20
100
100
400
400
6
7
8
9
50
50
50
50
50
50
50
10
11
12
13
14
15
16
17
18
19
20
21
100
100 200
50
50
50
50
100
100
100
200
200
200
50 200 200 200
200 200 100
100
100
100
100
100
320
320
320
520
520
350
150
150
100
350
350
350
600
400
100
100
100
100
100
100
100
320
640
960
1480
2000
2350
2500
2650
2750
3100
3450
3800
4400
4800
4900
5000
5100
5200
5300
5400
5500
102
Berdasarkan LS Akt A B C D E F G H I J K L M N
Mod
B A A E D C D I-H C F-G K J-LM
T 3 5 4 3 2 1 6 3 2 1 4 2 1
1
2
3
300
300
300
20
20
20
4
5
20
20
100
100
6
7
8
9
50
50
50
50
10
11
12
13
400
400
50
50
50
100
100
100
50
50
200
200
14
15
16
17
18
19
20
21
100 200 50
50
50
200 200
200
200
200 200
7
100
100
100
100
100
100
100
320
320
320
120
120
150
100
100
100
650
750
600
550
600
100
100
100
100
100
100
100
320
640
960
1080
1200
1350
1450
1550
1650
2300
3050
3650
4200
4800
4900
5000
5100
5200
5300
5400
5500
103
6000 5000 4000 3000
Earliest Latest
2000 1000
21
19
17
15
13
11
9
7
5
3
1
0
104
Soal Latihan Buatlah kurve S dari proyek dibawah dan tentukan jalur kritisnya Aktivitas Pendahulu Waktu Biaya A 10 20 B 12 30 C 14 28 D A 5 15 E A 6 12 F B 4 8 G B 3 6 H C 6 12 I C 7 14 J C 9 27 K D 7 21 L E-F 5 20 M G-H 8 36 N G-H 3 15 O G-H 5 5 P J 8 64 Q K-L-M 6 36 R O-I 9 27 S Q 4 12 T R-U 2 12 U P 6 18 V S-N-T 8 24 W R-U 10 20 X W 9 27 Y V-X 5 20 Z Y 10 20
105
DISKUSI KASUS Case #1 CUSTOM VANS INC Perusahaan Custom Van adalah perusahaan yang bergerak dibidang perombakan standar kendaraan model van kebentuk camper. Dengan kesesuaian pada jumlah pekerjaan dan perombakan yang dilakukan, perombakan ini membutukan biaya kurang dari $1000 atau lebih dari $5000. Pada empat tahun terakhir, Tony Rizzo mampu mengembangkan usahanya di Gary Indiana hingga mamapu mengembangkannya dengan memiliki outlet di Chicago,Milwaukee, Minneapolis dan Detroit. Kesuksesan usahan Tony ini sangat dipengaruhi oleh inovasi yang dikembangkannya dalam merombak bengkel van yang masih kecil menjadi usaha yang lebih besar dan professional di Midwest. Tony kelihatannya memiliki kemampuan khusus untuk merancang dan mengembangkan gaya dan model sehingga mampu meningkatkan permintaan dari para pemilik mobil van. Sebagai contoh, shower Rific mampi berkembang, setelah dirombak oleh tony 6 bulan setelah usaha tni dimulai. Sebuah shower kecil yang didesain dan dikembangkan untuk dapat ditempatkan di berbagai posisi di dalam van. Shower Rifik dibuat dari fiberglass dan terdiri dari rak handuk, tampat sapodansabun, dan pintu plastik yang unik. Tiap pembuatan Shower ini membutuhkan 2 galon fiberglass dan 3 jam kerja. Hampir semua proses produksi produk ini dikerakan gary di warehouse yang sama dimana perombakan van ditemukan. Pabrik dari produk ini menghasilkan 300 shower rific dalam satu bulan, Namun kapasitasnya tidak pernah mencukupi. Bengkel pembuatan peromabak van di semua lokasi mendapatkan protes karena tidak mencukupi produk shower ini dan jugakarena minneapolis terlalu jauh dari gay dibanding lokasi lainnya. Tony selalu cenderung mengirim shower rific ini ke leokasi lainnya sebelum ke
106
minneapolis. Hal ini membuat marah manager yang ada di minneapolis. Seleha dilakukan diskusi, tony memutuskan untuk membangun pabrik baru di Fort Wayne Indiana. Di tempat ini akan diproduksi sejumlah 150 shower tiap bulan. Pabrik di fort wayne ini tenyata masih belum mapu memenuhi permintaan untiuk produk ini. Dan tony juga mengatui bahwa untuk tahun depan permintaan ini akansemakin meningkat tajam. Setalah berkonsultasi dengan konsultan dan bank, tony dia harus segara membangun dua pabrik lainnya secepat mungkin. Tiap pabrik harus memiliki kapasitas yang sama dengan yang ada di fort wayne. Ada beberapa alternatif tempat untuk membangun dua pabriknya yaitu, detroit, michigan, rockord, illinois atau madison, wisconsin. Tony memahami bahwa pemilihan dan penempatan lokasi yang terbaik adalah keputusan sulit.
Biaya transportasi dan
permintaan untuk likasi yang berbeda akam mempengaruhi keputusan ini. Toko di chicago di manage oleh Bill Burch. Disini tony menemptkan salah satu outletnya yang kemudian diikuti dengan lokasi lain berikutnya. Pabrik gary ini mensuply 200 shower tiap bulannya. Walaupun Bill mengetahui bahwa permintaaan di chicago sebanyak 300 unit. Biaya transportasi dari gary ke chicago $10, dan biaya transport dari fort wayn dua kali jumlah tersebut. Bill selalu meminta kepada tony untukk mendapatkan tambahan 50 unit dari forth wayne. Tambahan 2 pabrik yang dibangun akan mampu suplai pada bill dengan tambahan 100 unit yng dibutuhkan bill. Dan biaya trnsportasinya akantergantung dari lokasi yang akan dipilihnya. Jika dari detroit biay transportasinya $30, dari rockford $5 dan dari madison $10. Wilma Jackson manajer di Milwaukee juga kesal dengn kekurangn suplai showerini. Permintaanya adalah 100 unit. Sedang suplai yang diterimanya selama ini hanya separuh dari kebutuhanya dari pabrik di fort wayne.
Wilma heran kenapa tony tidak mengiriminya 100 unit dari gary
walau biaya transportasinya hanya $20 dari Gary. Sedang biaya transpotasi
107
dari fortwayne $30.Wilma berharap tony akan memilih madison sebagai salah satu lokasi produksinya. Sehingga dia akan dapat memperoleh produk ini sesuai kebutuhannya dengan biaya transportasi hanya $5 per unit. Jika buka di Madison, pabrik baru di rockford akan mampu menyediakan seluruh kebutuhannya, namun biaya transportasinya akan menjadi duakali lipat dibanding dari madison. Karena biaya tranportasi per unit dari detoid $40, Wilma membuat spekulasi kalau-kalau detroid akan menjedi salah satu pabrik baru yang akan dibangun. Dia tidak akan mengambil dari selain dari Detroit. Custom Van Inc. Di minneapolis yang di pimpin oleh manager Tom Poanski, dia membutuhkan 100 shower dari parbrik gary. Permintaan yang ada 150 unit. Tom mendapatkan biaya transportasi tertinggi dibanding dengan lokasi lainnya. Biaya transportasi dari Gari sebesa $40 per unit. Hal ini lebih tinggi $10 jika shower dikirim dari lokasi Fort Wayne. Tom berharap detroit bukan satu-satunya pabrik baru yang akan dibangun, karena akan mengakibatkan biaya trsportasi menjadi $60 per unit. Rockford dan Madison akan memberikan biaya $30 dan $25 ke minneapolis. Posisi Toko di detroit hampir mirip dengn yang berada di Milwaukee, hanya saja permintaanya hanya separoh untuk tiap pekannya.Detroit tidak enerima 10 unit shower ini secara langsung dari Pabrik di fort Wayne, Biaya transportasinya hanya $15 per unit dari Fort Wayne, sedangkan biaya $25 dari gary. Dick Lopz manaer Custom Vans Inc di detroit, memperhitungkan kemungkinan jika menempatkan sebuah pabrik di detroit dengan pioritas yang tinggi. Pabrik yang akan ditempatkan di tengah kota dan biaya transportasinya hanya akan memakan $5 per unit. Dia akan medapatkan shower sejupah 150 unit dari pabrik baru di detroit dan 50 unit lainnya dari Fort Wayne. Jika Detroit tidak enjadi pilihan, maka dua lokasi lainnya tidak bisa dihindari. Rockford akan memakan biayatransportasi sebesar $35 dan Madison $40.
108
Tony empertimbangkan dilema pilihan lokasi dua pabrik baru beberapa pekan sebelum membuat keputusan dengan mengadakan pertemuan semua manajer dri semua tokonya. Keputusan ini akan sngat rumit, namun jelas tujuannya yaitu untuk meminimalisir biaya. Pertemuan akan di adakan di Gary dan semua manajer hadi kecuali Wilma. Tony: Terimakaih atas kehadiran saudara-saudara pada rapat kali ini. Sebagaimana kita ketahui berasma bahwa saya telah memutuskan untuk membuka dua pabrik baru di rockford, madisun atau detroit. Dua lokasi yang akan kita pilih akan emberikan pengaruh pada praktek pengiriman kita, dan harapan saya hal ini akan dapat memenuhi kebutuhan pengiriman dan permintaan untuk tiap toko saudara-saudara.Saya mengetahui bahwa anda harus menjual lebih banyak, saya ingin anda mengetahui bersma bahwa saya mohon maaf atas segala situasi ini. Dick: Tony, saya telah memaparkan kondisi ini dengan beberapa alasan, dan saya sangat baerharap bahwa salah satu pabriknya akan anda tempatkan di detroit. Sebagai mana anda ketahui, saya hanya mendapatkan separoh dari kebutuhan kami. Saudara saya, Leon, sangat terrtarik untuk ikut menjalankan pabrik ini dan saya tahu dia akan melamar untuk pekerjaan ini. Tom: Dick, saya tahu Leon akan mendapatkan pekerjaan yang baik ini, dan saya tahu betapa berat yang dirasakannya sejak di keluarkan dari industri Auto. Namun kita harus memperhatikan biaya total bukan permasalahan personal. Saya percaya jika pabrik baru akan di tempatkan di madison dan di rockford. Saya berpikir panjang jika penempatan pabrik dn beberapa toko yang direncanakan di tempat ini akan sangat signifikan mengurangi biaya transportasi. Dic: Hal itu mungkin benar, namun ada beberapa alasan lainnya. Detroit adalah salah satu suplier terbear untuk fiberglass, dan saya telah melakukan pengecekan biayanya. Satu pabrik baru di detroit hanya mebutuhkan $2 per
109
galon untuk fiberglass lebih murah dibandingkan dengan pabrik yang diusulkan di lokasi lain. Tom: di madison, kami memiliki biaya pekerja yang sangat menarik. Hal ini karena banyak pelajar dari Univeritas madison. Mereka adalah pekerja keras dan mereka hanya dibayar $1 perjam lebih murah dari lokasi lain. Ini alasan saya. Bill: Santai saja saudara-saudara, jelas disini kita tidak akan mampu memuaskan semuanya dari kita dlam memutuskan lokasi pabrik-pabrik baru kita. Namun kita harus memilih dengan voting yang terbaik dua lokasi yang akan kita jadikan tempat pembangunan pabrik baru kita. Tony: saya kira voting bukan hal terbaik bagi ita. Wilma tidak hadir saat ini, dan kita harus melihat semua faktor secara bersama-sama dengan semua kondisinya.
DISKUSI: Dimana lokasi pabrik itu akan ditempatkan?
110
Case #2 Haygood Company
George dan harry haygood adalah sebuah kontraktor bangunan yang mengkhususnkan pada pembangunan rumah tinggal, gudang dan bisnis kecil, yang kurang dari 20.000 kaki persegi untuk luasan lantai. Baik george maupun harry memulai dari program pelatihan asosiasi pengusaha kayu awal tahun 1990an dan selama mengikuti pelatihan untuk menjadi tenaga ahli hingga tahun 1996. Sebelum memulai bisnisnya sendiri, merke bekerja pada kontraktor-kontrakot di wilayah detroit. Akhirnya heygood bersaudara berhasil memenangkan beberapa tender poyek perumahn. Dalampenyelesian kontrak, beberapa aspek kontruksi seperti pemasangan jaringan listrik, saluran pembuangan, pengecatan, konblok dan lainnya di sub kontarkkan. George danharry hanya menangani pekerjaan kayunya saja. Namun mereka juga yang membuat perencanaan dan penjadwalan kerja untuk seluruh operasional pembangunan, dan masalah keuangan serta mensupervisi semua aktivitas pembangunan tersebut. Dengan moto “ Waktu adalah uang” Haygood mencoba untuk melakukan efisiensi dengan mengendalikan keuangan. Oleh karenanya jangan sampai ada penundaan pekerjaan dalam proyek ini. Untuk menganalisisi heygood menggunakan metode PERT. Yant pertama di jabarkan seluruh aktivitas dalam proyek tersebut. Kemudian dihitung kebutuhan waktu untuk penyelesaian masing-masing aktivitas tersebut, hingga konsekuensi pembiayaannya. Setelah diketahui Earliest dan Latest time untuk keseluruhan aktivita, haygood dapat mengalokasikan sumberdaya yang dimilikinya untuk penyelesaian proyek. Berikut aktivitas yang ada padaproyek tersebut: 1. Merancang Keuangan 2. Mencari subkontraktor
111
3. memasang pondasi 4. pemasangan plumbing 5. pemasangan rangka 6. pemasangan atap 7. pemasangan jaringan listrik 8. memasang pintu dan jendela 9. pemasangan jaringan pemanas dan pendingin ruangan 10. pemasangan panel dan plesteran dinding 11. pemasangan kabinet 12. pemasangan konblok 13. Pemasangan strimin luar 14. pemsangan strimin dalam 15. pengecatan 16. Pemasangan lantai
G D A
B
C
F
H I
E
L
O
K
P M
Q
N
J
112
Data proyek: Aktivitas AB BC CD CE D FG FH FI FJ JK KL KM MN LO OP PQ
optimis 4 2 5 4 2 3 4 3 5 10 4 7 4 5 5 2
realistis 5 5 7 5 4 5 5 4 7 11 6 8 5 7 6 3
Pesimis 6 8 9 6 6 9 6 7 9 12 8 9 10 9 7 4
Diskusi: 1. Jalur Kritis/ Critical path? Lama waktu proyek yang melalui jalur kritis? 2. Hitung jumlah waktu yang dapat ditunda untuk aktivitas yang ada tanpa mempengaruhi keterlambatan proyek 3. Berapa keumnginan yang terjadi jika proyek dimulai tanggal 1 agustus dan
selesai
tanggal
30
september?
Dengan
catatan
jadwal
penyelesaian 60 hari.
113
Case #3 MANAGEMENT VIDEO PROFESIONAL
Semenjak awal diperkenalkan sebuah system home video untuk televisi, stave Goodman sudah memimpikan sebuah peluang usahanya untuk sisete video untuk aktovitas professional. Selama beberapa tahun terakhir stave melihat beberapa film lama favoritnyadi video ruhamnya dan merancang pengebangan
untuk
system
video
rumahnya.
Dia
mencoba
untuk
menggunakan stasion televisi, agen periklanan dan dan beberapa kelompok dan perorangan yang menginginkan system vided terbaik. Dasar dari system ini termasuk ruang pengendali yang lengkap, dua system videotape yang terpisahkan, videodisk dan satu set televisi professional yang berkualitas. Semua peralatan ini adalah alat yang saling terintegrasikan. Sebagai tambahan, dasar dari system ini hadir dengan tambahan system remote control. System ini dapat mengoperasikan baik sviseo system, video disk dan system tv dengan mudah. Remote contro dapat bekerja dengan mengirimkan sinyal infra merah ke kotak pengendali yang ada dalam system pengenaliannya. Hal yang unik dalam system video ini adalah terdapat pada kotak pengendalinya. Kotak pengendali ii terdapat microposesorcanggih yang memiliki kemampuan menkoordinasikan pemakaianan dan ungsi peraalatan lain yang terdeteksi. Sistem video professional stave ini memiliki beberapa keunggulan disbanding system yang ada pada umumnya. untuk memulainya seperti adanya efek khusus yang dapat dikendalikan secara mudah. Image pada videodisk, salah satu sistem video tersebut, dan sistem televisi dapat dengan mudah ditempatkan pada sistem video lainnya. Sebagai tambahan hal ini memungkinkan untuk menghubungkan dengan kotak pengendali pada PC atau Mechintos. Hal ini membuat kemungkinan adanya pengembangan grafis yang lebih menarik dalam microkomputer dan dapat untuk mentranfer secara
114
langsung
ke
system
mencantelkansistem
video.
stereo
ke
Begitu dalam
juga
memungkinakn
kotak
pengendali
untuk untuk
mengintegrasikan sistem kualitas suara yang lebih teinggike dalam sistem dan merekamnya ke dalam salat satu video sistemnya. Kedua sistem video tersebut juga memiliki fleksibilitas yang luarbiasa untuk proses editing. Beberapa item khusus telah ditempatkan pada reote kontrolnya. Hal ini memungkinkan untuk merekam sebuah program pada salah satu sistem video yang pertama dan mengeditnya dengan sistem video tape yang lain untuk memberikan tambahan atau mengurangi begian-bagian tertentu. Salah satu feature terbaik pada sustem yang dikembangkan staveini adalah harganya. System dasar dan termasuk kotak pengendali, dua sistem video, video disk, dan system televisi hanya dijual dengan harga $1.995. Stave menemukan produk untuk sistem televisi, kotak pengendali, dan sistem videodisk di Amerika. Karena sistem videotapelebih terkenal, stave memiliki banyak pilihan. Setelah mengadakan penelitian, stave menemukan dua suplier. Kedua suplier ini adalah perusahaan jepang. Tishiki sebagai perusahaan baru di luar tokyo jepang. Seperti suplier lainnya, toshiki memberikan diskon . Untuk pembelian kurang dari 2000 unit, permintaan produk untuk stave akan diberikan harga $250 pervideo system. Sedangkan harga $230 akan diberikan untuk pembelian antara 2000 hingga 8000 unit. Dan untuk pembelian antara 8000 sampai 20.000 unit akan dikenakan biaya $210 per unit untuk sistem video ini. Suplier jepang lainnya, Kony. Walaupun asalnya Kony berawal di jepang, dan diluar tokyo, namun memiliki fasilitas dan kantor di seluruh dunia. Salah satunya berada di sekitar 100 mil utara atlanta, georgia. Seperti Toshiki, Diskont yang ditawarkan oleh Kony akan diberikan untuk sejumlah pembelian.
Untuk sejumhalh kurang dari 1000 unit akan diberikan harga
$250 per unit. Untuk julah 1000 hingga 5000 akan diberikan harga $240. Dan untuk pengadaan lebih dari 5000 akan diberikan harga $220.
115
Karena perusahaan Kony terletak di Amerika, biaya pemesanan dan waktu pengiriman lebih menarik dari Toshiki. Perkiraan biaya pemesanan untuk Kony adalah $40, dan pengirimanhanya memakanwaktu 2 pekan. Sedangkan untuk toshiki biaya pemesanan dan wktu pengirimanakan lebih tinggi dibnding dengan kony. Belum lagi tambahan biaya $90 untuk pengadaan dari jepang untuk tiap ordernya. Dan waktu pengiriman selama 3 bulan. Perkiran stave untuk biaya pengiriman akan mencapai lebih 30%. Untuk tahun pertama stave memutuskan untuk menjual hanya unit dasar dari system produk yang diciptakan. Yaitu kotak pengendali, televisi, video disk dan dua sistem videotae. Perminttaan dari sistem keseluruhan relati konstn selama 6 bulan terakhir. Misalnya untuk permintaan bulan juni penjualanan mencapai 7979 unit, juli 8070 unit, agustus 7950 unit dan september 8070unit. Perkembangan ini akan relatif tetap untuk beberapa bulan mendatang.
Diskusi: 1. Produk apa yang diunggulkan stave? 2. Apa saja masalah yang dihadapi stave untuk memasarkan produk? 3. Berapa ROP untuk Kony dan toshiki? 4. Jika anda menjadi stave, perusahaan mana yang akan anda pilih sebagai mitraa suplier anda? 5. Stave memiliki beberaa strategi. Strategi pertama stave adalah akan menjual koponenya secara terpisah. Strategi kedua adalah akan memodifikasi kotak pengendali mengikuti sistem videotape untuk digunakan sebaik sistem video yang dihailkan stave. Secara umum, apa
pengaruh
dari
penambahan
sistem
ini
pada
ROP
dan
pengendalian persediaan bagi stave?
116
PAPER Paper-1: Presentation of a New and Beneficial Method Through Problem Solving Timing of Open Shop by Random Algorithm Gravitational Emulation Local Search
Abstract One of the most important problems of timing in engineering and industry is timing of open shop. The problem of timing of the open shop induces big and complicated solve space. So, this problem is a kind of NP-Complete. In timing of the open shop, there some works, that each work has several operation. Each operation should do in machine whit should do in the same machine the aim of timing of the open shop is to catch a suitable timing for doing all of the operation, how that enough time to minimize to make-span. In problem solve of timing of the open shop. Until now different algorithm were presented. In this article, a new algorithm that is called TIME_GELS is presented which used of a random. Algorithm Gravitational Emulation Local Search (GELS) for following problem solving. This algorithm is basic of the random local search use of two of the four main parameter of speed and the power of gravity in physics. A suggestive algorithm compared with Genetic Algorithm and result is show that a proposed algorithm has a better efficient and finding the answer very soon. Keywords: Timing; Open Shop; Genetic Algorithm; Velocity; Newton law; Gravitational force
117
Paper-2: Inverse Optimization for Linear Fractional Programming Abstract: In this paper, we have proposed an inverse optimization model for linear ractional
programming
the parameters of
(LFP) problem.
In our
proposed model,
the objective function are adjusted as
little as
ossible (under L1 norm), so that the given feasible solution become optimal. We formulate the inverse linear fractional programming (ILFP) problem as a linear
programming
problem
which can be solved by
having
many
large number existing
of
variables, methods or
optimization software such as: TORA, EXCELSOLVER etc. The method has been illustrated by a numerical example also. Keywords:
Inverse
optimization,
Linear
Fractional
Programming,
Complementary slackness Paper-3: A multi-objective model for designing a group layout of a dynamic cellular manufacturing system
Abstract This paper presents a multi-objective mixed-integer nonlinear programming model to esign a group layout of a cellular manufacturing system in a dynamic environment, in which the number of cells to be formed is variable. Cell formation (CF) and group layout (GL) are concurrently made in a dynamic environment by the integrated model, which incorporates with an extensive coverage of important manufacturing features used in the design of CMSs. Additionally, there are some features that make the presented model different from the previous studies. These features include the following: (1) the variable number of cells, (2) the integrated CF and GL decisions in a dynamic environment by a multi-objective mathematical model, and (3) two conflicting
118
objectives that minimize the total costs (i.e., costs of intra and inter-cell material handling, machine relocation, purchasing new machines, machine overhead, machine processing, and forming cells) and minimize the imbalance of workload among cells. Furthermore, the presented model considers some limitations, such as machine capability, machine capacity, part demands satisfaction, cell size, material flow conservation, and location assignment. Four numerical examples are solved by the GAMS software to illustrate the promising results obtained by the incorporated features. Keywords: Dynamic cellular manufacturing systems, Multi-objective model, Cell formation, Group layout
Paper-4: Integrating truck arrival management into tactical operation planning at container terminals
Abstract Truck arrival management (TAM) has been recognized as an effective olution to alleviate the gate congestion at container terminals. To further utilize TAM in improving the overall terminal performance, this study integrates TAM with the other terminal operations at a tactical level. An integrated planning model and a sequential planning model are presented to coordinate the major terminal planning activities, including quayside berth allocation, yard storage space allocation and TAM. A heuristic-based genetic algorithm is developed to solve the models. A range of numerical examinations are performed to compare two planning models. The result shows that: the integrated model can improve the terminal performance significantly from the sequential model alone, particularly when the gate capacity and the yard capacity are relatively low; whereas the sequential model is more efficient than the integrated model in terms of computational time. Keywords: container terminal; integrated planning; truck arrival management; berth allocation; storage space allocation
119
Paper-5: Pharmaceutical Inventory Management Issues in Hospital Supply Chains Abstract The primary focus of the healthcare sector is to provide patients with the best quality of care. While the healthcare cost is keep on growing, effective healthcare supply chain should be achieved to reduce some unnecessary costs. To address this issue, this study aims to examine inventory management practice in one of Indonesian public hospital and focus on the role of inventory to drive hospital supply chain performance. Three major issues regarding inventory management practice has been identified such as overstock, unjustified forecasting technique and lack of IT support. Proposed (s,Q) policy using continuous review can reduce by 50% total inventory value on hand of oncology medication. Among several forecasting technique that’s presented, Holt’s model appears to be the best adapted for oncology medication. Future study is needed to simulate the outlook condition using proposed policy. By implementing a new inventory policy that cope all the constraints and problems will help hospital to manage its pharmacy inventory in effective and efficient way. Keywords: Inventory Management, Oncology Medication, Public Hospital, Indonesia
Paper-6: Improving a Flexible Manufacturing Scheduling using Genetic Algorithm Abstract A Flexible Manufacturing System (FMS) is designed to produce a variety of products, utilizing a set of resources like work stations, robots etc., interlinked by certain means of transport. The prime characteristic of an FMS is that the overall system is under the computer control to realize these essential improvements in a firm; it imposes many challenging problems for planning, scheduling, monitoring and control of manufacturing system. These problems have a fundamental implication on the overall performance of a FMS, and
120
influence the responsiveness of the system to satisfy the changing customer needs. In this study, dispatching rules are used to solve the scheduling problem. Further, the multiple dispatching rule based heuristic is proposed to search the optimal sequence of operations. Genetic Algorithm (GA) is used as a random search optimization technique in the proposed heuristic. Finally, the sequence determined with the proposed heuristic is utilized to develop based intelligent controller. Keywords: Job shop scheduling, genetic algorithm, priority rule, flexible manufacturing system, heuristics
121
CONTOH SOAL QUIZ, UTS DAN UAS Quiz
Take Home, dikumpulkan sehari setelah soal ini dibagikan Dikerjakan dengan kertas bergaris, dengan huruf balok. soal transportasi
TUJUAN Kapasitas Gudang 1 (500) Gudang 2 (500) Gudang 3 (1000)
Pasar A 600 Rp. 1.250,Rp. 2.250,Rp. 2.500,-
Pasar B 750 Rp. 1.750,Rp. 1.500,Rp. 1.500,-
Pasar C 650 Rp. 1.000,Rp. 1.750,Rp. 2.500,-
Tentukan distribusi yang menghasilkan biaya terendah dan berapa biaya yang terjadi.
Soal Inventori Tentukan -
ROP dan EOQ
Data Order January February March April May June July August September October November December
Product Sold 1500 1600 1700 1500 1600 1600 1700 1500 1500 1400 1400 1500
Ordering Cost $ 20 $ 20 $ 20 $ 20 $ 20 $ 20 $ 20 $ 20 $ 20 $ 20 $ 20 $ 20
Carrying Cost $ 1,275 $ 1,360 $ 1,445 $ 1,275 $ 1,360 $ 1,360 $ 1,445 $ 1,275 $ 1,275 $ 1,190 $ 1,190 $ 1,275
sending (day)
3 4 5 3 5 4 4 5 3 4 5 3
122
Pembelian <3500 3500-5000 >5000
Discount no Disc 30% 45%
jika ,Stock out cost perunit sebesar 20+X; X adalah digit terakhir NIM anda Berapa nilai EMV terkecil dan pada posisi alternatif order berapa
123
UTS
Dikerjakan dengan kertas bergaris, dengan huruf balok Waktu mengerjakan 90 menit, OPEN BOOK. Kerjakan Sendiri-sendiri Tentukan Critical path dan S Kurve-nya aktivitas A B C D E F G H I
pendahulu A B C D F G,E,H
Waktu 3 5 3 6 5 8 6 9 8
Biaya (Rp.) 6 10 9 18 15 16 12 27 32
124
UAS
Kerjakan dua soal dari soal-soal berikut: Berapa biaya ternendah untuk penyelesaian kasus 2: Custom Vanc Inc. Buatlah kurve S dari kasus 4: Hay Good Company Berapa persen efektifitasn yang terjadi dari perubahan layout pada Kasus 3: New England Casting Pada formulasi loket seperti apa yang menghasilkan biaa antrian terendah antrian pada kasus 6: Management Family
125
PENULIS Setyabudi Indartono, Ph.D Lahir di Purwokwero, 20 juli 1972. Menyelesaikan studi SD hingga SMA di Banjarnegara Jawa Tengah. Kemudian melanjutkan studi S1 di Teknis Sipil Universitas Gadjahmada dan S2 di Magister Manajemen di Universitas yang sama, Sedang S3 di dapatkan dari National Central University Taiwan. Pernah bekerja di PT Freeport Indonesia sebagai senior fasilitator/trainer, kemudian Direktur Umum dan Keuangan Rumah Sakit PKU Muhammadiyyah Bantul. Menjadi Direktur Cabang LMT Trustco sejak 1998. Kemudian menjadi Staf Pengajar/Dosen Manajeman di Universitas Negeri Yogyakarta. Beberapa buku dan modul yang pernah ditulis adalah: 1. Steel Structure Design of PT FI apartments with Staad III Software (1995), 2. Construction Management of PT FI (1997), 3. Justice Party direct Selling (2000), 4. Management Behavior : Mentoring as Solution (2000), Business Research Method: Memory Research (2000), 5. Yogyakarta Islamic Hospital: Managing Performance (2000), 6. Yayasan Bina Sehat: Organization Change and Developmet as a priority need (2000), 7. Human Resource Management: Sociaty central health Bantul Yogyakarta (2000), 8. Organization Design of Region Directorate of Justice Party of Yogyakarta (2000), 9. PT KPI Tembagapura Compensation applications (2000), 10. SWOT (2003), 11. Advance SWOT (2003), 12. Modul TFT Trustco (2004), 13. Leadership (2005), 14. Training For Beginer (2005), 15. Smart Trainer (2005), 16. Strategic trainer (2005), 17. Marketing Advance (UNY, 2005),
126
18. Lembaga Keuangan (UNY, 2005), 19. Bahan Ajar Perkuliahan Manajemen Konflik (2013) 20. Bahan Ajar Perkuliahan Strategic Human Resourches Management (2012) 21. Bahan Ajar Perkuliahan Metode Penelitian Bisnis (2012) 22. Bahan Ajar Perkuliahan Metodologi Riset SDM (2011) 23. Bahan Ajar Perkuliahan Manajemen Perubahan (2011) 24. Bahan Ajar Perkuliahan Perilaku Organisasi (2010) 25. Bahan Ajar Perkuliahan Teknik Proyeksi Bisnis (2010) 26. Panduan praktikum Perkuliahan Operation Research (UNY, 2009), 27. Bahan Ajar Perkuliahan Pengantar Manajemen (2009) Journal Publication 1. Indartono & chen, 2008, Glocalization of Personal Ethical Threshold, Journal of Education, Vol. 1. No. 1, pg. 39 2. Indartono & chen, 2008, Perception of direct and indirect compensations fulfillment on hazardous work environment The relationship with age, tenure, employee’s rank and work status, Jurnal Siasat Bisnis, Vol. 12 No.1, pg. 13 3. Indartono, Chou & chen, 2008, The Knowledge Characteriscs Work Design Analysis of Job Fit Influence on Role Performance, Journal of Human Capital, Vol 1 No 1 pg. 81 4. Indartono, 2008, Pengaruh personal job fit terhadap hubungan desain kerja dan kinerja pengajar, Jurnal Humaniora, Vol. 13 no. 2, pg. 33 5. Indartono et al, 2009, The knowledge characteristics work design: Analysis of job fit influence on role performance, Usahawan, No. 01 vol. 38, pg. 33 6. Indartono & chen, 2009, Articulating strategic human resources management: Concept perspective to practice of managing human resources, Journal of Human Capital, Vol 1 No 3., pg.227 7. Indartono , 2009, Contribution of different organizational politics perceptions: Study on interaction among perception organizational politics, performance and trust on the role of compensation, Integritas Jurnal Manajemen Bisnis, Vol 2 no 1., pg 13 8. Indartono, 2009, Mediation effect of trust on the relationship between perception of organization politics and commitment, Jurnal Administrasi Bisnis, Vol. 5 no. 2., pg.160 9. Indartono, 2009, Different effect of Task Characteristics requirement on Job satisfaction: Gender analysis of teacher occupation on WDQ, Jurnal Ekonomika Madani,Vol 1, no. 2., pg.20 10. Indartono, Setyabudi and Vivian Chen, Chun-Hsi , 2010, Moderation of Gender on the relationship between task characteristics and performance,
127
International Journal of Organizational Innovation (IJOI), Vol. 2, no 4, Pg. 195-223 11. Indartono, Setyabudi; Chiou, Hawjeng; Vivian Chen, Chun-Hsi, 2010 The Joint Moderating Impact of Personal Job Fit and Servant Leadership on the Relationship between the Task Characteristics of Job Design and Performance, Interdisciplinary Journal of Contemporary Research in Business,Vol 2, No 8, pg 42-61 12. Indartono, Setyabudi and Vivian Chen, Chun-Hsi , 2011, Moderating Effects of Tenure and Gender on the Relationship between Perception of Organizational Politics and Commitment and Trust, South Asian Journal of Management, Vol18, no1. Pg.7-36 13. Vivian Chen, Chun-Hsi and Indartono, Setyabudi, 2011, Study of commitment antecedents: The dynamic point of view, Journal of Business Ethics, Vol. 103, No.4 , Pg.529-541 (IF2010: 1.125) 14. Indartono, Setyabudi, 2011, The Effect of E-Learning on Character Building: Proposition for Organizational Behavior Course, Jurnal Pendidikan Karakter Vol 1, No. 1, pp.59-73, LPPMP UNY 15. Indartono, Setyabudi; Nafiuddin, Yajid; Sakti K., Lingga; and Praja R. Ega, 2012, Different Perception of Gender on Workplace Spirituality: Case on School Environment, Online Journal of Education Research, Volume 1, Issue 4, Pages: 73-79 Conference proceeding 1. Indartono, Setyabudi, 2010, from statisc to dynamic perspective of behavior: case of organizational commitment”, proceeding “the First Annual Indonesia Scholars Conference in Taiwan: improving nation competitiveness by strengthening and accelerating independent reseearch”, Vol. 1 no. 1, Tainan Taiwan 2. Indartono, Setyabudi, 2009, Measuring the behavior of individual and group performance: Hierarchical linier modeling approach”, proceeding “Doctoral Program National Qolloquium” Gadjahmada University Indonesia 3. Indartono, Setyabudi, 2011, “Effect of Servant Leadership on Knowledge characteristics”, proceeding “the Second Annual Indonesia Scholars Conference in Taiwan: Becoming “Asian Tiger” through modern agriculture-based Industry : revitalization and modernization of education, technology, economy, and investment climate in agricultural sector, Vol. 2. no. 1, Taichung Taiwan 4. Indartono, Setyabudi, 2011, Acceptance and Tolerance Limit Phenomena: an Empirical Approach, International Sustainability Forum on Islamic Economic and Business, Universitas Lambung Mangkurat Indonesia 5. Indartono, Setyabudi, 2012, Reformatting Knowledge and Science Theory Building: Transcendental Point of View, proceeding “the Third Annual
128
Indonesia Scholars Conference in Taiwan: Acceleration and Development of Information and Communication Technology Research basd on Demand: Improving Sustainable Synergy of Academycs, Industry, and Government, Vol. 1.No. 1, Hsinchu Taiwan 6. Indartono, Setyabudi, 2012, Desain Kerja untuk Staf pengajar untuk mencapai Kesesuaian dan Kepuasan Kerja, Konvensi Nasional Pendidikan Indonesia VII 2012, Universitas Negeri Yogyakarta Membership and Activities 1. Member of Forum Dosen Ekonomi dan Bisnis Islam (FORDEBI) 2011-now 2. Secreatry of board, Indonesia Committee for Science and Technology Transfer in Taiwan (IC3T), 2010-now 3. Member of Editorial Board of International Journal of Commerce & Accounting Research (IJCAR), 2011-now 4. Member of Editorial Board of Journal of Arts Science & Commerce Research (RW-JASCR) , 2011-now 5. Member of Editorial Board of Asian Journal of Business Ethics (AJBE) , 2012-now 6. Member of Editorial Board of International Journal of Organizational Analysis (IJOA) , 2012-now 7. Coordinator of Development Division of Economic Faculty, Yogyakarta State University, 2011-now 8. Member of Research Devision of Economic Faculty, Yogyakarta State University, 2011-now Tinggal dengan seorang Istri, dr. Yayuk Soraya, AAK, dan tiga anak lakilakinya, Aiman Hilmi Asaduddin (1999), Rofiq Wafi’ Muhammad (2001), dan Muhammad Kaisan Haedar (2004) di Jl Arwana No 7 Minomartani.
[email protected]
129
REFFERENCES Winston, Wayne L., Operations Research: Applications and Algorithms, 3rd Edition, Duxbury Press, 1994, p. 2. http://en.wikipedia.org/wiki/Linear_programming copy at September, 7th 2013 http://www.me.utexas.edu/~jensen/ORMM/models/unit/linear/subunits/resour ce_allocation/ copy at September, 7th 2013 http://www.dspguide.com/ch5/2.htm copy at September, 7th 2013 http://www.tutorsonnet.com/homework_help/micro_economics/product_pricin g/linear_programming_and_its_limitations_assignment_help_online_tuto ring.htm copy at September, 7th 2013
130
131
