9.1. Introduction to the Problem

For our next example of linear programming, we will look at a problem involving graphs and networks to do with Network Bandwidth. So, suppose we have a small communication network involving three users. So, the users are capital A, capital B and capital C, and each of them is connected through some switches, which we call a, b and c. So, we have a network which this in an internet network which connect these three users and our requirement is to ensure that each pair of users A to B, B to C and A to C gets at least two mega bits per second of connectivity from between that pair of users.

In this chunk, we are introducing a linear programming problem related to network bandwidth allocation. We have a network with three users: A, B, and C, interconnected by switches. The goal is to ensure that each pair of users can communicate with a minimum bandwidth of 2 Mbps. This requirement establishes the foundation of our linear programming problem.

Imagine a small coffee shop with three tables. Each table represents a user, and they need a server (the switches) to deliver coffee (bandwidth) between them. Each pair of tables wants at least two cups of coffee per hour to be satisfied. The coffee shop must manage how much coffee to serve to ensure all tables are happy.

Now, notice that from A to B, there are two ways I can sent packets, I can sent that directly via A and B or I can sent them indirectly, I have small seek. So, it turns out, it does not really a matter from the point of viewer, we uses whether this 2 Mbps bandwidth comes from the shorter a red route and a longer green route. So, our aim is to combine the capacity of the red and the green for each pair, so similarly there will be, for example, there will be a direct route from B to C and there will be an indirect route that goes like this.

In this chunk, we discuss how bandwidth can be delivered in two ways: directly or indirectly. The specific path taken (whether it's the 'red route' or the 'green route') does not matter as long as the total bandwidth combined reaches the required 2 Mbps. This highlights the flexibility in managing network resources and the different routes data can take through the network.

Think of a water delivery system, where you can either deliver water through a short pipe (the direct route) or a longer one (the indirect route). As long as the two pipes together deliver the required amount of water, the system works effectively, regardless of which route is taken.

On the other side, we earn some money from this customer which is not uniform. So, for the A, B link, we get 300 rupees for mega bit Mbps per month, but from B to C we get only 200, but from A to C we get 400.

Here we discuss the monetary aspect related to bandwidth allocation. Each connection generates different revenue. For each Mbps allocated, the revenue varies depending on the customer, highlighting the importance of maximizing this revenue while fulfilling the bandwidth requirements.

Consider a milkman who delivers milk to different customers. Some customers (like those at A) are willing to pay 300 rupees per liter of milk, while others might pay less. The milkman must decide how to allocate his deliveries to maximize his earnings while ensuring every customer is satisfied with their delivery requirements.

So, as we have been seen will be our aim is to set this up as a linear program. So, in this case, what are the variables that we are going to use? So, recall that we said that every connection has two routes. So, we have A to B coming where the short route and we have A to B coming by either long route. So, what we use is the variable x, from A to B to denote that quantity that is showing on the red route and similarly, y from A to B to denote the quantity, it is flowing on the green route.

In this chunk, we introduce the formal setup for our linear programming problem. We define our variables such that each connection has two associated routes (short and long). The variables (like x and y) represent the amount of bandwidth allocated through these pathways, providing a clear method to quantify the problem.

Imagine a delivery system where we can use two types of vehicles: bikes and vans. We define variables for how many deliveries each vehicle type will make. By tracking these variables, the delivery service can optimize routes and ensure efficient deliveries based on demand and capacity.

--