Виды задач линейного программирования
- Задача линейного программирования: основные определения
- Примеры формулировки (модели) задач линейного программирования
- Сведение любой задачи линейного программирования к канонической
- Основные теоремы линейного программирования
Линейное программирование – метод решения задач оптимизации.
В первых оптимизационных задачах требовалось выяснить, сколько различных изделий
нужно произвести, чтобы получить максимальный доход, если известно количество ресурсов (сырья,
рабочего времени, оборудования) и цены, по которым можно реализовать готовые изделия. Другой вид задач –
выяснить, при каких условиях свести расходы к минимуму (это, например, задача о питании). Таким образом, общая задача линейного программирования – это задача, в которой требуется найти максимум или минимум
(оптимум) функции, называемой функцией цели, при ограничениях, заданных системой линейных неравенств
или уравнений.
При этом переменные чаще всего по условиям задачи должны принимать неотрицательные значения (то есть положительные либо нулевые), но бывают и исключения, о которых чуть ниже.
Функция цели в задаче линейного программирования обычно записывается так:
.
Или в сокращённом виде с сигмой:
.
Можно встретить обозначение целевой функции и через C, и через F.
Система ограничений в задаче линейного программирования в канонической форме записывается так:
.
Или в сокращённом виде:
И система ограничений, и целевая функция имеют линейный характер, то есть содержат переменные только в первой степени.
Канонической задачей линейного программирования называется задача, в которой,
как было показано выше, требуется найти максимум целевой функции при ограничениях, заданных системой
линейных уравнений.
Задачей линейного программирования в стандартной, или, как говорят иначе, нормальной форме, называется задача, в которой требуется найти максимум целевой функции при ограничениях, заданных системой неравенств одного смысла, то есть с одинаковым знаком, и этот знак — «меньше или равно», причём действует также условие неотрицательности переменных. Если в задаче линейного программирования, заданной в стандартной форме, требуется найти минимум целевой функции, то система ограничений состоит из системы неравенств со знаком «больше или равно».
Задачей линейного программирования в общей форме, или, как говорят иначе, в смешанной
форме, называется задача, в которой требуется найти максимум или минимум целевой функции, а
система ограничений может включать в себя неравенства с различными знаками, а также уравнения, то есть равенства.
При этом в задаче, заданной в общей форме, условие неотрицательности переменных не обязательно соблюдается, то есть некоторые переменные
могут быть без ограничения знака, а для некоторых (как впрочем, иногда и всех) переменных может быть
задано условие неположительности.
Если все или некоторые ограничения в системе заданы неравенствами, то задачу можно свести к канонической путём преобразования неравенств в уравнения.
Множество чисел (запись последовательности иксов), удовлетворяющих системе ограничений, называется решением этой системы. Решение системы также часто называется планом, и немного реже – программой, но именно отсюда и пошло название «линейное программирование».
Оптимальным решением задачи линейного программирования называется решение системы, при которых функция цели обращается в максимум или минимум, в зависимости от условия задачи, или в общем смысле – в оптимум.
Решение задачи линейного программирования называется вырожденным, если в нём некоторые переменные равны нулю. В противном случае решение является невырожденным.
Как было отмечено выше, переменные в задаче линейного программирования чаще всего должны быть
неотрицательными, но, как мы уже усвоили, общая форма записи задачи допускает и отрицательные значения
переменных.
К приведённым определениям следует добавить следующее правило, имеющее практическое значение. Для того чтобы решение задачи имело смысл, ограничения задачи линейного программирования должны быть заданы в одних и тех же единицах. Например, если фигурантами задачи линейного программирования являются трудодни, то необходимо определить, идёт ли речь о трудоднях в неделю или в месяц и определённого уточнения придерживаться на всём протяжении решения задачи.
Задачи линейного программирования в случае двух переменных можно решить и графическим методом, в случаях, когда переменных больше, применяется симплекс-метод.
На сайте есть Онлайн калькулятор
решения задач линейного программирования симплекс-методом.
Разберём несколько типов экономических задач и запишем их в виде математических соотношений. Или, говоря иначе, построим математическую модель предметной области.
Для этого, как следует из предыдущего параграфа, надо так представить предметную область, чтобы получить следующие атрибуты задачи линейного программирования.
Целевая функция. Её нужно максимизировать или минимизировать. Для того, чтобы функцию максимизировать, переменные, являющиеся её слагаемыми, должны принимать как можно большие значения в соответствии с условиями задачи. При минимизации — наоборот, меньшие. Обычно целевая функция выражает доходы или расходы.
Переменные. Каждая переменная, как правило, означает запасы одного из производственных факторов — вида сырья, времени, рабочей силы, технологических возможностей или чего-либо другого.
Ограничения.
Очень просто. Например, в каждом уравнении (неравенстве)
заданы ограничения перечисленных выше или других запасов, используемых для производства
определённого вида продукции.
Пример 1. Схема задачи использования сырья.
Сформулировать для решения как задачи линейного программирования следующую задачу.
Для изготовления двух видов продукции и требуется четыре вида ресурсов (сырья): , , , . Запасы сырья — соответственно , , , единицы.
Доход от реализации одной единицы продукции равен у. е., а доход от реализации одной единицы продукции равен у. е. Требуется получить наибольший доход от изготовления продукции и , то есть, узнать, сколько единиц и сколько единиц нужно изготовить из имеющегося запаса сырья, чтобы получить максимальный доход.
Решение. Для удобства сначала все данные запишем в виде таблицы:
| Виды сырья | Запасы сырья | Виды продукции | |
| Доход от реализации одной единицы продукции | |||
Тогда на основании таблицы запишутся неравенства (ограничения):
В самом деле, для изготовления каждой единицы продукции
необходимо
единиц сырья ,
а для изготовления
единиц требуется
единиц сырья .
Из остальных строк таблицы составим ещё 3 неравенства системы.
Доход от реализации единиц продукции по у. е. за каждую единицу составляет у. е. Аналогично доход от реализации единиц продукции по у. е. за каждую единицу составит у. е. Тогда суммарный доход от реализации двух видов продукции и запишется в виде . В задаче требуется найти максимальный доход, то есть найти максимум функции цели .
На нашем сайте есть решение числового примера этой задачи графическим методом
.На сайте есть Онлайн калькулятор решения задач линейного программирования симплекс-методом.
Нет времени вникать в решение? Можно заказать работу!
Пример 2. Схема задачи о смесях.
Сформулировать для решения как задачи линейного программирования следующую задачу.
Требуется найти наиболее дешёвый набор из доступных исходных материалов, обеспечивающих получение смеси с заданными свойствами. Полученные смеси должны иметь в свойм составе n различных компонент в определённых количествах, а сами компоненты являются составными частями m исходных материалов. Для упрощения примем, что n=3 и m=4. Пусть стоимость одной единицы материала соответственно составляет , , , . В свою очередь необходимое количество каждой из компонент в смеси составляет соответственно , , .
Решение. Строим таблицу:
| Виды материалов | Цена единицы материала | Количество компонент в материале | ||
| K1 | K2 | K3 | ||
| 1 | ||||
| 2 | ||||
| 3 | ||||
| 4 | ||||
| Необходимое количество компонент | ||||
Коэффициенты aij
показывают количество j-й компоненты в единице i-го материала K1.
Требуется получить
смесь с заданными свойствами при наименьших затратах на приобретение материалов.
Запишем задачу в виде математических соотношений. Обозначим через xi количество материалов i-го вида, входящего в смесь. Тогда задача сведётся к отысканию минимума функции
при ограничениях
Одним из частных случаев общей задачи о смесях служит задача о питании. К ней сейчас же и перейдём.
На сайте есть Онлайн калькулятор решения задач линейного программирования симплекс-методом.
Пример 3. Схема задачи о питании.
Сформулировать для решения как задачи линейного программирования следующую задачу.
Для нормального функционирования организма необходимо потреблять
ежесуточно определённое количество питательных веществ: жиров, белков, углеводов, витаминов.
Они содержатся в разных продуктах в различных количествах. Пусть стоимость одной единицы
продукта соответственно составляет ,
,
. Нужно так
организовать питание, чтобы организм получал необходимое количество питательных веществ,
а стоимость питания была бы наименьшей.
Решение. Строим таблицу:
| Питательные вещества | Норма | Продукты | ||
| Ж | ||||
| Б | ||||
| У | ||||
| В | ||||
| Стоимость питательных веществ | ||||
В таблице выше, например, число
означает количество белков, содержащихся в одной единице продукта .
Число — это
суточная норма потребления углеводов и т. д.
Запишем задачу в виде математических соотношений. В задаче неизвестно количество каждого вида продукта. Поэтому обозначим количество продукта буквой , количество продукта — буквой , количество продукта — буквой .
Получим систему неравенств (ограничений):
Требуется найти найти такое неотрицательное решение системы ограничений, при котором функция цели обращалась бы в минимум.
На сайте есть Онлайн калькулятор решения задач линейного программирования симплекс-методом.
Пример 4. Схема задачи об использовании мощностей оборудования.
Сформулировать для решения как задачи линейного программирования следующую задачу.
Предприятию требуется за время T выпустить N1 единиц продукции П1
и N2 единиц продукции П2. Каждый из этих двух видов продукции
может производиться тремя машинами A, B, C.
Составить оптимальный план работы машин, то есть найти время загрузки машин A, B, C,
с тем расчётом, чтобы стоимость изготовления всей продукции предприятием оказалась минимальной.
Мощность машин задана следующей таблицей:
| Машины | П1 | П2 |
| A | ||
| B | ||
| C |
В этой таблице — количество единиц продукции, производимое за единицу времени.
Цена одной единицы рабочего времени на изготовление одной единицы продукции на каждой машине задана следующей таблицей:
| Машины | П1 | П2 |
| A | ||
| B | ||
| C |
В этой таблице, например, число
означает цену одной единицы рабочего времени машины B, затрачиваемой
на изготовление одной единицы продукции П1.
Запишем задачу в виде математических соотношений. Неизвестным является время загрузки машин по производству продукции. Обозначим через время загрузки машины A по изготовлению продукции П1, через — время загрузки машины A по изготовлению продукции П2. Аналогично — время загрузки машины B по изготовлению продукции П1, — время загрузки машины B по изготовлению продукции П2, — время загрузки машины C по изготовлению продукции П1, время загрузки машины C по изготовлению продукции П2.
Машины A, B, C работают одновременно, значит если обозначим время одновременной работы всех трёх машин буквой T, то получим систему неравенств:
Машина A изготовлением продукции П1
занята единицы времени на
единицы продукции. Машина B изготовлением П1
занята единицы времени
по единицы продукции.
Аналогично машина C изготовлением П1 занята единицы времени, по единицы продукции и т.д. Всего нужно N1 единиц продукции П1 и N2 единицы П2.
То есть получаем ещё одну систему:
Тогда общая стоимость всей продукции запишется в виде равенства:
.
Окончательно получаем систему ограничений, состоящую из соотношений:
Задача заключается в том, чтобы найти такое неорицательное решение последней из приведённых систем, чтобы целевая функция C приняла минимальное значение.
Пример 5. Транспортная задача (схема).
Сформулировать для решения как задачи линейного программирования следующую задачу.
На двух станциях отправления и
имеется соответственно
и
единиц
некоторого груза.
Этот груз следует доставить в три пункта назначения ,
,
и в каждый
из них должно быть завезено соответственно ,
,
единиц этого
груза. Стоимость перевозки одной единицы груза из пункта
в пункт равна
.
Составить такой план перевозок, чтобы общая стоимость всех перевозок была минимальной.
Решение. Считаем, что запас всего груза на обоих пунктах отправления равен потребности в этом грузе на всех трёх пунктах назначения, т. е.
Запишем задачу в виде математических соотношений. Количество единиц груза, отправляемых из пункта в пункт , обозначим и составим матрицу перевозок (таблицу):
| Пункт отправления | Пункт назначения | Запас груза | ||
| Потребность в грузе | ||||
В таблице выше каждая клетка для пункта назначения разделена на две части.
В верхней части записана стоимость перевозки, а в нижней — количество груза. Например, в
клетке
(в клетке, расположенной на пересечении строки )
со столбцом )
число
означает стоимость перевозки из пункта
в пункт .
Тогда система ограничений запишется в виде уравнений:
Цель задачи — найти неотрицательное решение системы уравнений, при котором функция цели была минимальной.
На сайте есть статья, посвящённая решению транспортной задачи распределительным методом.
В большинстве задач линейного программирования ограничения задаются не в
виде системы уравнений, а в виде системы линейных неравенств, причём возможны различные
формы таких систем: левая часть меньше или равна (меньше) правой, левая часть больше или
равна (больше) правой. Кроме того, система ограничений может быть смешанной: часть
ограничений неравенства первого из вышеназванных типов, части — второго типа, а часть задана
в виде уравнений.
Однако любую систему ограничений можно свести к системе уравнений. Для этого достаточно к левой части каждого неравенства прибавить, если система первого типа, или отнять, если система второго типа, некоторое неотрицательное число — добавочную переменную, чтобы каждое неравенство превратилось в уравнение. Эти действия называются сведением задачи линейного программирования к канонической.
Пример 6. Записать систему неравенств
в виде уравнений для приведения задачи линейного программирования к канонической.
Решение. Прибавляя к левым частям неравенств по одной дополнительной переменной, получим систему уравнений:
Таким образом, как бы ни были первоначально заданы ограничения задачи линейного программирования, их всегда можно привести к системе уравнений, используя для этой цели добавочные переменные.
На сайте есть Онлайн калькулятор
решения задач линейного программирования симплекс-методом.
На нашем сайте также даны примеры решения задач линейного программирования графическим методом без сведения задачи к канонической и симплекс-методом с предварительным сведением задачи к канонической.
Чтобы найти оптимальное решение среди бесчисленного множества допустимых решений системы ограничений в задаче линейного программирования любого вида, понадобится ряд теорем, к рассмотрению которых мы и переходим.
Теорема 1. Множество всех допустимых решений системы ограничений задачи линейного программирования является выпуклым.
Множество решений задачи линейного программирования определяется совокупностью линейных ограничений, поэтому такое множество геометрически представляет собой выпуклый многогранник или неограниченную многогранную область, за исключением тех случаев, когда система ограничений несовместна.
О том, что такое выпуклые множества — на уроке Системы линейных неравенств
и выпуклые множества точек.
Теорема 2. Если существует, и притом единственное, оптимальное решение задачи линейного программирования, то оно совпадает с одной из угловых точек множества допустимых решений.
Эта теорема позволяет сделать вывод, что поиски оптимального решения можно ограничить перебором конечного числа угловых точек. Однако для отыскания угловых точек требуется построение области решений системы ограничений. Это построение возможно только для двух- или трёхмерного пространства, а в общем случае задача остаётся неразрешимой. Следовательно, нужно располагать каким-то аналитическим методом, позволяющим находить координаты угловых точек. Для этого понадобятся следующие две теоремы.
Теорема 3. Каждому допустимому базисному решению задачи линейного программирования соответствует угловая точка области допустимых решений системы ограничений.
Теорема 4 (обратная).
Каждой угловой точке множества
допустимых решений системы ограничений соответствует допустимое базисное решение.
Следствие. Если существует, и притом единственное, оптимальное решение задачи линейного программирования, то оно совпадает с одним из допустимых базисных решений системы ограничений.
Справедливость этого утверждения вытекает из теорем 2 и 4.
Итак, оптимум линейной формы нужно искать среди конечного числа допустимых
базисных решений. Однако даже в простейших задачах линейного программирования (при небольших
значениях m и n) нахождение оптимального решения путём рассмотрения всех
базисных решений является крайне трудоёмким процессом, поскольку число базисных решений
может быть весьма велико. Поэтому нужна какая-то вычислительная схема, позволяющая
осуществлять переход от одного допустимого базисного решения к другому, при котором линейная
форма или приблизилась к оптимуму, или, по крайней мере не изменила своего значения.
Такой
вычислительной схемой является, например, симплекс-метод решения задач линейного программирования.
| Назад | Листать | Вперёд>>> |
Нет времени вникать в решение? Можно заказать работу!
Продолжение темы «Линейное программирование»
- Графический метод решения задач линейного программирования
- Пример задачи линейного программирования: задача использования ресурсов, её графическое решение
- Симплекс-метод решения задач линейного программирования: типичный пример и алгоритм
- Симплекс-метод: случай, когда максимум целевой функции — бесконечность
- Симплекс-метод: случай, когда система не имеет ни одного решения
- Симплекс-метод: случай, когда оптимальное решение — не единственное
- Двойственная задача линейного программирования
- Решение задачи целочисленного программирования: методы и примеры
- Решение транспортной задачи распределительным методом на примерах
Поделиться с друзьями
Пример решения задачи линейного программирования графическим методом
Find:
Highlight allMatch case
Current View
Current View
Automatic ZoomActual SizeFit PageFull Width50%75%100%125%150%200%300%400%
Enter the password to open this PDF file:
File name:
—
File size:
—
Title:
—
Author:
—
Subject:
—
Keywords:
—
Creation Date:
—
Modification Date:
—
Creator:
—
PDF Producer:
—
PDF Version:
—
Page Count:
—
Ваулина В.
А.,
УрГЭУ
Пример решения задачи линейного программирования
графическим методом
Линейное программирование — это раздел математики, в котором
рассматриваются методы решения экстремальных задач с линейным
функционалом и линейными ограничениями.
Существуют два наиболее распространенных способа решения задач
линейного
программирования: графический
метод и симплекс-метод.
Графический метод существенно нагляднее и обычно проще для понимания
решения. Также этот метод позволяет практически одновременно найти
решение на минимум и максимум.
Основные шаги по решению ЗПЛ графическим методом следующие:
построить область допустимых решений задачи (выпуклый многоугольник),
который определяется как пересечение полуплоскостей, соответствующих
неравенствам задачи, построить линию уровня целевой функции, и, наконец,
двигать линию уровня в нужном направлении, пока не достигнем крайней
точки области — оптимальной точки (или множества).
В отличие от графического метода, симплексный метод практически не
имеет ограничений на задачу, может быть любое количество переменных и
т.
п. При решении задачи симплексным методом вычисления ведутся в
таблицах. Решение задачи данным методом дает не только оптимальное
решение, но и решение двойственной задачи, остатки ресурсов и т.п.
Рассмотрим
решение
задачи
линейного
программирования
графическим методом.
Для производства столов и стульев мебельная фабрика использует три
вида древесины. Норма затрат для каждого вида древесины на один стол составляет 1; 2; 5; на один стул – 1; 5; 2. Запасы древесины – 150; 600; 600.
Прибыль от реализации одного стола – 200р, одного стула – 100р. Составить
оптимальный план производства, обеспечивающий максимальную прибыль.
Решение.
Составим математическую модель задачи. Пусть Х — столы, У — стулья,
I,II,III – виды древесины соответственно.
I
II
III
Прибыль
X
1
2
5
200
Y
1
5
2
100
150
600
600
Общий запас
Составим неравенства по полученной таблице:
{
x 1+ x2 ≤150,
2 x 1+5 x 2 ≤600,
5 x 1 +2 x 2 ≤600,
x1,2 ≥ 0.
}
F ( x )=200 x 1+100 x 2 → max
Применим описанные выше шаги решения.
Построим область допустимых решений.
Рассмотрим целевую
функцию задачи F = 200×1+100×2 → max и построим вектор-градиент,
составленный из коэффициентов целевой функции. Так как нас интересует
максимальное решение, то опорную прямую двигаем прямую до последнего
касания обозначенной области.
Получаем оптимальную точку D. Так как точка D получена в результате
пересечения прямых (1) и (3), то ее координаты удовлетворяют уравнениям
этих прямых:
x1+x2=150
5×1+2×2=600
Решив систему уравнений, получим: x1 = 100, x2 = 50
Откуда
найдем
максимальное
значение
целевой
функции:
F(X) = 25000.
На примере данной задачи мы рассмотрели решение задачи линейного
программирования графическим методом. Этот метод наглядно показывает
область дополнительных решений и нахождение оптимальной точки.
Руководитель: Кныш А.А.
Линейное программирование — определение, формула, задача, примеры
Линейное программирование — это процесс, который используется для определения наилучшего результата линейной функции. Это лучший способ выполнить линейную оптимизацию, сделав несколько простых предположений.
Линейная функция известна как целевая функция. Отношения в реальном мире могут быть чрезвычайно сложными. Однако линейное программирование можно использовать для изображения таких отношений, что упрощает их анализ.
Линейное программирование используется во многих отраслях, таких как энергетика, телекоммуникации, транспорт и производство. Эта статья проливает свет на различные аспекты линейного программирования, такие как определение, формула, методы решения задач с использованием этого метода и соответствующие примеры линейного программирования.
| 1. | Что такое линейное программирование? |
| 2. | Формула линейного программирования |
| 3. | Как решать задачи линейного программирования? |
| 4. | Методы линейного программирования |
| 5. | Приложения линейного программирования |
6. | Часто задаваемые вопросы по линейному программированию |
Что такое линейное программирование?
Линейное программирование, также сокращенно LP, представляет собой простой метод, который используется для изображения сложных отношений реального мира с помощью линейной функции. Элементы полученной таким образом математической модели имеют линейную зависимость друг от друга. Линейное программирование используется для выполнения линейной оптимизации для достижения наилучшего результата.
Определение линейного программирования
Линейное программирование можно определить как метод, который используется для оптимизации линейной функции для достижения наилучшего результата. Эта линейная функция или целевая функция состоит из ограничений линейного равенства и неравенства. Мы получаем наилучший результат, минимизируя или максимизируя целевую функцию.
Примеры линейного программирования
Предположим, почтальон должен доставить 6 писем в день из почтового отделения (расположенного в A) в разные дома (U, V, W, Y, Z).
Расстояние между домами указано на линиях, как показано на изображении. Если почтальон хочет найти кратчайший маршрут, который позволит ему доставлять письма, а также экономить топливо, то это становится задачей линейного программирования. Таким образом, LP будет использоваться для получения оптимального решения, которое будет кратчайшим маршрутом в этом примере.
Формула линейного программирования
Задача линейного программирования будет состоять из переменных решения, целевой функции, ограничений и неотрицательных ограничений. Переменные решения, x и y, определяют результат задачи LP и представляют окончательное решение. Целевая функция Z — это линейная функция, которую необходимо оптимизировать (максимизировать или минимизировать), чтобы получить решение. Ограничения — это ограничения, которые накладываются на переменные решения, чтобы ограничить их значение. Переменные решения всегда должны иметь неотрицательное значение, которое задается неотрицательными ограничениями.
Общая формула задачи линейного программирования приведена ниже:
Целевая функция: Z = ax + by
Ограничения: cx + dy ≤ e, fx + gy ≤ h. Неравенства также могут быть «≥»
Неотрицательные ограничения: x ≥ 0, y ≥ 0
Как решать задачи линейного программирования?
Самая важная часть решения задачи линейного программирования — сначала сформулировать задачу, используя данные. Шаги для решения задач линейного программирования приведены ниже:
- Шаг 1: Определите переменные решения.
- Шаг 2: Сформулируйте целевую функцию. Проверьте, нужно ли минимизировать или максимизировать функцию.
- Шаг 3: Запишите ограничения.
- Шаг 4: Убедитесь, что переменные решения больше или равны 0. (Неотрицательное ограничение)
- Шаг 5: Решите задачу линейного программирования с помощью симплексного или графического метода.
Давайте подробно рассмотрим эти методы в следующих разделах.
Методы линейного программирования
Существует два основных метода решения задачи линейного программирования. Это симплексный метод и графический метод. Ниже приведены шаги для решения задачи линейного программирования с использованием обоих методов.
Линейное программирование с помощью симплекс-метода
Симплекс-метод в lpp можно применять к задачам с двумя или более переменными решения. Предположим, что целевая функция Z = 40\(x_{1}\) + 30\(x_{2}\) должна быть максимизирована, а ограничения заданы следующим образом:
\(x_{1}\) + \(x_{2}\) ≤ 12
2\(x_{1}\) + \(x_{2}\) ≤ 16
\(x_{1 }\) ≥ 0, \(x_{2}\) ≥ 0
Шаг 1: Добавьте еще одну переменную, известную как резервная переменная, чтобы преобразовать неравенства в уравнения. Кроме того, перепишите целевую функцию в виде уравнения.
— 40\(x_{1}\) — 30\(x_{2}\) + Z = 0
\(x_{1}\) + \(x_{2}\) + \(y_{ 1}\) =12
2\(x_{1}\) + \(x_{2}\) + \(y_{2}\) =16
\(y_{1}\) и \( y_{2}\) — переменные резерва.
Шаг 2: Постройте исходную симплекс-матрицу следующим образом:
\(\begin{bmatrix} x_{1} & x_{2} &y_{1} & y_{2} & Z & \\ 1&1 &1 &0 &0 &12 \\ 2& 1 & 0& 1 & 0 & 16 \\ -40&-30&0&0&1&0 \end{bmatrix}\)
Шаг 3: Определите столбец с самой высокой отрицательной записью. Это называется сводной колонкой. Так как -40 является самой высокой отрицательной записью, таким образом, столбец 1 будет сводным столбцом.
Шаг 4: Разделите записи в крайнем правом столбце на записи в сводном столбце. Мы исключаем записи в самой нижней строке.
12/1 = 12
16/2 = 8
Строка, содержащая наименьшее частное, идентифицируется для получения основной строки. Поскольку 8 — меньшее частное по сравнению с 12, строка 2 становится основной строкой. Пересечение опорной строки и опорного столбца дает опорный элемент.
Таким образом, поворотный элемент = 2.
Шаг 5: С помощью поворотного элемента выполнить поворот, используя свойства матрицы, чтобы все остальные записи в сводном столбце стали равными 0.
Используя элементарные операции, разделите строку 2 на 2 (\(R_{2}\ ) / 2)
\(\begin{bmatrix} x_{1} & x_{2} &y_{1} & y_{2} & Z & \\ 1&1 &1 &0 &0 &12 \\ 1& 1/2 & 0& 1 /2 & 0 & 8 \\ -40&-30&0&0&1&0 \end{bmatrix}\)
Теперь применим \(R_{1}\) = \(R_{1}\) — \(R_{2}\)
\(\begin{bmatrix} x_{1} & x_{2} &y_{1} & y_{2} & Z & \\ 0&1/2 &1 &-1/2 &0 &4 \\ 1& 1/2 & 0& 1/2 & 0 & 8 \\ -40&-30&0&0&1&0 \end{bmatrix}\)
Наконец \(R_{3}\) = \(R_{3}\) + 40\(R_{2}\ ), чтобы получить требуемую матрицу.
\(\begin{bmatrix} x_{1} & x_{2} &y_{1} & y_{2} & Z & \\ 0&1/2 &1 &-1/2 &0 &4 \\ 1& 1/2 & 0& 1/2 & 0 & 8 \\ 0&-10&0&20&1&320 \end{bmatrix}\)
Шаг 6: Проверьте, нет ли в самой нижней строке отрицательных значений. Если нет, то оптимальное решение найдено. Если да, то вернитесь к шагу 3 и повторите процесс. -10 является отрицательной записью в матрице, поэтому процесс необходимо повторить. Получаем следующую матрицу.
\(\begin{bmatrix} x_{1} & x_{2} &y_{1} & y_{2} & Z & \\ 0&1 &2 &-1 &0 &8 \\ 1& 0 & -1& 1 & 0 & 4 \\ 0&0&20&10&1&400 \end{bmatrix}\)
Записав нижнюю строку в виде уравнения, получим Z = 400 — 20\(y_{1}\) — 10\(y_{2}\).
Таким образом, 400 — это максимальное значение, которое Z может получить, когда \(y_{1}\) и \(y_{2}\) равны 0.
Кроме того, когда \(x_{1}\) = 4 и \ (x_{2}\) = 8, тогда значение Z = 400
Таким образом, \(x_{1}\) = 4 и \(x_{2}\) = 8 являются оптимальными точками и решением нашей линейной проблема с программированием.
Линейное программирование графическим методом
Если в задаче линейного программирования есть две решающие переменные, то для решения такой задачи можно легко использовать графический метод.
Предположим, нам нужно максимизировать Z = 2x + 5y.
Ограничения: x + 4y ≤ 24, 3x + y ≤ 21 и x + y ≤ 9
где x ≥ 0 и y ≥ 0.
Чтобы решить эту задачу с помощью графического метода, выполните следующие действия.
Шаг 1: Запишите все ограничения неравенства в виде уравнений.
x + 4y = 24
3x + y = 21
x + y = 9
Шаг 2: Нанесите эти линии на график, определив контрольные точки.
x + 4y = 24 — это прямая, проходящая через (0, 6) и (24, 0). [Подставив x = 0, получим точку (0, 6). Аналогично при y = 0 определяется точка (24, 0).]
3x + y = 21 проходит через (0, 21) и (7, 0).
x + y = 9 проходит через (9, 0) и (0, 9).
Шаг 3: Определите допустимую область. Допустимую область можно определить как область, ограниченную набором координат, который может удовлетворять некоторой конкретной системе неравенств.
Любая точка, лежащая на прямой x + 4y = 24 или ниже нее, удовлетворяет ограничению x + 4y ≤ 24.
Аналогично, точка, лежащая на прямой 3x + y = 21 или ниже, удовлетворяет ограничению 3x + y ≤ 21.
Кроме того, точка, лежащая на прямой x + y = 9 или ниже нее, удовлетворяет x + y ≤ 9.
Допустимая область представлена OABCD, поскольку она удовлетворяет всем трем вышеупомянутым ограничениям.
Шаг 4: Определите координаты угловых точек. Угловые точки являются вершинами допустимой области.
О = (0, 0)
А = (7, 0)
В = (6, 3). B является пересечением двух прямых 3x + y = 21 и x + y = 9. Таким образом, подставляя y = 9 — x в 3x + y = 21, мы можем определить точку пересечения.
C = (4, 5), образованное пересечением x + 4y = 24 и x + y = 9
D = (0, 6)
Шаг 5: Замените каждую угловую точку в задаче функция. Точка, дающая наибольшее (максимизирующее) или наименьшее (минимизирующее) значение целевой функции, и будет оптимальной точкой.
| Угловые точки | Z = 2x + 5y |
| О = (0, 0) | 0 |
| А = (7, 0) | 14 |
| Б = (6, 3) | 27 |
| С = (4, 5) | 33 |
| Д = (0, 6) | 30 |
33 является максимальным значением Z и находится в точке C. Таким образом, решение x = 4 и y = 5,
Приложения линейного программирования
Линейное программирование используется в нескольких реальных приложениях.
Он используется в качестве основы для создания математических моделей для обозначения реальных отношений. Некоторые приложения LP перечислены ниже:
- Производственные компании широко используют линейное программирование для планирования производства.
- Службы доставки используют линейное программирование для определения кратчайшего маршрута, чтобы минимизировать время и расход топлива.
- Финансовые учреждения используют линейное программирование для определения портфеля финансовых продуктов, которые могут быть предложены клиентам.
Связанные статьи:
- Линии
- Введение в графику
- Линейные уравнения с двумя переменными
- Решения линейного уравнения
- Математическая индукция
Важные замечания по линейному программированию
- Линейное программирование — это метод, который используется для определения оптимального решения линейной целевой функции.
- Симплекс-метод в lpp и графический метод можно использовать для решения задачи линейного программирования.
- В задаче линейного программирования переменные всегда будут больше или равны 0.
Примеры решений для линейного программирования
Примеры решений для линейного программированияOR-Notes — это серия вводных заметок по темам, подпадающим под широкий заголовок области исследования операций (ИЛИ). Они были изначально используется мной во вводном курсе ИЛИ, который я веду в Имперском колледже. Они теперь доступны для использования любыми студентами и преподавателями, заинтересованными в ИЛИ при соблюдении следующих условий.
Полный список тем, доступных в OR-Notes, можно найти здесь.
Примеры решения для линейного программирования
Пример линейного программирования 1997 г. экзамен UG
Компания производит два продукта (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 на складе в конце недели.
- Сформулируйте задачу, чтобы решить, сколько каждого продукта производить на текущей неделе в виде линейной программы.
- Решите эту линейную программу графически.
Раствор
Пусть
- x — количество единиц X, произведенных за текущую неделю
- y — количество единиц Y, произведенных за текущую неделю
тогда ограничения:
е. x >= 45, поэтому производство X >= спрос (75) — начальный запас
(30), что гарантирует удовлетворение спроса Цель: максимизировать (x+30-75) + (y+90-95) = (x+y-50)
то есть максимизировать количество единиц, оставшихся на складе в конце недели
Из диаграммы ниже видно, что максимум приходится на пересечение из х=45 и 50х + 24у = 2400
Решение одновременно, а не чтение значений с графика, мы имеем, что x = 45 и y = 6,25 со значением целевой функции 1,25
Пример линейного программирования 1995 г. экзамен UG
Показан спрос на два продукта в каждую из последних четырех недель ниже.
неделя
1 2 3 4
Спрос - продукт 1 23 27 34 40
Спрос - продукт 2 11 13 15 14
Применить экспоненциальное
сглаживание с константой сглаживания 0,7 для получения прогноза
спрос на эти товары на неделе 5.
Эти продукты производятся с использованием двух машин, X и Y. Каждая единица произведенный продукт 1 требует 15 минут обработки на машине X и 25 минут обработки на машине Y. Каждая единица продукта 2, произведено требует 7 минут обработки на машине X и 45 минут обработки на машине Y. Ожидается, что доступное время на машине X на неделе 5 составит будет 20 часов, а на машине Y на неделе 5 прогнозируется 15 часов. Каждый единица продукта 1, проданная на 5-й неделе, дает вклад в прибыль в размере 10 фунтов стерлингов. и каждая единица продукта 2, проданная на неделе 5, дает вклад в прибыль от 4 фунтов стерлингов.
Может быть невозможно произвести достаточно, чтобы удовлетворить ваш прогнозируемый спрос на эти товары в неделю 5 и на каждую единицу неудовлетворенного спроса на товар 1 стоит 3 фунта стерлингов, каждая единица неудовлетворенного спроса на продукт 2 стоит 1 фунт стерлингов.
- Сформулируйте задачу, чтобы решить, сколько каждого продукта производить
на 5 неделе по линейной программе.
- Решите эту линейную программу графически.
Раствор
Обратите внимание, что первая часть вопроса — это прогнозирование вопрос так решается ниже.
Для продукта 1 применяется экспоненциальное сглаживание с константой сглаживания из 0,7 получаем:
М 1 = Y 1 = 23
M 2 = 0,7Y 2 + 0,3M 1 = 0,7(27) + 0,3(23)
= 25,80
M 3 = 0,7Y 3 + 0,3M 2 = 0,7(34) + 0,3(25,80)
= 31,54
M 4 = 0,7Y 4 + 0,3M 3 = 0,7(40) + 0,3(31,54)
= 37,46
Прогноз на пятую неделю — это среднее значение на 4-ю неделю = M 4 = 37,46 = 31 (поскольку у нас не может быть дробного спроса).
Для продукта 2 применяется экспоненциальное сглаживание с константой сглаживания из 0,7 получаем:
М 1 = Y 1 = 11
М 2 = 0,7Г 2 + 0,3М 1 = 0,7(13) + 0,3(11)
= 12,40
M 3 = 0,7Y 3 + 0,3M 2 = 0,7(15) + 0,3(12,40)
= 14,22
M 4 = 0,7Y 4 + 0,3M 3 = 0,7(14) + 0,3(14,22)
= 14.
07
Прогноз на пятую неделю — это среднее значение на 4-ю неделю = M 4 = 14,07 = 14 (поскольку у нас не может быть дробного спроса).
Теперь мы можем сформулировать LP для недели 5, используя две цифры спроса. (37 для продукта 1 и 14 для продукта 2), полученные выше.
Пусть
x 1 количество произведенных единиц товара 1
x 2 количество произведенных единиц продукта 2
где х 1 , х 2 >=0
Ограничения:
15x 1 + 7x 2 <= 20(60) станок X
25x 1 + 45x 2 <= 15(60) станок Y
x 1 <= 37 спрос на продукт 1
x 2 <= 14 спрос на продукт 2
Цель состоит в максимизации прибыли, т.е.
увеличить 10x 1 + 4x 2 — 3(37-x 1 ) — 1(14-x 2 )
т.е. максимизировать 13x 1 + 5x 2 — 125
График показан ниже, из графика мы имеем, что решение происходит по горизонтальной оси (x 2 =0) в x 1 =36 в какой точке максимальная прибыль 13(36) + 5(0) — 125 = £343
Пример линейного программирования 1994 UG экзамен
Компания занимается производством двух изделий (X и Y).
ресурсы, необходимые для производства X и Y, двояки, а именно машинное время для
автоматическая обработка и время мастера для ручной отделки. Таблица ниже
дает количество минут, необходимых для каждого элемента:
Машинное время Время мастера
Пункт Х 13 20
Д 19 29 У компании есть 40 часов машинного времени в наличии на следующем рабочем месте. неделю, но только 35 часов рабочего времени. Машинное время стоит 10 фунтов стерлингов за час работы, а время мастера стоит 2 фунта стерлингов за час работы. Время простоя машины и мастера не требует затрат. Полученный доход за каждый произведенный товар (все производство продано) составляет 20 фунтов стерлингов для X и 30 фунтов стерлингов за Y. У компании есть конкретный контракт на производство 10 изделий. X в неделю для конкретного клиента.
- Сформулируйте задачу о том, сколько производить в неделю, как линейная программа.
- Решите эту линейную программу графически.
Раствор
Пусть
- x количество элементов X
- y — количество элементов Y
тогда LP:
увеличить
- 20x + 30y — 10(время работы машины) — 2(время работы мастера)
предмет:
- 13x + 19y <= 40(60) машинного времени
- 20x + 29y <= 35(60) времени мастера
- х >= 10 контракт
- х, у >= 0
так, чтобы целевая функция стала
увеличить
- 20x + 30y — 10(13x + 19y)/60 — 2(20x + 29y)/60
т.
е. максимизировать
- 17,1667х + 25,8667у
предмет:
- 13x + 19y <= 2400
- 20x + 29y <= 2100
- х >= 10
- х, у >= 0
Из диаграммы ниже видно, что максимум приходится на пересечение из х=10 и 20х + 29у <= 2100
Решение одновременно, а не чтение значений с графика, имеем, что x=10 и y=65,52 со значением целевой функции £1866,5
Пример линейного программирования 1992 UG экзамен
Компания производит два продукта (А и В) и прибыль на единицу продано 3 и 5 фунтов стерлингов соответственно. Каждое изделие должно быть собрано на конкретной машине каждая единица продукта А собирается за 12 минут. времени и каждой единицы продукта B 25 минут времени сборки. Компания оценивает, что машина, используемая для сборки, имеет эффективную рабочую неделю всего 30 часов (из-за технического обслуживания/поломки).
Технологические ограничения означают, что на каждые пять единиц продукции
Произведено не менее двух единиц продукта В.
- Сформулируйте задачу о том, сколько каждого продукта производить, как линейную программа.
- Решите эту линейную программу графически.
- Компании была предложена возможность арендовать дополнительную машину, тем самым удвоение эффективного доступного времени сборки. Что такое максимум сумма, которую вы готовы платить (в неделю) за аренду этой машины и почему?
Раствор
Пусть
x A = количество произведенных единиц A
x B = количество произведенных единиц B
, тогда ограничения:
12x A + 25x B <= 30(60) (время сборки)
х В >= 2(х А /5)
т. е. x B — 0,4x A >= 0
т.е. 5x B >= 2x A (технологический)
где х А , х В >= 0
и цель
увеличить 3x A + 5x B
Из диаграммы ниже видно, что максимум приходится на пересечение из 12х A + 25x B = 1800 и x B — 0,4x A = 0
Решение одновременно, а не чтение значений с графика, у нас это:
х А = (1800/22) = 81,8
х В = 0,4 х А = 32,7
со значением целевой функции £408,9
Удвоение доступного времени сборки означает, что ограничение времени сборки (в настоящее время 12x A + 25x B <= 1800) становится 12x A + 25x B <= 2(1800) Это новое ограничение будет параллельно существующее ограничение по времени сборки, так что новое оптимальное решение будет лежать на пересечении 12x A + 25x B = 3600 и х В — 0,4х А = 0
т.
е. при х А = (3600/22) = 163,6
х В = 0,4 х А = 65,4
со значением целевой функции £817,8
Следовательно, мы получили дополнительную прибыль в размере £(817,8-408,9) = £408,9. и это максимальная сумма мы были бы готовы заплатить за аренда станка для удвоения времени сборки.
Это потому, что если мы заплатим больше этой суммы, мы уменьшим наша максимальная прибыль ниже 408,9 фунтов стерлингов, которые мы получили бы без новая машина.
Пример линейного программирования 1988 г. экзамен UG
Решить
свернуть
4а + 5б + 6с
с учетом
Решение
Чтобы решить эту LP, мы используем уравнение c-a-b=0, чтобы положить c=a+b (>= 0 как a >= 0 и b >= 0), поэтому LP уменьшается до
.свернуть
при условии
а + б >= 11
а — б <= 5
7а + 12б >= 35
а >= 0 б >= 0
На приведенной ниже диаграмме минимум приходится на пересечение — б = 5 и а + б = 11
т.
е. a = 8 и b = 3 с c (= a + b) = 11 и значением цели
функция 10а + 11б = 80 + 33 = 113.
Пример линейного программирования 1987 г. экзамен UG
Решите следующую линейную программу:
увеличить 5x 1 + 6x 2
при условии
x 1 + x 2 <= 10
x 1 — x 2 >= 3
5x 1 + 4x 2 <= 35
x 1 >= 0
x 2 >= 0
Решение
Из диаграммы ниже видно, что максимум приходится на пересечение из
5x 1 + 4x 2 = 35 и
х 1 — х 2 = 3
Решение одновременно, а не чтение значений с графика, у нас есть
5(3 + х 2 ) + 4 х 2 = 35
т.е. 15 + 9x 2 = 35
т.е. х 2 = (20/9) = 2,222 и
х 1 = 3 + х 2 = (47/9) = 5,222
Максимальное значение равно 5(47/9) + 6(20/9) = (355/9) = 39,444.