%% It is just an empty TeX file.
%% Write your code here.
% !TEX encoding = UTF-8 Unicode
\documentclass[a4paper, 12pt]{article} % use "amsart" instead of "article" for AMSLaTeX format
\usepackage[left=20mm, top=15mm, right=10mm, bottom=15mm]{geometry}
\usepackage[parfill]{parskip} % Activate to begin paragraphs with an empty line rather than an indent
\usepackage{graphicx} % Use pdf, png, jpg, or epsç with pdflatex; use eps in DVI mode
\usepackage[14pt]{extsizes}
\usepackage{setspace,amsmath}
\usepackage{mathtools}
\usepackage{ dsfont }
\usepackage{amsmath,amssymb}
\usepackage[unicode]{hyperref}
\usepackage{xcolor}
\usepackage{color}
\usepackage{minted}
\usepackage{caption}
\usepackage{array}
\newcolumntype{P}[1]{>{\centering\arraybackslash}p{#1}}
\usepackage{cmap} % Улучшенный поиск русских слов в полученном pdf-файле
\usepackage[T2A]{fontenc} % Поддержка русских букв
\usepackage[utf8]{inputenc} % Кодировка utf8
\usepackage[english, russian]{babel} % Языки: русский, английский
% TeX will automatically convert eps --> pdf in pdflatex
\usepackage{amssymb}
\begin{document}
\begin{titlepage}
\thispagestyle{empty}
\begin{center}
Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования Московский государственный технический университет имени Н.Э. Баумана
\end{center}
\vfill
\centerline{\large{Лабораторная работа №6. Вариант 6.}}
\centerline{\large{«Методы решения задач линейного и}}
\centerline{\large{линейного целочисленного программирования»}}
\centerline{\large{по курсу}}
\centerline{\large{«Методы оптимизации»}}
\vfill
Студент группы ИУ9-81 \hfill Климов С.В.
Преподаватель \hfill Каганов Ю.T.
\vfill
\centerline{Москва, 2019}
\clearpage
\end{titlepage}
\newpage
\setcounter{page}{2}
\tableofcontents
\newpage
\section{Цель работы}
\begin{enumerate}
\item Изучение симплекс-метода линейного программирования и методов линейного целочисленного программирования.
\item Разработка программы реализации алгоритма симплекс-метода линейного программирования и алгоритмов линейного целочисленного программирования.
\item Решение задачи линейного и линейного целочисленного программирования.
\end{enumerate}
\newpage
\section{Постановка задачи}
\textbf {Дано}: 6 Вариант. Функция:
\begin{equation}
f(x) = 3x_1 + 4x_2 - 10x_3.
\end{equation}
Функции ограничений:
\begin{equation}
\begin{cases}
2x_1 + x_2 + 3x_3 = 24 \\
3 x_1 + x_2 + x_4 = 12 \\
x_1, ..., x_4 \geq 0
\end{cases}
\end{equation}
\subsection{Задача 6.1}
\begin{enumerate}
\item Найти условный максимум для задачи линейного программирования симплекс-методом Дж. Данцига.
\item Реализовать алгоритмы с помощью языка программирования высокого уровня.
\end{enumerate}
\subsection{Задача 6.2}
\begin{enumerate}
\item Найти условный максимум для задачи линейного целочисленного программирования методом «ветвей и границ».
\item Реализовать алгоритмы с помощью языка программирования высокого уровня.
\end{enumerate}
\newpage
\section{Исследование}
Найдем условный максимум для функции:
\begin{equation}
f(x) = 3x_1 + 4x_2 - 10x_3
\end{equation}
с помощью пакета scipy:
\begin{equation}
max(f(x)) = 8,\quad (x_1, x_2, x_3, x_4) = (0, 12, 4, 0)
\end{equation}
\subsection{Задача 6.1}
\subsubsection{Симлекс-метод}
Это алгоритм решения оптимизационной задачи линейного программирования путём перебора вершин выпуклого многогранника в многомерном пространстве.
Сущность метода: построение базисных решений, на которых монотонно убывает линейный функционал, до ситуации, когда выполняются необходимые условия локальной оптимальности.
\subsection{Задача 6.2}
\subsubsection{Метод ветвей и границ}
Общий алгоритмический метод для нахождения оптимальных решений различных задач оптимизации, особенно дискретной и комбинаторной оптимизации. По существу, метод является вариацией полного перебора с отсевом подмножеств допустимых решений, заведомо не содержащих оптимальных решений.
Общая идея метода может быть описана на примере поиска минимума функции $f(x)$ на множестве допустимых значений переменной $x$. Функция $f$ и переменная $x$ могут быть произвольной природы. Для метода ветвей и границ необходимы две процедуры: ветвление и нахождение оценок (границ). При этом накладывается условие целочисленности переменных.
\newpage
\section{Практическая реализация}
Все методы были реализованы на языке программирования \textbf{Python}.
\textbf{Листинг 1.} Симлекс-метод.
\begin{minted}[frame=single, framesep=10pt, fontsize = \footnotesize, linenos=true, breaklines]{python}
def simplex(A, c, b, b_idx, eps=10 ** -3):
if b_idx is None:
return None, None
k = 0
max_iters = A.shape[0] * 5
n_idx = [i for i in range(A.shape[1]) if i not in b_idx]
def get_cb():
return c[:, b_idx]
def get_cn():
return c[:, n_idx]
def get_B():
return A[:, b_idx]
def get_N():
return A[:, n_idx]
while k <= max_iters:
k += 1
Binv = np.linalg.inv(get_B())
N = get_N()
xb = np.matmul(Binv, b).reshape(-1)
cb = get_cb()
cn = get_cn()
gamma = cb @ Binv
z = gamma @ N
d = z - cn
mind = min([(i, v) for i, v in enumerate(d[0].tolist())], key=operator.itemgetter(1))
q_ind = mind[0]
q = n_idx[q_ind]
mind = mind[1]
if mind >= eps and np.min(xb) >= 0:
x = np.zeros(A.shape[1])
x[b_idx] = xb.reshape(-1)
return x, k
alphq = (Binv @ A[:, q]).reshape(-1)
beta = xb.reshape(-1)
filtered = list(filter(lambda x: x[1][1] > 0, [(i, v) for i, v in enumerate(zip(beta, alphq))]))
if len(filtered) == 0:
return None, None
p_ind = min(filtered, key=lambda v: v[1][0] / v[1][1])[0]
p = b_idx[p_ind]
b_idx[p_ind] = q
n_idx[q_ind] = p
return None, None
def get_basis(A, c, b):
m = A.shape[0]
n = A.shape[1]
A = A.tolist()
c = c.tolist()
M = 1000
for i in range(m):
added = [0] * m
added[i] = 1
A[i] += added
c[0] += [-M] * m
A = np.array(A)
c = np.array(c)
basis = simplex(A, c, b, [i + n for i in range(m)])[0]
if basis is None:
return basis
return list(map(operator.itemgetter(0), filter(lambda x: x[1] != 0, enumerate(basis))))
def two_step_simplex(A, b, c):
basis = get_basis(A, c, b)
return simplex(A, c, b, basis)
\end{minted}
\textbf{Листинг 2.} Метод ветвей и границ.
\begin{minted}[frame=single, framesep=10pt, fontsize = \footnotesize, linenos=true, breaklines]{python}
def is_int(x):
return np.allclose(x - np.round(x), np.zeros(x.shape[0]))
def branching(A, b, idx, x):
import math
newA1 = np.copy(A)
newb1 = np.copy(b)
newcons = np.zeros((1, newA1.shape[1]))
newcons[0][idx] = 1
newA1 = np.concatenate((newA1, newcons))
newb1 = np.concatenate((newb1, np.array([[math.floor(x[idx])]])))
newA2 = np.copy(A)
newb2 = np.copy(b)
newcons = np.zeros((1, newA2.shape[1]))
newcons[0][idx] = -1
newA2 = np.concatenate((newA2, newcons))
newb2 = np.concatenate((newb2, np.array([[-(math.floor(x[idx]) + 1)]])))
return newA1, newb1, newA2, newb2
def lab62():
import scipy.optimize
two_step_simplex = lambda A, b, c: scipy.optimize.linprog(-c.reshape(-1), A_eq=A, b_eq=b.reshape(-1)).x
A = np.array([
[2, 1, 3, 0],
[3, 1, 0, 1]
])
c = np.array([[3, 4, -10, 0]])
b = np.array([
[24],
[12]
])
k = 0
f = lambda x: (x @ c.transpose())[0]
x = two_step_simplex(A, b, c)
if np.isnan(x).any():
return None, None, None
f_val = f(x)
if is_int(x):
return x, f_val, 1
q = [(f_val, x, A, b)]
xs = []
max_iters = 30
while q:
fs = [x[0] for x in q]
maxind = max(enumerate(fs))[0]
new_f, new_x, new_a, new_b = q.pop(maxind)
filtered = list(filter(lambda v: not abs(v[1] - round(v[1])) <= 10 ** -8, enumerate(new_x)))
if not filtered:
continue
idx = max(filtered, key=operator.itemgetter(0))[0]
A1, b1, A2, b2 = branching(new_a, new_b, idx, new_x)
x = two_step_simplex(A1, b1, c)
if not np.isnan(x).any():
if is_int(x):
xs.append(x)
q.append((f(x), x, A, b))
x = two_step_simplex(A2, b2, c)
if not np.isnan(x).any():
if is_int(x):
xs.append(x)
q.append((f(x), x, A, b))
if k > max_iters:
break
k += 1
if len(xs) == 0:
return None, None, k
maxx = max(xs, key=f)
return maxx, f(maxx), k
\end{minted}
\newpage
\section{Результаты.}
Программы, представленные в \textbf{Листинге 1} и \textbf{Листинге 2} дали следующие результаты:
\textbf{Листинг 5.} Результаты выполнения программ.
\begin{minted}[frame=single, framesep=10pt, fontsize = \footnotesize, linenos=true, breaklines]{text}
Симплекс метод:
k = 3
x = (0,12,4,0)
f(x) = 8
Метод ветвей и границ:
k = 1
x = (0,12,4,0)
f(x) = 8
\end{minted}
\end{document}