В одном из проектов «возможно скоро будет запущен» используется линейное программирование для некоторых оптимизаций. Поскольку это не очень знакомая тема для меня, я начал искать примеры и инструменты, поэтому я лучше готов, когда начнутся действия. В этой публикации я покажу вам, как решать простые задачи линейного программирования, используя Microsoft Solver Foundation — бесплатный математический пакет, доступный DevLabs .
Линейное программирование используется во многих реальных расчетах: бизнес, экономика, транспорт, энергетика, телекоммуникации, производство и т. Д. Цель свята: принимать оптимальные решения и экономить ресурсы, такие как деньги, время и материалы.
Предпосылки
- Некоторая версия Visual Studio
- Фонд Microsoft Solver
- Документация Microsoft Solver Foundation
- Большая чашка кофе
Что такое линейное программирование?
Линейное программирование является частным случаем математического программирования или оптимизации. Есть линейная функция, которую мы хотим максимизировать или минимизировать, есть некоторые ограничения и неотрицательные переменные. Практически это так:
У нас есть функция, которую нужно максимизировать:
f (x, y) = c 1 x 1 + c 2 x 2 .- У нас есть ограничения, такие как:
a 1 x 1 + b 1 x 2 <= d 1 ,
a 2 x 2 + b 2 x 2 <= d 2. - Неотрицательные переменные:
x 1 > = 0,
x 2 > = 0.
У нас есть функция, которую нужно максимизировать: На основании этой информации мы найдем максимальное значение. Мы можем сделать это графически, но мы также можем рассчитать значение. На графике выше серая область называется выполнимой областью. Где-то на линиях, которые рисуют эту область, находятся точки, где расположены максимальные значения.
Пример упражнения
Я нашел несколько хороших упражнений по линейному программированию на домашней странице университета Брунеля .
- Компания производит два продукта (X и Y), используя две машины (A и B). Каждая единица X , который производится требует 50 минут времени обработки на машине A и 30 минут времени обработки на машине B. Каждый блок Y , который производится требует 24 минут времени обработки на компьютере А и 33 минут на машине В. Обработка
В настоящее время На начало текущей недели в наличии 30 единиц X и 90 единиц Y. Предполагаемое время обработки на машине A составляет 40 часов, а на машине B — 35 часов.
По прогнозам, спрос на X на текущей неделе составит 75 единиц, а на Y прогнозируется на уровне 95 единиц. Политика компании заключается в максимизации суммарной суммы единиц X и единиц Y на складе в конце недели.
Сформулируйте задачу решения, сколько из каждого продукта сделать на текущей неделе в виде линейной программы. Решите эту линейную программу графически. - Плотник делает столы и стулья. Каждый стол можно продать с прибылью в 30 фунтов, а каждый стул — с прибылью в 10 фунтов. Плотник может позволить себе тратить до 40 часов в неделю на работу, и на изготовление стола уходит шесть часов, а на изготовление стула — три часа. Потребность клиента требует, чтобы он сделал как минимум в три раза больше стульев, чем столов. Столы занимают в четыре раза больше места для хранения, чем стулья, и есть место для максимум четырех столов в неделю.
Сформулируйте эту проблему как задачу линейного программирования и решите ее графически.
Вы можете найти больше подобных упражнений при поиске в Интернете.
Использование Microsoft Solver Foundation
Теперь давайте решим одно упражнение, используя Microsoft Solver Foundation. API-интерфейс, который он предлагает, не очень знаком разработчикам, которые создают обычные веб-приложения, и требуется некоторая математика, чтобы понять, как и почему он построен таким образом. Но все же это не что-то сложное, просто немного другое.
Упражнение от Виттора . Магазин обратился к производителю с просьбой изготовить брюки и спортивные куртки.
Для материалов производитель имеет 750 м2 хлопкового текстиля и 1000 м2 полиэстера. Каждая пара брюк (1 единица) нуждается в 1 м2 хлопка и 2 м2 полиэстера. Каждой куртке требуется 1,5 м2 хлопка и 1 м2 полиэстера.
Цена штанов установлена на уровне 50 долларов, а куртки — на 40 долларов.
Какое количество брюк и пиджаков должно быть предоставлено производителем в магазинах, чтобы эти товары получили максимальную продажу?
Сначала мы должны выяснить, что является функцией максимизации и каковы ограничения. Это как описано выше.
Давайте предположим, что х = количество штанов и у = количество курток.
- Функция максимизации:
f (x, y) = 50x + 40y - Ограничения (см. Страницу Vitutor для хороших объяснений ):
2x + 3y <= 1500,
2x + y <= 1000 - Неотрицательные переменные:
x> = 0,
y> = 0.
Теперь у нас есть вся информация на основе того, что мы знаем, и пришло время написать некоторый код.
Мы создаем консольное приложение Windows и создаем ссылку на сборку Microsoft.SolverFoundation.Services, которая находится в следующем месте на вашем жестком диске:
c: \ Program Files (x86) \ Справочные сборки \ Microsoft \ Framework \ .NETFramework \ v4.0 \ Microsoft.Solver.Foundation
using Microsoft.SolverFoundation.Services;
using System;
using System.Linq;
namespace LinearProgrammingSFS
{
class Program
{
static void Main(string[] args)
{
// Create solver context and model
SolverContext context = SolverContext.GetContext();
Model model = context.CreateModel();
// Create decision for objective function
Decision x = new Decision(Domain.RealNonnegative, "pants");
Decision y = new Decision(Domain.RealNonnegative, "jackets");
model.AddDecisions(x, y);
// Add constraints
model.AddConstraints("production",
2 * x + 3 * y <= 1500,
2 * x + y <= 1000);
// Add non-negative variables
model.AddConstraints("nonnegative",
x >= 0,
y >= 0);
// Add goal - what we want to maximize
model.AddGoal("cost", GoalKind.Maximize,
50 * x + 40 * y);
Solution solution = context.Solve(new SimplexDirective());
Report report = solution.GetReport();
Console.WriteLine("result: " + solution.Goals.First().ToDouble());
Console.WriteLine("x: {0}, y: {1}", x.ToDouble(), y.ToDouble());
Console.Write("{0}", report);
Console.ReadLine();
}
}
}
Если мы запустим эту программу, мы получим следующий вывод:
Первые две строки в выводе дают нам решение: производитель должен изготовить 375 штанов и 250 курток, чтобы заработать $ 28,750, что максимально возможно. Все остальные результаты — отчет Фонда Солвера о произведенных расчетах.
Вывод
Microsoft Solver Foundation — это набор математических инструментов, которые позволяют решать некоторые математические задачи, с которыми вы сталкиваетесь в реальных приложениях. Хотя предоставляемый им API не очень похож на то, что многие из нас видели раньше, он все же достаточно прост, чтобы начать с ним, когда математическая часть ясна. В этой публикации мы решили простую задачу линейного программирования. Когда мы закончили подготовительную работу, мы написали несколько простых строк кода, чтобы получить ответы, которые мы искали. Microsoft Solver Foundation — это более широкая платформа для различных вычислений, и прежде чем писать математику вручную, я предлагаю вам взглянуть на то, что может предложить Solver Foundation.