\documentclass{article}
\usepackage[utf8]{inputenc}
\usepackage[a4paper, margin=1in]{geometry}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{mathtools}
\usepackage{enumerate}
\usepackage{enumitem}


\title{\textbf{MS\&E 114/214 Autumn 2024 Homework 1} }
\date{~}
\begin{document}
\maketitle


Submission due {\bf 12:00 pm Oct 11.}
 When submitting, please attach the relevant Python scripts and/or Excel files to enable us to give partial credits.


\section*{Problem 1}

A pharmaceutical company has 10,000 mg of a certain drug and wants to package it into capsules of four different sizes: 

\begin{itemize}
    \item (a) extra-large,
    \item (b) large,
    \item (c) medium, and
    \item (d) small.
\end{itemize}

These capsules can hold 100 mg, 60 mg, 30 mg, and 10 mg of the drug, respectively.

Past consumer research suggests the following constraints:
\begin{itemize}
    \item The number of large capsules should be at least twice that of the extra-large capsules.
    \item The number of medium capsules should be at least three times the number of large capsules.
    \item There must be at least 100 small capsules.
\end{itemize}

Each capsule provides a different profit:
\begin{itemize}
    \item Extra-large capsules yield a profit of 5 dollars each.
    \item Large capsules yield a profit of 4 dollars each.
    \item Medium capsules yield a profit of 2 dollars each.
    \item Small capsules yield a profit of 50 cents each.
\end{itemize}


\begin{enumerate}
\item The company can produce fractional quantities of capsules. How many capsules of each size should the company manufacture to maximize profit?
\item Report the maximum profit the company can earn.
\item Identify which of the constraints are tight or slack.
\end{enumerate}

\newpage

\section*{Problem 2}

You are in charge of distributing \$100,000 among three charities. Each charity’s impact is directly proportional to the amount of money it receives, but you want to ensure no charity is significantly underfunded.

The impact of the donations is modelled as follows:
\begin{itemize}
    \item Education: $0.1 \times \text{money}_1$
    \item Healthcare: $0.08 \times \text{money}_2$
    \item Environment: $0.12 \times \text{money}_3$
\end{itemize}

No charity can receive more than \$50,000.

\begin{enumerate}
    \item How should the \$100,000 be allocated to maximize the minimum impact across the three charities?
    \item If the maximum donation to each charity is increased to \$60,000, how does the allocation change?
\end{enumerate}

\newpage

\section*{Problem 3}

The MS\&E department is conducting a budgeting exercise, where a fixed budget needs to be allocated across multiple projects. Each project has an associated cost and benefit score. Fractional funding of projects is allowed. Each project has:
\begin{itemize}
    \item A \textit{cost} (the amount required to fund the project fully),
    \item A \textit{benefit score} (the total benefit to the department if fully funded). 
\end{itemize}

The department has \$100,000 and four projects with the following characteristics:

\[
\begin{array}{c|c|c}
\text{Project} & \text{Cost (in \$)} & \text{Benefit Score} \\
\hline
1 & 50,000 & 60 \\
2 & 40,000 & 50 \\
3 & 30,000 & 40 \\
4 & 20,000 & 35 \\
\end{array}
\]
\subsection*{Part 1:}
\begin{enumerate}
    \item The goal is to allocate the budget to maximize the total benefit. Formulate and solve the budgeting problem as a linear program, where the decision variables represent the fraction of each project’s cost to be funded.
    \item Interpret the results: Which projects receive full, partial, or no funding? What is the total benefit achieved?
\end{enumerate}



\subsection*{Part 2: Fairness Constraints}
The department has introduced the following fairness constraints:
\begin{itemize}
    \item The allocation to \textit{Project 3} must be at least \$10,000.
    \item The sum of allocations to \textit{Projects 1 and 2} must be at most \$60,000.
    \item \textit{Project 4} must receive at least as much funding as \textit{Project 3}.
\end{itemize}

\begin{enumerate}
    \item Modify the original LP to include these fairness constraints.
    \item Solve the updated problem and discuss how the fairness constraints affect the allocation and total benefit.
\end{enumerate}

\newpage 

\section*{Problem 4}

A company is trying to assign three workers to three different projects. Each worker has a different skill level for each project, and each project has a certain demand for worker skills. The company wants to maximize the total skill matching while ensuring fairness in both compensation and job assignments. Each worker can only be assigned to one project, and each project must be assigned to exactly one worker.


Let the skill levels of the workers for each project be represented by the following table:

\[
\begin{array}{c|c|c|c}
\text{Worker} & \text{Project 1} & \text{Project 2} & \text{Project 3} \\
\hline
\text{Worker 1} & 7 & 6 & 5 \\
\text{Worker 2} & 5 & 8 & 7 \\
\text{Worker 3} & 6 & 5 & 9 \\
\end{array}
\]


\textbf{Part 1: Basic Assignment Problem} \\
Maximize the total skill level of the assignments. Is it possible to find an integer optimal solution? Is there an integer basic feasible solution?

\vspace{0.5cm}

\textbf{Part 2: Fair Assignment with Compensation and Satisfaction} \\
In addition to maximizing the total skill level of the assignments, the company wants to ensure fairness in both compensation and worker satisfaction.
Each worker has a preference score for each project based on factors like job suitability, location, and role satisfaction. The preference scores for the projects are given by:

\[
\begin{array}{c|c|c|c}
\text{Worker} & \text{Project 1 Preference} & \text{Project 2 Preference} & \text{Project 3 Preference} \\
\hline
\text{Worker 1} & 3 & 8 & 6 \\
\text{Worker 2} & 7 & 5 & 9 \\
\text{Worker 3} & 6 & 6 & 7 \\
\end{array}
\]

A higher score indicates a stronger preference for a project. Workers assigned to projects with lower preference scores should be compensated more to maintain fairness.

\textbf{Compensation and Fairness:} \\
Each project has a fixed base salary:

\[
\begin{array}{c|c|c|c}
\text{Project} & \text{Base Salary (in \$)} \\
\hline
\text{Project 1} & 100,000 \\
\text{Project 2} & 120,000 \\
\text{Project 3} & 110,000 \\
\end{array}
\]

\textbf{Fairness Constraints:} \\
     \( c_i \) represents the compensation for worker \( i \).
    \( p_{ij} \) is the preference score of worker \( i \) for project \( j \).
The compensation should be inversely proportional to preferences, i.e., workers who prefer a project less are compensated more:

\[
c_i = \sum_{j=1}^3 x_{ij} \times \text{Base Salary}_j \times \frac{M - p_{ij}}{M}
\]
where \( M \) is the maximum possible preference score (here, 10), and $x_{ij}$ is the fraction of job $j$ assigned to worker $i$.
Additionally, introduce a new variable \( \Delta \), representing the difference between the highest and lowest compensations received by the workers:
\[
\Delta = \max(c_1, c_2, c_3) - \min(c_1, c_2, c_3)
\]

\textbf{Weighted Objective:} \\
The company seeks to optimize a weighted combination of the following objectives:
\begin{itemize}
    \item Maximize the total skill level of the assignments: \( \sum_{i=1}^{3} \sum_{j=1}^{3} x_{ij} \cdot \text{skill}_{ij} \).
    \item Minimize the difference between the highest and lowest compensation: \( \Delta \).
\end{itemize}
The objective is given by:
\[
\text{maximize} \left( \alpha \cdot \sum_{i=1}^{3} \sum_{j=1}^{3} x_{ij} \cdot \text{skill}_{ij} - (1 - \alpha) \cdot \Delta \right)
\]
where \( \alpha \in [0, 1] \) is a parameter that adjusts the relative importance of maximizing total skill versus minimizing the compensation gap. Solve the problem for three cases: $\alpha = 0, 5\cdot 10^{-5},$ and $1$. 
Is it always possible to find an integer optimal solution?

\newpage

\section*{Problem 5}

A farm needs to allocate a limited amount of water and fertilizer to three crops. The yield of each crop depends on both the water and fertilizer it receives, but the yield is determined by the more limiting factor — meaning the yield is the minimum of two functions: one for water and one for fertilizer.

Each crop $i$ has the following yield functions:
\begin{itemize}
    \item Crop 1:
    \[
    f_{1,W}(\text{water}_1) = 2 \times \text{water}_1, \quad f_{1,F}(\text{fertilizer}_1) = 3 \times \text{fertilizer}_1
    \]
    \item Crop 2:
    \[
    f_{2,W}(\text{water}_2) = 1.5 \times \text{water}_2, \quad f_{2,F}(\text{fertilizer}_2) = 2 \times \text{fertilizer}_2
    \]
    \item Crop 3:
    \[
    f_{3,W}(\text{water}_3) = 3 \times \text{water}_3, \quad f_{3,F}(\text{fertilizer}_3) = 1.5 \times \text{fertilizer}_3
    \]
\end{itemize}

The yield of each crop $i$ is given by:
\[
\text{yield}_i = \min \left( f_{i,W}(\text{water}_i), f_{i,F}(\text{fertilizer}_i) \right)
\]

The farm has 120 units of water and 90 units of fertilizer available to allocate across the three crops. Formulate the problem as a linear program where the objective is to maximize the minimum yield across all crops. What is the optimal yield achieved for each crop?
    


\end{document}
