Читать книгу Linear and Convex Optimization - Michael H. Veatch - Страница 13

International responses to rapid‐onset disasters are frequent and expensive. After a major disaster, such as the 2014 earthquake in Nepal, food, shelter, and other items are needed quickly in large quantities. Local supplies may be insufficient, in which case airlift to a nearby airport is an important part of a timely response. The number of flights in the first few days may be limited by cost and other factors, so the aid organizations seek to send priority items first.

To illustrate the decisions involved, consider an organization that is sending tents and nonperishable food from their stockpile to people whose homes were destroyed in a hurricane. Because they are delivering to a small airport, they are using a medium‐sized cargo aircraft, the C‐130. It has space for six pallets and a payload capacity of 40 000 lb for this length of flight. In the next week or so, the responding organizations will try to fly in enough supplies to meet all the high‐priority needs. But the first flights will be loaded before the needs assessment is even complete, just knowing that a large number of people need food and shelter. The organization has estimated the criticality of each item on a 10‐point scale (10 being the most critical). They are based on the deprivation likely to be experienced by recipients if the item is not delivered until later. However, for many reasons, not all aid meets high‐priority needs, so the organization also considers the cost (market value) of the aid, and defines expected benefit to be the average of criticality and cost. Their objective is to load the aircraft to have the greatest expected benefit. Table 1.1 lists the weight, cost, criticality, and expected benefit for both items. They have time to re‐pack one pallet with a mixture of tents and food, so the number of pallets of each item does not have to be an integer. However, only five pallets of food are immediately available – they do not stockpile large quantities of food because it eventually expires.

Table 1.1 Data for sending aid.

	Tents	Food
Weight (1000 lbs)	7.5	5
Cost ($1000/pallet)	11	4
Criticality	5	8
Expected benefit	8	6

The first idea one might have is to load six pallets of tents, the item with the largest expected benefit. However, this load is not allowed because it exceeds the weight limit. Further, since the number of pallets does not have to be an integer, trying other loads may not find the best one. Instead, we formulate the problem mathematically. Let

Then the expected value of aid loaded is

and we want to maximize over a domain that contains the possible values of . First, we have the logical restrictions . The weight limit requires that

In this expression, 7.5 is the weight per pallet of tents, so is the weight of tents. Similarly, is the weight of food. The left‐hand side, then, is the total weight of the load, which must be less than or equal to the payload capacity of 40 (these quantities are in 1000s of lbs). The space limit requires that

The left‐hand side is the total number of pallets. This total does not have to be an integer; a total of 5.4 pallets would mean that one pallet is only loaded 40% full. Finally, only five pallets of food are ready, so

These inequalities define the domain of . We will call them constraints and the function to be maximized the objective function. Optimizing a function whose domain is defined by constraints is a constrained optimization problem. The complete problem is

(1.1)

We have abbreviated “subject to” as “s.t.”

Constrained optimization problems have three components: