\documentclass{article}
%\usepackage{stix2}
\pdfoutput=1
\usepackage[utf8]{inputenc}
\usepackage[a4paper, margin=1in]{geometry}
\usepackage[active]{srcltx}
\usepackage{babel}
%\usepackage{stix}
\usepackage{verbatim}
\usepackage{mathtools}
\usepackage{bm}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{microtype,comment}
\usepackage{graphicx}
\usepackage{caption}
\usepackage{subcaption}
%\usepackage{subfigure}
\usepackage{booktabs} 
\usepackage{verbatim}
\usepackage{mathtools}
\usepackage{bbm}
\usepackage{amsmath}
\usepackage{amssymb} 
\usepackage{amsthm}
\usepackage{babel}
\usepackage{amsthm}
\usepackage{dsfont}
\usepackage{array}
\usepackage{mathrsfs}
\usepackage{color}
\usepackage{natbib}
\usepackage{enumerate}
\usepackage{comment}
\usepackage{url}[sf]
\usepackage{needspace}
\usepackage{enumitem}
\usepackage{etoolbox}
\usepackage[2col]{optional} % 2col/arxiv
\DeclarePairedDelimiterX\set[1]\lbrace\rbrace{\def\given{\;\delimsize\vert\;}#1}

\newlist{pfparts}{description}{1}
\setlist[pfparts,1]{%
  font=\normalfont\textsf,
  itemindent=2pt,
  wide,
  itemsep=0pt,topsep=2pt,
  labelsep=0.75ex
}


\usepackage{tikz}
\usepackage{tikzscale}
\usepackage{pgfplots}
\usepackage{lineno}


%\usepackage{style}

\pgfplotsset{compat=1.17}
\usetikzlibrary{calc}
\usetikzlibrary{positioning}
\usetikzlibrary{intersections}
\usetikzlibrary{backgrounds}

 \bibpunct[, ]{(}{)}{,}{a}{}{,}%
 \def\bibfont{\small}%
 \def\bibsep{\smallskipamount}%
 \def\bibhang{24pt}%
 \def\newblock{\ }%
 \def\BIBand{and}%


% \def\lowint{\mkern3mu\underline{\vphantom{\intop}\mkern40mu}\mkern-20mu\int}
% % %\def\lowiint{\mkern3mu\underline{\vphantom{\intop} \vphantom{\intop} \mkern7mu}\mkern-10mu\iint}

%  \def\upint{\mathchoice%
%     {\mkern3mu\overline{\vphantom{\intop}\mkern40mu}\mkern-20mu}%
%     {\mkern7mu\overline{\vphantom{\intop}\mkern40mu}\mkern-14mu}%
%     {\mkern7mu\overline{\vphantom{\intop}\mkern40mu}\mkern-14mu}%
%     {\mkern7mu\overline{\vphantom{\intop}\mkern40mu}\mkern-14mu}%
%   \int}

% \newcommand{\lowint}[1]{
%   \underline{\int_{#1}}
% }
% \newcommand{\lowint}[2][\text{}]{
%   \underline{\int_{#1}^{#2}}
% }

% \newcommand{\upint}[1]{
%   \overline{\int_{#1}}
% }
% \newcommand{\upint}[2]{
%   \overline{\int_{#1}^{#2}}
% }
\newtheorem{example}{Example}

% \theoremstyle{plain} 
% \newtheorem{lemma}{\textbf{Lemma}} 
% \newtheorem{proposition}{\textbf{Proposition}}
% \newtheorem{theorem}{\textbf{Theorem}}\setcounter{theorem}{0}
% \newtheorem{corollary}{\textbf{Corollary}} 
% \newtheorem{assumption}{\textbf{Assumption}}
% \newtheorem{example}{\textbf{Example}} 
% \newtheorem{definition}{\textbf{Definition}}
% \newtheorem{fact}{\textbf{Fact}}
% \newtheorem{property}{Property}
% \theoremstyle{definition}
% \theoremstyle{remark}
% \newtheorem{condition}{Condition}
% \newtheorem{claim}{Claim}
% \newtheorem*{claim*}{Claim}
% \newtheorem*{lemma*}{Lemma}
% \newtheorem*{theorem*}{Theorem}
% \newtheorem{case}{Case}
% %\theorempostwork{\setcounter{case}{0}}
% \newtheorem{conjecture}{Conjecture}
% \newtheorem{remark}{\textbf{Remark}}
%  \newcommand{\vect}{\textbf} 

\usepackage{braket}
\newcommand{\vect}{\textbf} 

%\theorempostwork{\setcounter{case}{0}}
\DeclarePairedDelimiter\ceil{\lceil}{\rceil}
\DeclarePairedDelimiter\floor{\lfloor}{\rfloor}
\DeclareMathOperator*{\argmax}{arg\,max}
\DeclareMathOperator*{\argmin}{arg\,min}
\newcommand{\defeq}{:=}
\newcommand{\rhovaname}{\rho_{V}}
\newcommand{\rhovbname}{\rho_{VB}}
\newcommand{\rhova}[1]{\rhovaname\left( #1 \right)}
\newcommand{\loRiemannint}[2]{
  \underline{\int_{#1}^{#2}}
}
\newcommand{\rhovb}[1]{\rhovaname\left( #1 \right)}
\newcommand{\Aball}[2]{\mathcal{B}_{#1,#2}}
\newcommand{\Aballsize}[2]{\left| \Aball{#1}{#2} \right|}
\newcommand{\ballsize}[1]{\left| \mathcal{B}_{#1} \right|}

\definecolor{mor}{rgb}{0.8, 0.5, 0.0}
%\newcommand{\zhihao}[1]{ {\color{mor} [ Zhihao: {#1} ]  } }
\newcommand{\sss}[1]{ {\color{orange} [ Sahasrajit: {#1} ]  } }

%\newcommand{\ak}[1]{ {\color{mor} [ Aleksandra: {#1} ]  } }

 \makeatletter
\def\namedlabel#1#2{\begingroup
    #2%
    \def\@currentlabel{#2}%
    \phantomsection\label{#1}\endgroup
}
\makeatother

\makeatletter
\let\original@footnote\footnote
\newcommand{\align@footnote}[1]{%
  \ifmeasuring@
    \chardef\@tempfn=\value{footnote}%
    \footnotemark
    \setcounter{footnote}{\@tempfn}%
  \else
    \iffirstchoice@
      \original@footnote{#1}%
    \fi
  \fi}
\pretocmd{\start@align}{\let\footnote\align@footnote}{}{}
\makeatother


\title{\textbf{Homework on logistics/finance} }
\begin{document}
\maketitle
        \noindent
%Electronic submission to Gradescope due on {\bf 5:00pm Wednesday 5/15}.
% \section{Solving optimization problems in python}

% Familiarise yourself with solving optimization problems in python. You may use some common softwares like \cite[CVXPY]{diamond2016cvxpy}, \cite[OR-Tools]{or-tools}. You may visit \url{cvxpy.org} for some examples on how to use cvxpy for the formulation of convex optimization problems. To gain more familiarity, formulate and solve the following problem on an LP solver. A linear program is formulated and solved in the colab notebook \\
% \url{https://colab.research.google.com/drive/1dAQF02yok3Y7SUUtoMq69_Hn7DYp8Xxf?usp=sharing}. 

% The required python scripts are formulated and described in the colab notebook \\\url{https://colab.research.google.com/drive/1XnRa3XcHKAz4hC9jFKgUpPzjyK_M1FHn?usp=sharing} and \\\url{https://colab.research.google.com/drive/1vFs6ECjiSBGdY3PCG6G9yO_RQVzfyup_?usp=sharing}..

%Please do not directly edit the colab notebook. Make a copy of the notebook and then solve the problems on it. While submitting please attach the relevant python scripts and/or excel files to enable us to give partial credits. %Please send the required excel files to us (on the staff mailing list \url{msande214-spr2324-staff@lists.stanford.edu}) on email and paste the required urls for the colab files on the submitted pdf.

The data for most of the problem files are given in Homework3.xlsx


\section*{Problem 1}

    MSE Airlines needs to hire customer
service agents. Research on customer demands has led to the
following requirements on the minimum number of customer service
agents that need to be on duty at various times in any given day:
\begin{center}
	\begin{tabular}{|c|c|}
		\hline
		Time Period & staff Required \\ \hline
		6am to 8am & 68 \\
		8am to 10am & 90 \\
		10am to noon & 56 \\
		Noon to 2pm & 107 \\
		2pm to 4pm & 80 \\
		4pm to 6pm & 93 \\
		6pm to 8pm & 62 \\
		8pm to 10pm & 56 \\
		10pm to midnight & 40 \\
		Midnight to 6am & 15 \\
		\hline
	\end{tabular}
\end{center}
The head of personnel would like to determine the least expensive way to
meet these staffing requirements. Each agent works an 8 hour shift,
but not all shifts are available. The following table gives the
available shifts and daily wages for agents working various shifts:
\begin{center}
	\begin{tabular}{|c|c|}
		\hline
		Shift & Daily Wages \\ \hline
		6am-2pm & \$180 \\
		8am-4pm & \$170 \\
		10am-6pm & \$160 \\
		Noon-8pm & \$190 \\
		2pm-10pm & \$200 \\
		4pm-Midnight & \$210 \\
		10pm-6am & \$225 \\
		Midnight-8am & \$210\\
		\hline
	\end{tabular}
\end{center}

\begin{enumerate}
	\item Write a linear program that determines the
	least expensive way to meet staffing requirements.

	\item Solve the linear program using Excel.
\end{enumerate}

\section*{Problem 2}

The cities of Palu and Donggala have been affected by floods and an international agency has decided to help. Suppose you are in charge of coordinating an aid campaign to bringing medicaments from three different cities (Shanghai, Delhi and Mumbai) to the cities of Palu and Donggala. The logistics group of the project determined that the best way to do it is in two phases. First, bring the medicaments from the origin cities to an intermediate transfer city (Jakarata, Surabaya, Bandung are the possible transfer cities), and then send them to the destination cities. Assume that there is only one type of medicament.

The origin city $i$ ($i = 1,\ldots,I$) has an availability of medicaments equal to $S_i$. You are not required to use up all the available supply at an origin city. The warehouse at transfer city $j$ ($j = 1,\ldots,J)$ has a capacity $T_j$; that is, no more than $T_j$ units of medicaments can go through transfer city $j$. Everything that goes into transfer city $j$ must go out to some destination city. The destination city $k$ ($k = 1,\ldots, K$) has a demand $D_k$ of medicaments, which must be satisfied. The unit transportation cost from city $i$ to the transfer city $j$ is $c_{ij}$, for $i = 1,\ldots, I$ and $j = 1,\ldots,J$. The unit transportation cost from the transfer city $j$ to the destination city $k$ is $d_{jk}$, for $j = 1,\ldots,J$ and $k = 1,\ldots,K$.

\begin{enumerate}
	\item Formulate a min-cost flow problem that minimizes the total transportation costs while satisfying the demand requirements of each city, without violating the availability and capacity constraints.

    \textbf{Hint:} To model the capacity constraints of a node, one can construct some ``dummy'' nodes and edges. To model the fact that not all the supply has to be used up, you can use another dummy node that uses up the excess supply. But in this problem, instead of using dummy nodes, you should also feel free to modify the min-cost flow formulation so that (a) some of the conservation constraints are ``$\le$" constraints, to capture the fact not all the supply has to be used, and (b) There are additional constraints on the total incoming flow into a transfer city.


	\item Suppose the origin cities are Delhi with an availability of 1,200 (units are in thousands of medicaments), Shanghai with an availability of 1,200, and 
    Mumbai with an availability of 1,200.
 There are three transfer cities: Jakarta with a capacity of 800, Surabaya with a capacity of 1,500 and Bandung with capacity of 800. The destination cities are: Palu and Donggala with demandz of 1,500 and 1,500 respectively. The unit costs of transportation are given in the following tables (in thousands of dollars per thousands of medicaments):
	\begin{center}
		\begin{tabular}{|c|c|c|c|}
			\hline
			& Jakarta & Surabaya & Bandung\\ \hline 
			 Delhi & 10 & 12 & 25\\ \hline
			 Shanghai & 7 & 8 & 15\\
			\hline
               Mumbai & 5 & 8 & 10\\
			\hline
		\end{tabular}
	\end{center}
	
	\begin{center}
		\begin{tabular}{|c|c|c|}
			\hline
			& Palu & Donggala \\ \hline 
			Jakarta & 20 & 15 \\ \hline
			Surabaya & 15 & 20 \\ \hline
                Bandung & 10 & 16 \\ \hline
			%\hline
		\end{tabular}
	\end{center}
	Solve the problem by either (a) Solving the min-cost flow problem from part 1, or (b) Directly formulating as an LP and solving it.
	
\item Use the values of the dual variables (on Excel's sensitivity sheet) to answer the following. Suppose you can invest at the same cost in expanding the availability at one of the origin cities by one unit or expanding the capacity at one of the transfer cities by one unit. In which would you invest? Why? Suppose you have to provide an additional unit of medicament to one of the destination cities. Which is the most expensive one to provide it to? Why?

   \textbf{Hint:} This part will be easier if you followed our suggestion in the hint of the first part of this problem to modify the min-cost flow LP as opposed to adding dummy nodes.
 
\end{enumerate}

\section*{Problem 3}

A manufacturer in the United States is considering an order from a retailer in China that wishes to purchase
100,000 units of a vehicle telematics system for Y70 million Chinese Yuan.
Producing components would cost the manufacturer \$5 million. The components could then be assembled in the US for \$4 million, or the assembly can
be handled in China by the retailer, in which case the retailer wants a Y20
million price reduction. The manufacturer will be paid by the retailer when
the components or assembled units are shipped, which is planned for three
months from now. The manufacturer can wait until then to decide whether
to assemble the units in the US. The manufacturer can also decide then not
to ship anything to China and instead sell the components to dealers in the
US for \$3 million.
The manufacturer is interested in this opportunity but is concerned that
the recently volatile exchange rate will influence profitability. In particular,
if $y$ is the dollar price of Yuan come delivery time three months
from now, the manufacturer’s profit in millions of dollars will be the largest
among $70y-9$, $50y-5$, and $-2$. The first expression is the profit if the units
are assembled in the US, the second is for the case where components are
shipped, and the third represents the loss incurred if the components are sold
to dealers in the US.

\begin{enumerate}
    
    \item The manufacturer has also access to 3 other financial instruments. He can buy a) Yuan currency b) a zero coupon-bond with a face-value of 1 USD c) call option of Yuan/USD (Yuan priced in USD) with a strike of 0.1.  Let us assume that the Yuan currency is currently priced at 0.15 USD and the call option is priced at 0.07 respectively.

Provide a minimum cost portfolio which gives no future liability and formulate this problem as a linear program. More precisely, the total payoff in the future (i.e. the payoff from the portfolio plus the payoff from the manufacturing operation ($\max(70y-9, 50y-5,-2)$) is non-negative.

\textbf{Hint}: You may solve by formulating it as a linear program by considering various different dollar price of Yuan come delivery time three months
from now.

    \item The goal in this part is not to cover any future liabilities, but to do arbitrage. Along with the three previously mentioned financial options, the manufacturer also has access to a Yuan/USD put option with a strike price of 0.15 priced at 0.03 USD.

    \textbf{Hint}: You may solve by formulating it as linear program by considering various different dollar price of Yuan come delivery time three months from now.

Formulate a linear program to check if there exists an arbitrage opportunity. 
\end{enumerate}


% \subsection*{Part a}




% \subsection*{Part b}

 %Also, find the most lucrative arbitrage opportunity at the least cost.


\section*{Problem 4}

In this problem $\mathbbm{R}_{\geq 0}$ denotes the set of non-negative reals.

Consider a portfolio of 4 assets with the covariance matrix $V$ and expected return $\mu$ described in attached excel file (check sheet ``Problem 4''). Assuming that the covariance matrix is positive semi-definite, find a portfolio $p \in \mathbbm{R}_{\geq 0}^4$ which maximises expected return minus $\lambda$ times the variance ($\mu^Tp -\lambda p^TVp$) ensuring that the portfolio $p$ has a norm of 1 and is non-negative.  


\section*{Problem 5}
% \section*

% \paragraph{Problem 1}
	\ \\
	\begin{figure}[h!]
		\centering 
		\vspace{-.4in}\ \\
		\centering\includegraphics[height=1.5in]{ps4}
		\\
	\end{figure}
	
	
	Consider the oil pipeline network in the figure above. The table below gives the capacity of each pipeline (in million gallons per hour), the cost per million gallons of sending oil over a pipeline, and the failure probability.
	
	\vspace{6pt}
	\begin{center}
		\begin{tabular}{c|ccc}
			\hline
			Edge & Capacity & Cost & Failure Prob.\\
			\hline
			AC & 5 & \$7000 & .4\\
			AD & 4 & \$4000 & .9\\
			AS & 2 & \$1000 & .1\\
			CD & 1 & \$2000 & .2\\
			CT & 1 & \$4000 & 0\\
			DT & 3 & \$2000 & .5\\
			DF & 1 & \$2000 & .1\\
			SD & 1 & \$1000 & .3\\
			SF & 2 & \$3000 & .4\\
			SG & 2 & \$5000 & .2\\
			FB & 1 & \$2000 & .2\\
			FT & 4 & \$6000 & .2\\
			GT & 5 & \$0 & 1\\
			TB & 2 & \$1000 & .6\\
			GB & 2 & \$2000 & .8\\
			\hline
		\end{tabular}
	\end{center}
	\vspace{6pt}
	
	For each of the following, construct 
        a flow problem whose solution gives the desired information and solve in Excel:
 %a min-cost flow graph whose solution gives the desired information and solve in Excel:
	\begin{enumerate}
		% \item the cheapest way of sending $1$ million gallons per hour from $A$ to $B$
		% \item the cheapest way of sending $5$ million gallons per hour from $A$ to $B$
		\item the most reliable path from $A$ to $B$.  Assume that failure probabilities along different edges are independent of each other.

  \textbf{Hint}: The cost of the flow graph may be given as an appropriate function of the failure probabilities.
		\item the maximum amount of oil that can be sent from $A$ to $B$.
	\end{enumerate}
    
% \textbf{Hint}: One may define the min-cost flow graph with the cost of every edge chosen approp
        
\end{document}