Задача линейного программирования пример: Математическое Бюро. Страница 404

Содержание

Пример решения задачи линейного программирования графическим методом

Ваулина В. А., УрГЭУ Пример решения задачи линейного программирования графическим методом Линейное программирование — это раздел математики, в котором рассматриваются методы решения экстремальных задач с линейным функционалом и линейными ограничениями. Существуют два наиболее распространенных способа решения задач линейного программирования: графический метод и симплекс-метод. Графический метод существенно нагляднее и обычно проще для понимания решения. Также этот метод позволяет практически одновременно найти решение на минимум и максимум. Основные шаги по решению ЗПЛ графическим методом следующие: построить область допустимых решений задачи (выпуклый многоугольник), который определяется как пересечение полуплоскостей, соответствующих неравенствам задачи, построить линию уровня целевой функции, и, наконец, двигать линию уровня в нужном направлении, пока не достигнем крайней точки области — оптимальной точки (или множества).

В отличие от графического метода, симплексный метод практически не имеет ограничений на задачу, может быть любое количество переменных и т.п. При решении задачи симплексным методом вычисления ведутся в таблицах. Решение задачи данным методом дает не только оптимальное решение, но и решение двойственной задачи, остатки ресурсов и т.п. Рассмотрим решение задачи линейного программирования графическим методом. Для производства столов и стульев мебельная фабрика использует три вида древесины. Норма затрат для каждого вида древесины на один стол составляет 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. На примере данной задачи мы рассмотрели решение задачи линейного программирования графическим методом. Этот метод наглядно показывает область дополнительных решений и нахождение оптимальной точки. Руководитель: Кныш А.А.

Решение задач линейного программирования с использованием Python / Хабр

Зачем решать экстремальные задачи

На практике очень часто возникают задачи, для решения которых используются методы оптимизации.

В обычной жизни при множественном выборе, например, подарков к новому году мы интуитивно решаем задачу минимальных затрат при заданном качестве покупок.

К сожалению, не всегда можно положиться на интуицию. Допустим Вы сотрудник коммерческой фирмы и отвечаете за рекламу. Затраты на рекламу в месяц не должны превышать 10 000 денежных единиц (д.е). Минута радиорекламы стоит 5 д.е., а телерекламы 90 д.е. Фирма намерена использовать радиорекламу в три раза чаще чем телерекламу. Практика показывает, что 1 минута телерекламы обеспечивает объём продаж в 30 раз больший чем 1 минута радиорекламы.

Перед Вами стоит задача определить такое распределение средств между двумя упомянутыми видами рекламы при котором объём продаж фирмы будет максимальным. Вы сначала выберите переменные, а именно месячный объём в минутах на телерекламу — x1, а на радиорекламу —x2. Теперь не трудно составить следующую систему:

30×1+x2 –увеличение продаж от рекламы;
90×1+5×2 <=10 000 – ограничение средств;
x2=3×1 – соотношение времён радио и теле рекламы.

Теперь на время забудем о рекламе и постараемся обобщить изложенное. Таких задач, как приваленная, может быть много, но они имеют следующие общие признаки. Обязательным есть наличие линейно зависящей от переменных функции цели, в нашем случае это

30×1+x2, которая при найденных значениях входящих переменных должна иметь единственное максимальное значение. При этом условие не отрицательности входящих переменных выполняется автоматически. Далее следуют опять-таки линейные равенства и неравенства в количестве, зависящем от наличия условий. Вот мы и сформулировали одну группу задач линейного программирования.

Другую большую группу задач линейного программирования, рассмотрим на примере так называемой транспортной задачи. Допустим Вы сотрудник коммерческой фирмы, которая оказывает транспортные услуги. Есть поставщики товара со складами в разных трёх городах, причём объёмы однородной продукции на этих складах соответственно равны a1, a2, a3. Есть и потребители в других трёх городах которым нужно привести товар от поставщиков в объёмах b1, b2, b3 соответственно.

Известны также стоимости доставки с1÷с9 товаров от поставщиков к потребителям, согласно таблице.

Если обозначить через x1…xn количество перевозимого груза, тогда функцией цели будет общая стоимость перевозки:

F(x)=c1*x1+c2*x2+c3*x3+c4*x4+c5*x5+c6*x6+c7*x7+c8*x8+c9*x9.

Условия, которые записываться. в виде неравенств:

x1+x2+x3<=20 – больше чем есть у поставщика не возьмёшь

x4+x5+x6<=45
x7+x8+x9<=30

Условия, которые записываться. в виде равенств:

x1+x4+x7=b1– сколько надо столько и привезём
x2+x5+x8=b2
x3+x6+x9=b3

Тут дополнительно нужны условия не отрицательности переменных x поскольку они по смыслу не отрицательны и ищется минимум F(x). Эти неравенства не приводим.

Теперь Вы знаете как строить функции цели и условия для основных задач линейного программирования. Но когда Вы прочитаете в специальной литературе про геометрический, симплекс, искусственного базиса методы решения указанных задач Вы бросили и рекламу и логистику.

Но ведь можно найти простое и понятное решение на Python.

Выбор библиотек Python для решения типовых задач линейного программирования

Для линейного программирования в Python мне известны три специализированные библиотеки. Рассмотрим решение обеих приведенных задач на каждой из библиотек. Кроме интерфейса и результатов оптимизации будем оценивать и быстродействие. Поскольку нам нужно только качественное отличие в быстродействии воспользуемся для этого самым простым листингом усредняя результаты каждого запуска программ.

Оптимизация с библиотекой pulp [1].

Листинг программы для решения задачи «О рекламе»

from pulp import *
import time
start = time.time()
x1 = pulp.LpVariable("x1", lowBound=0)
x2 = pulp.LpVariable("x2", lowBound=0)
problem = pulp.LpProblem('0',pulp.LpMaximize)
problem += 30*x1 +x2, "Функция цели"
problem += 90*x1+ 5*x2 <= 10000, "1"
problem +=x2 ==3*x1, "2"
problem.solve()
print ("Результат:")
for variable in problem.variables():
    print (variable.  name, "=", variable.varValue)
print ("Прибыль:")
print (value(problem.objective))
stop = time.time()
print ("Время :")
print(stop - start)

В лис тенге программы уже знакомые нам соотношения для максимальной прибыли от рекламы 30*x1+x2, условия ограничения затрат, помеченные для сравнения «1». Мы не забыли и об отношении времён использования радио и теле рекламы, помеченные в лис тенге как «2». Назначение других операторов очевидны, Подробности можно прочесть в [1].

Результаты решения задачи оптимизации с использованием pulp.

Результат:
x1 = 95.238095
x2 = 285.71429
Прибыль:
3142.85714
Время:
0.10001182556152344

В итоге мы получили значения времён рекламы, при которых ожидаемая прибыль от её использования будет максимальна.

Оптимизация с библиотекой cvxopt [2].

Листинг программы для решения задачи «О рекламе».

from cvxopt.modeling import variable, op
import time
start = time.  time()
x = variable(2, 'x')
z=-(30*x[0] +1*x[1])#Функция цели
mass1 = (90*x[0] + 5*x[1]  <= 10000) #"1"
mass2 = (3*x[0] -x[1] == 0) # "2"
x_non_negative = (x >= 0) #"3"    
problem =op(z,[mass1,mass2,x_non_negative])
problem.solve(solver='glpk')  
problem.status
print ("Прибыль:")
print(abs(problem.objective.value()[0]))
print ("Результат:")
print(x.value)
stop = time.time()
print ("Время :")
print(stop - start)

По структуре программа аналогична предыдущей, но имеются два существенных отличия. Во-первых, библиотека cvxopt настроена на поиск минимума функции цели, а не на максимум. Поэтому целевая функция взята с отрицательным знаком минус -(30*x[0] +1*x[1]). Полученное вследствие этого отрицательное её значение выведено по абсолютной величине. Во-вторых, введено ограничение на не отрицательность переменных- non_negative. Повлияло ли это на результат мы сейчас у видим.

Результаты решения задачи оптимизации с использованием cvxopt.

Прибыль:
3142. 857142857143
Результат:
[ 9.52e+01]
[ 2.86e+02]
Время:
0.041656494140625

Никаких существенных изменений в сравнении с библиотекой pulp не произошло за исключением время работы программы.

Оптимизация с библиотекой scipy. optimize [3].

Листинг программы для решения задачи «О рекламе».

from scipy.optimize import linprog
import time
start = time.time()
c = [-30,-1] #Функция цели
A_ub = [[90,5]]  #'1'   
b_ub = [10000]#'1'   
A_eq = [[3,-1]] #'2'   
b_eq = [0] #'2'   
print (linprog(c, A_ub, b_ub, A_eq, b_eq))
stop = time.time()
print ("Время :")
print(stop - start)

Достаточно беглого взгляда на листинг, чтобы понять, что мы имеем дело с принципиально иным подходом к вводу данных. Хотя приведенные в листингах цифры помогают прояснить принцип организации данных, путём сравнения, всё же приведу пояснения. Список c = [-30,-1] содержит коэффициенты функции цели с обратным знаком, поскольку linprog () ищет минимум.

Матрица A_ub содержит коэффициенты при переменных для условий в виде неравенств. Для нашей задачи это 90×1+5×2 3×1-x2=0, причём ноль в правой части, помещается в список b_eq.

Результаты решения задачи оптимизации с использованием scipy. optimize.

Fun: -3142.8571428571431
message: ‘Optimization terminated successfully.’
nit: 2
slack: array([ 0.])
status: 0
success: True
x: array ([ 95.23809524, 285.71428571])

Время:
0.03020191192626953

Здесь более подробно выведены результаты расчётов, но сами результаты те же что и в предыдущих библиотеках.

По результатам решения задачи «О рекламе» можно сделать промежуточный вывод, о том что использование библиотеки scipy. optimize обеспечивает большее быстродействие и рациональную форму исходных данных. Однако без результатов решения транспортной задачи окончательный вывод делать рано.

Привожу решение транспортной задачи, но уже без подробных пояснений, поскольку основные этапы решения уже подробно описаны.

Оптимизация с библиотекой pulp.

Листинг программы для решения транспортной задачи.

from pulp import *
import time
start = time.time()
x1 = pulp.LpVariable("x1", lowBound=0)
x2 = pulp.LpVariable("x2", lowBound=0)
x3 = pulp.LpVariable("x3", lowBound=0)
x4 = pulp.LpVariable("x4", lowBound=0)
x5 = pulp.LpVariable("x5", lowBound=0)
x6 = pulp.LpVariable("x6", lowBound=0)
x7 = pulp.LpVariable("x7", lowBound=0)
x8 = pulp.LpVariable("x8", lowBound=0)
x9 = pulp.LpVariable("x9", lowBound=0)
problem = pulp.LpProblem('0',pulp.LpMaximize)
problem += -7*x1 - 3*x2 - 6* x3 - 4*x4 - 8*x5 -2* x6-1*x7- 5*x8-9* x9, "Функция цели"
problem +=x1 + x2 +x3<= 74,"1" 
problem +=x4 + x5 +x6 <= 40, "2"
problem +=x7 + x8+ x9 <= 36, "3"
problem +=x1+ x4+ x7 == 20, "4"
problem +=x2+x5+ x8 == 45, "5"
problem +=x3 + x6+x9 == 30, "6"                     
problem.solve()
print ("Результат:")
for variable in problem.variables():
    print (variable.name, "=", variable.varValue)
print ("Стоимость доставки:")
print (abs(value(problem. objective)))
stop = time.time()
print ("Время :")
print(stop - start)

Решение транспортной задачи требует минимизации затрат по доставке, поэтому функция цели вводиться со знаком минус, а выводиться по абсолютной величине.

Результаты решения транспортной задачи с использованием pulp.

Результат:
x1 = 0.0
x2 = 45.0
x3 = 0.0
x4 = 0.0
x5 = 0.0
x6 = 30.0
x7 = 20.0
x8 = 0.0
x9 = 0.0
Стоимость доставки:
215.0
Время:
0.19006609916687012

Оптимизация с библиотекой cvxopt.

Листинг программы для решения транспортной задачи.

from cvxopt.modeling import variable, op
import time
start = time.time()
x = variable(9, 'x')
z=(7*x[0] + 3*x[1] +6* x[2] +4*x[3] + 8*x[4] +2* x[5]+x[6] + 5*x[7] +9* x[8])
mass1 = (x[0] + x[1] +x[2] <= 74)
mass2 = (x[3] + x[4] +x[5] <= 40)
mass3 = (x[6] + x[7] + x[8] <= 36)
mass4 = (x[0] + x[3] + x[6] == 20)
mass5 = (x[1] +x[4] + x[7] == 45)
mass6 = (x[2] + x[5] + x[8] == 30)
x_non_negative = (x >= 0)    
problem =op(z,[mass1,mass2,mass3,mass4 ,mass5,mass6, x_non_negative])
problem. solve(solver='glpk')  
problem.status
print("Результат:")
print(x.value)
print("Стоимость доставки:")
print(problem.objective.value()[0])
stop = time.time()
print ("Время :")
print(stop - start)

Результаты решения транспортной задачи с использованием cvxopt.

Результат:
[ 0.00e+00]
[ 4.50e+01]
[ 0.00e+00]
[ 0.00e+00]
[ 0.00e+00]
[ 3.00e+01]
[ 2.00e+01]
[ 0.00e+00]
[ 0.00e+00]
Стоимость доставки:
215.0
Время :
0.03001546859741211

Оптимизация с библиотекой scipy. optimize.

Листинг программы для решения транспортной задачи.

from scipy.optimize import linprog	
import time
start = time.time()
c = [7, 3, 6,4,8,2,1,5,9]
A_ub = [[1,1,1,0,0,0,0,0,0],
               [0,0,0,1,1,1,0,0,0],
               [0,0,0,0,0,0,1,1,1]] 
b_ub = [74,40,36] 
A_eq = [[1,0,0,1,0,0,1,0,0],
               [0,1,0,0,1,0,0,1,0],
               [0,0,1,0,0,1,0,0,1]] 
b_eq = [20,45,30] 
print(linprog(c, A_ub, b_ub, A_eq, b_eq))
stop = time. time()
print ("Время :")
print(stop - start)

Результаты решения транспортной задачи с использованием scipy optimize.

fun: 215.0
message: ‘Optimization terminated successfully.’
nit: 9
slack: array([ 29., 10., 16.])
status: 0
success: True
x: array([ 0., 45., 0., 0., 0., 30., 20., 0., 0.])
Время:
0.009982585906982422

Анализ решения двух типовых задач линейного программирования с помощью трёх библиотек аналогичного назначения не вызывает сомнения в выборе библиотеки scipy. optimize, как лидера по компактности ввода данных и быстродействию.

Что нового для использования библиотеки scipy. optimize при решении задач линейного программирования

Получение из исходной матрицы, списка для функции цели, а также заполнение матриц неравенств A_ub и равенств A_eq программно, позволит упростить работу по вводу данных и увеличить размерность исходной матрицы. Это позволить решать реальные задачи оптимизации.

Рассмотрим, как это можно сделать на простом демонстрационном примере, не претендующем на идеальность кода.Заголовок спойлера

import numpy as np
from scipy.optimize import linprog
b_ub = [74,40,36] 
b_eq = [20,45,30] 
A=np.array([[7, 3,6],[4,8,2],[1,5,9]])
m, n = A.shape
c=list(np.reshape(A,n*m))# Преобразование матрицы A в список c.
A_ub= np.zeros([m,m*n])
for i in np.arange(0,m,1):# Заполнение матрицы условий –неравенств.
         for j in np.arange(0,n*m,1):
                  if i*n<=j<=n+i*n-1:
                        A_ub  [i,j]=1
A_eq= np.zeros([m,m*n])
for i in np.arange(0,m,1):# Заполнение матрицы условий –равенств.
         k=0
         for j in np.arange(0,n*m,1):
                  if j==k*n+i:
                           A_eq [i,j]=1
                           k=k+1
print(linprog(c, A_ub, b_ub, A_eq, b_eq))

Теперь вводиться только сама матрица A и списки правых частей b_ub неравенств и b_ub – равенств.

Результат рaботы программы предсказуем.
fun: 215.0
message: ‘Optimization terminated successfully.’
nit: 9
slack: array([ 29., 10., 16.])
status: 0
success: True
x: array([ 0., 45., 0., 0., 0., 30., 20., 0., 0.])

Вывод частный

При решении задач линейного программирования целесообразно использовать библиотеку scipy.optimize по методике, приведенной в статье, а матрицы условий заполнять програмно. При этом Вам не понадобятся специальные знания о методах решения оптимизационных задач.

Вывод общий

В последнее время появились разные библиотеки Python решающие аналогичные задачи. Решение о применении той или иной библиотеки часто носит субъективный характер. Поэтому целесообразно проводить их сравнительный анализ для области решаемых Вами задач.

Ссылки

pythonhosted.org/PuLP
cvxopt.org/userguide/modeling.html
docs.scipy.org/doc/scipy/reference/tutorial/optimize.html

Поиск решения EXCEL (6.

1). Задача линейного программирования (ЛП) . Примеры и описание

Решим задачу линейного программирования с помощью надстройки Поиск решения.

В этой статье мы отойдем от формулировки практических задач и решим задачу линейного программирования в абстрактных терминах: вектор переменных х, матрица ограничений A х , вектор b , целевая функция cTx (вместо более привычных: объем производства, количество комплектующих разного вида, максимальный доход). Задача линейного программирования (ЛП) есть задача максимизации линейной функции при линейных ограничениях. Задачу ЛП можно записать несколькими стандартными способами. Мы сформулируем ее в форме max { cTx : Ax b , x >0}

Задача

Необходимо максимизировать целевую функцию cTx: max 50* x1 + 30* x2 + 25* x3 + 30* x4 при условии, что: 2* x1 + 2,5* x2 + 3* x3 + 1,8* x4 x1 + x2 + 2* x3 + 0,8* x4 x1 + 1,2* x2 + 1,5* x3 + 0,8* x4 x2 >= 50 x3 >= 30 x1; x2; x3; x4 >= 0

cTx — это векторное произведение векторов cT (транспонированный вектор с) и х.

Примечание : эта задача эквивалентна задаче определения оптимальной структуры производства с целью максимизации дохода (см. статью Поиск решения MS EXCEL (1.1). Оптимальная структура выпускаемой продукции ). Сформулируем эту задачу в общем виде: Предприятие планирует производить n видов продукции, используя m видов ресурсов. Для производства единицы j-го продукта требуется aij единиц i-го ресурса. Стоимость единицы j-го продукта равна cj. В наличии имеется bi единиц i-го ресурса. Нужно определить план производства с целью максимизировать прибыль. Обозначив хj — объем выпуска продукции j-го вида (j =1;…;n), мы можем записать задачу поиска оптимального производственного плана следующим образом:

Или в матричной форме:

Получается, что в исходной задаче:

вектор с (стоимость продукции) равен (50; 30; 25; 30)
вектор x (количество продукции) необходимо найти для заданных условий
n=4 (4 вида продукции)
m=3 (3 вида ресурсов)
вектор b (количество ресурсов) равен (800; 400; 380)
матрица A (количество единиц ресурсов для изготовления продукта) равна (2; 2,5; 3; 1,8 : 1,2; 1; 2; 0,8 : 1,5; 1,2; 1,5; 0,8)

Теперь создадим модель.

Создание модели

На рисунке ниже приведена модель, созданная для решения задачи (см. файл примера ).

Для решения задачи на листе MS EXCEL необходимо записать матрицу А , вектора b и cT (предварительно все неравенства переведены в форму меньше или равно путем умножения соответствующих уравнений на -1):

Примечание : для удобства настройки Поиска решения используются именованные диапазоны .

Совет : Вводная статья про Поиск решения в MS EXCEL 2010 находится здесь .

Значение целевой функции cTx получено путем матричного умножения векторов cT и x (используйте функцию МУМНОЖ() , которая вводится как формула массива ). Аналогично получена функция ограничений Ах , путем умножения матрицы А на х . Так как матрица Ах имеет размерность 5х1, то перед вводом формулы = МУМНОЖ(Матрица_А;Вектор_Х) необходимо выделить столбец из 5 ячеек, затем после записи формулы в Строке формул , нажмите CTRL + SHIFT + ENTER для ее ввода.

Настроить Поиск решения нужно следующим образом:

Линейное программирование | Статья в журнале «Молодой ученый»

В данной статье рассматривается задача линейного программирования и возможный способ её решения — симплекс метод. Приведены примеры, поясняющие, что такое линейное программирование и симплекс метод.

Ключевые слова: линейное программирование, математическая оптимизация, pivot-переменная, симплекс метод, slack variables

Линейное программирование — это мощный инструмент для описания и решения задач оптимизации. Возьмем простой пример и рассмотрим задачу минимизации стоимости продуктов, соответствующих ежедневным нормам рациона человека. Модель линейного программирования имела бы множество переменных решений, которые подразумевают под собой количество каждого покупаемого продукта. Цель данной задачи — минимизировать стоимость приобретения выбранных продуктов, имея ограничения в виде питательных веществ.

Используя алгебраическую нотацию, линейное программирование может быть описано следующим образом:

Objective: minimize c^Tx

Constraints: Ax = b (ограничения линейного вида) / l ≤ x ≤ u (ограничения на заданном интервале).

В результате описания в данной форме, вектор х представляет собой вектор переменных решений, с — линейная целевая функция, матричное уравнение Ах = b указывает линейные ограничения в х, векторы l и u — нижнюю и верхнюю границы в х.

Пример нахождения минимального и максимального значения:

Допустим вам необходимо купить шкафы для хранения документов. Известно, что 10 единиц стоит шкаф Х, который хранит 8 м² файлов и требует пространства 6 м². С другой стороны, известно, что 20 единиц стоит шкаф У, который хранит 12 м²и^{требует 8 м². Имеется 140 единиц денег, а также помещение размером 72 м².}

Подставляем значения в решение:

Количество хранимого:

Пространство:

Стоимость:

Рис. 1. Графическое представление задачи

Из графика видно, что решение соответствует точкам (8, 3).

Первый алгоритм для решения задач линейного программирования был создан американским математиком Джорджом Данцигом в 1947 году.

Симплекс-метод — алгоритм решения оптимизационной задачи линейного программирования путём перебора вершин выпуклого многогранника в многомерном пространстве.

Сущность метода: построение базисных решений, на которых монотонно убывает линейный функционал, до ситуации, когда выполняются необходимые условия локальной оптимальности.

История линейного программирования

В работе Л. В. Канторовича «Математические методы организации и планирования производства» (1939) были впервые изложены принципы новой отрасли математики, которая позднее получила название линейного программирования.

Исторически общая задача линейного программирования была впервые поставлена в 1947 году Джорджом Бернардом Данцигом, Маршаллом Вудом и их сотрудниками в департаменте военно-воздушных сил США. В то время эта группа занималась исследованием возможности использования математических и смежных с ними методов для военных задач и проблем планирования. В дальнейшем для развития этих идей в ВВС была организована исследовательская группа под названием «Project SCOOP». Первое успешное решение задачи линейного программирования на ЭВМ SEAC было проведено в январе 1952 года [2].

Эффективность

Симплекс метод удивительно эффективен на практике, но в 1972 Кли и Минти привели пример, в котором симплекс-метод перебирал все вершины симплекса, что показывает экспоненциальную сходимость метода в худшем случае. С тех пор для каждого варианта метода был найден пример, на котором метод вел себя исключительно плохо.

Наблюдения и анализ эффективности метода в практических приложениях привело к развитию других способов измерения эффективности.

Симплекс метод имеет среднюю полиномиальную сходимость при широком выборе распределения значений в случайных матрицах.

Вычислительная эффективность оценивается обычно при помощи двух параметров:

Числа итераций, необходимого для получения решения;
Затрат машинного времени.

В результате численных экспериментов получены результаты:

Число итераций при решении задач линейного программирования в стандартной форме с M ограничениями и N переменными заключено между M и 3M. Среднее число итераций 2M. Верхняя граница числа итераций равна 2M+N.
Требуемое машинное время пропорционально M³.

Число ограничений больше влияет на вычислительную эффективность, чем число переменных, поэтому при формулировке задач линейного программирования нужно стремиться к уменьшению числа ограничений пусть даже путём роста числа переменных.

Покажем суть метода на примере:

Владельцу предприятия, производящего трейлеры, необходимо определить лучший набор 3 продуктов: трейлер с прицепом, экономичный трейлер или трейлер высокого качества. Предприятие ограничено работой 24 днями на металлообработке и 60 днями на деревообработке для разработки трейлеров. Следующая таблица наглядно представит задачу:

	С прицепом	Экономичный	Высокого качества	Ограничения (дней)
Металлообработка	0.5	2	1	24
Деревообработка	1	2	4	60
Выручка за единицу	6	14	13

Обозначим трейлеры за х₁, х₂, х₃.

Необходимо:

Согласно ограничениям:

0.5x₁+2x₂+x₃ ≤24

x₁+2x₂+4x₃ ≤60

Неравенства «≥» и «≤» необходимо привести к равенствам с помощью добавления переменных, в английской литературе называемых slack variables.

0.5x₁+2x₂+x₃+x₄=24

x₁+2x₂+4x₃+x₅=60

Далее необходимо выбрать pivot переменную:

BASIS	X₁	X₂	X₃	X₄	X₅	Ограничения	Отношение	Pivot
X₄	0. 5	2	1	1	0	24	12	*
X₅	1	2	4	0	1	60	30
-z	-6	-14	-13	0	0	0
Pivot		*

Выбранный алгоритмом элемент выделен жирным. Далее необходимо “занулить” столбец с pivot переменной, а также привести её к 1. В столбце basis Х₄ заменяется на Х₂, так как pivot в столбце Х₂ и строке Х₄.

Результат:

BASIS	X₁	X₂	X₃	X₄	X₅	Ограничения	Отношение	Pivot
X₂	0.25	1	0.5	0.5	0	12	24
X₅	0. 5	0	3	-1	1	36	12	*
-z	-2.5	0	-6	7	0	168
Pivot			*

Операция повторяется:

BASIS	X₁	X₂	X₃	X₄	X₅	Ограничения	Отношение	Pivot
X₂	1/6	1	0	2/3	-1/6	6	36	*
X₃	1/6	0	1	-1/3	1/3	12	72
-z	-1. 5	0	0	5	2	240
Pivot	*

Операция повторяется:

BASIS	X₁	X₂	X₃	X₄	X₅	Ограничения	Отношение
X₁	1	6	0	4	-1	36	36
X₃	0	-1	1	-1	0. 5	6	6
-z	0	9	0	11	0.5	294

Таким образом, решение минимума z = -294. Максимум равен 294. Оптимальное решение х = (36, 0, 6, 0, 0).

В результате решения задач становится понятно, что симплекс метод является чрезвычайно полезным инструментом в области линейного программирования, несмотря на его простоту.

Литература:

Singiresu S. Rao Engineering optimization: theory and practice. — New York: Wiley, 2009. — 813 p.
Гасс С. Линейное программирование. — М.: Государственное издательство физико-математической литературы, 2015. — 304 c.

Основные термины (генерируются автоматически): линейное программирование, BASIS, симплекс метод, ограничение, число итераций, SCOOP, SEAC, высокое качество, вычислительная эффективность, решение задач.

Линейное программирование и смешано-целочисленное линейное программирование

Основанное на проблеме смешано-целочисленное линейное программирование

Смешано-целочисленные линейные основы программирования: основанный на проблеме

Простой пример смешано-целочисленного линейного программирования.

Фабрика, склад, модель выделения продаж: основанный на проблеме

В этом примере показано, как настроить и решить смешано-целочисленную задачу линейного программирования.

Проблема коммивояжера: основанный на проблеме

В этом примере показано, как использовать бинарное целочисленное программирование, чтобы решить классическую задачу коммивояжера.

Оптимальная отправка производителей электроэнергии: основанный на проблеме

В этом примере показано, как запланировать два газовых электрических генератора оптимально, означая получать большую часть дохода минус стоимость.

Присвоения Office бинарным целочисленным программированием: основанный на проблеме

В этом примере показано, как решить задачу присвоения бинарным целочисленным программированием с помощью подхода задачи оптимизации.

Смешано-целочисленная оптимизация портфеля квадратичного программирования: основанный на проблеме

В этом примере показано, как решить задачу оптимизации портфеля Смешано-целочисленного квадратичного программирования (MIQP) с помощью подхода, основанного на проблеме.

Сокращение проблемы запаса: основанный на проблеме

В этом примере показано, как решить сокращающую задачу запаса с помощью линейного программирования с целочисленной линейной стандартной подпрограммой программирования.

Минимизируйте Makespan в параллельной обработке

Минимизируйте максимальное время для набора процессоров, чтобы выполнить группу задач.

Решите судоку через целочисленное программирование: основанный на проблеме

В этом примере показано, как решить Судоку с помощью бинарного целочисленного программирования.

НОУ ИНТУИТ | Лекция линейного программирования

Аннотация: Предлагаются параллельные методы решения задач линейного и целочисленного линейного программирования. Методы предполагают применение SPMD-технологии в вычислительных сетях и в многопроцессорных вычислительных системах.

Предпосылки методов

Задачи линейной и нелинейной оптимизации, сетевые транспортные задачи — задачи высокой сложности, подверженные «проклятию размерности». Ориентация на применение многопроцессорных симметричных вычислительных систем в составе персональных компьютеров или рабочих станций (параллельные вычисления) и на применение сетевых технологий (распределенные вычисления) требует разработки новых параллельных методов их решения. Эти методы должны быть лишены недостатков «традиционных» методов: последовательного характера вычислений и введения дополнительных переменных (для задач линейного программирования). Анализ способов распараллеливания показывает эффективность распараллеливания «по информации». Весьма перспективной поэтому становится SPMD-технология программирования ( Single Program — Multiple Data ). При этой технологии вычислительный процесс строится на основе единственной программы, запускаемой на всех процессорах вычислительной системы или на многих станциях локальной сети. Копии программы могут выполняться по разным ветвям алгоритма, обрабатывая подмножества данных. Неизбежна синхронизация во времени и при обработке общих данных.

Такая технология параллельного программирования и обусловила разработку рассмотренных ниже методов. В то же время не отрицаются известные традиционные методы, сокращающие общее число операций и исключающие перебор. Иной методологический подход открывает дорогу решению задач большой размерности и эффективной параллельной работе многих процессоров. Для ряда задач этот подход еще нуждается в исследовании, уточнении области применения и развитии — проведении тщательной математической экспертизы. Поэтому мы посчитали необходимым осветить его подробно — для лучшего представления «физического смысла», ощутимости пространственной модели задач и следующих из этого планов их параллельного решения.

Метод прямого перебора при решении задачи линейного программирования

Графический метод решения и его обобщение

Рассмотрим пример

z=c₁x₁+c₂x₂=2x₁+5x₂-> max (4.1)

при ограничениях

q₁=x₁<= 40

q₂=x₂<= 30

q₃=x₁+x₂<= 50

и условиях x₁ >= 0, x₂ >= 0.

Каждое ограничение в двухмерном пространстве, n=2, определяет полуплоскость. Их пересечение образует многоугольник R (рис. 4.1). Его грани — прямые, получены на основе ограничений, в которых неравенства заменены равенствами.

q₁ = 40

q₂ = 30 (4.2)

q₃ = 50

Эти равенства образуют уравнения границ или просто границы R.

Рис. 4.1. Графический метод решения задачи линейного программирования

Этот многоугольник (выпуклый многогранник; выпуклый, — ибо он остается по одну сторону от любой прямой, проходящей через его ребро) представляет собой допустимое множество решений R задачи ЛП.

Выберем произвольное значение, например, z=100 целевой функции. Прямая 2x₁+5x₂=100 показана на рисунке. Она пересекает ось x₁ в точке x₁=50 и ось x₂ в точке x₂=20.

intuit.ru/2010/edi»>Отметим, что для .

Т.к. dx₁ и dx₂ принадлежат прямой z, то скалярное произведение двух векторов, которое здесь изображено, равно нулю в том случае, если вектор (c₁, c₂) =(2, 5) перпендикулярен прямой z.

Увеличиваем значение z, передвигая (с помощью линейки) прямую — целевую — функцию параллельно самой себе в сторону ее возрастания вдоль вектора (2, 5) до тех пор, пока линейка не коснется последней возможной точки многогранника. R. Это значение z и будет максимальным. В данном случае — это точка A = (x₁=20, x₂=30).

Сделаем важное замечание относительно многогранника R.

То, что он выпуклый, мы заметили ранее.
Нам были заданы три ограничения, отсекающие полуплоскости, но определившие не все границы многогранника R. С «не закрытой» ими стороны область R оказалась закрытой условиями неотрицательного решения задачи: x₁ >= 0, x₂ >= 0. Значит, эти выражения пришлось из ранга условий перевести в ранг ограничений.
При этом не все условия могут быть переведены в ограничения. В нашей задаче могло существовать некоторое ограничение q₄ (на рисунке пунктиром), которое бы определяло границу R слева, исключая границу x₁ = 0. При этом граница x₂ = 0 внизу осталась бы.
Другое важное замечание: решение задачи мы нашли на границе многогранника R.

При этом возможны варианты:

Единственному конечному решению соответствует вершина R, как в нашем примере.
Решением может являться бесконечное множество точек на грани R, например, если бы ограничение q₃ определяло бы прямую, параллельную z (уравнения q₃ и z были бы линейно зависимыми).
Система ограничений может определять «открытый» многогранник R, включающий бесконечно удаленные точки, в которых достигается max z, т.е. . Например, та же задача ЛП могла быть поставлена при отсутствии ограничений q₂ и q₃ ( рис. 4.2). Перемещение z в сторону ее увеличения может быть бесконечным, т.е. . Но если бы была поставлена задача z -> min, то она бы при этих ограничениях имела конечное и единственное решение, в данном случае x₁=x₂=0.

Рис. 4.2. Случай отсутствия решения

Значит, имеет значение, с какой стороны многогранник R открыт: либо он позволяет поиск решения вдоль «закрытых» стенок, либо допускает возможность «выпасть» за его пределы, искать решение в бесконечности.

Тогда, как бы мы могли искать решение нашей первоначально поставленной задачи ЛП?

intuit.ru/2010/edi»>Учитывая, что решение задачи — в одной из вершин R, мы сначала выпишем уравнения всех прямых, ограничивающих R, т.е. уравнения всех его границ:

x₁ = 40

x₂ = 30

x₁ + x₂ = 50

x₁ = 0

x₂ = 0

Для нахождения координат каждой вершины R решаем совместно пару уравнений прямых, образующих эту вершину, и находим значение z в найденной вершине:

Действительно, max z = 190 достигается в точке A.

Отметим возможноcть распараллеливания решения задачи на многопроцессорной ВС, точнее, ВС SPMD-технологии.

intuit.ru/2010/edi»>В трехмерном пространстве ограничения и условия образуют пространственный многогранник R, охваченный плоскостями-границами, записанными на основе ограничений и условий, где неравенства заменены равенствами, а каждая плоскость z = const, среди которых мы ищем решение, пересекает, «прорезает» его, деля на две части ( рис. 4.3).

Рис. 4.3. Задача линейного программирования в трёхмерной области

На рисунке иллюстрируется задача ЛП:

z=c₁x₁+c₂x₂+c₃x₃-> max

при ограничениях

q₁=a₁₁x₁+a₁₂x₂+a₁₃x₃<= b₁

q₂=a₂₁x₁+a₂₂x₂+a₂₃x₃<= b₂

intuit.ru/2010/edi»>и при условии

x₁>= 0, x₂>= 0, x₃>= 0.

Две грани q₁=b₁ и q₂=b₂, ограничивают многогранник R — область возможных значений переменных сверху (спереди) и справа. Слева, внизу и сзади пространственный многогранник R ограничен условиями неотрицательности решения, ставшими ограничениями x₁ = 0, x₂ = 0, x₃ = 0. Плоскость z=const пересекает многогранник R. Перемещая плоскость z параллельно себе, т.е. вдоль вектора (c₁, c₂, c₃), в сторону возрастания значений линейной формы z, мы находим решение. Здесь наглядно показана очевидность того, что решение следует искать в вершинах R.

Однако графическое представление уже в трехмерном пространстве затруднительно, в n -мерном пространстве нам необходимо действовать формально. Здесь существует ряд проблем.

Во-первых, мы не представляем пространственной картины и не знаем, охватывают ли заданные ограничения область R со всех сторон и какими условиями эти ограничения должны быть дополнены без противоречий.

Во-вторых, мы не знаем, какие n ограничений, дополненных условиями, соответствуют каждой конкретной вершине многогранника R, чтобы найти координаты этой вершины и найти в ней значение целевой функции z. Значит, мы должны испытать все возможные комбинации по n (в данном случае — тройки) ограничений и условий, т.е. все возможные комбинации по три, составленные на основе всех потенциальных границ- ограничений и условий.

Тогда при построении (параллельной!) вычислительной процедуры мы должны опираться на то, что любая противоречивость в системе ограничений (в их состав мы включили теперь и условия) выразится в неразрешимости системы трех уравнений, составленной для нахождения координат очередной испытываемой вершины R. Т.е. в этом случае вершина находится в бесконечности или содержит отрицательные значения координат. Эта неразрешимость находится в процессе счета.

Оставаясь в области практических решений задач ЛП, т.е. в области инженерии и экономики, примем предположение, что задача сформулирована корректно. Под этим будем предполагать, что ограничения выбраны так, что она не имеет неограниченного решения .

Например, ставя задачу о максимизации прибыли от перевозки, не надо забывать о том, что объем перевозок ограничен ресурсами страны, сообщества и т.д. В противном случае мы получим тривиальное решение: чем больше, тем лучше.

Значит, мы будем предполагать, что в многограннике R обязательно есть вершины (их координаты не отрицательны), в целом ограничивающие области изменения переменных, и хотя бы в одной из этих вершин целевая функция — линейная форма z принимает максимальное значение.

В свете сказанного будем также считать, что ограничения не противоречивы. Противоречивые ограничения приводят к случаю .

Например, ограничения

x + y >= 5

x + y <= 2

противоречивы.

Тогда, развивая на n -мерное пространство, мы можем реализовать следующую стратегию поиска решения задачи ЛП.

Примеры решений для линейного программирования

OR-Notes — это серия вводных заметок по темам, относящимся к широкий заголовок области исследования операций (OR). Они изначально были использованный мной во вводном курсе операционной, который я читаю в Имперском колледже. Они теперь доступны для использования всеми учащимися и преподавателями, интересующимися OR при соблюдении следующих условий.

Полный список тем, доступных в OR-Notes, можно найти здесь.

Примеры решений для линейного программирования

Пример линейного программирования 1997 UG экзамен

Компания производит два продукта (X и Y) на двух машинах (A и B). Каждая произведенная единица X требует времени обработки 50 минут. машина A и время обработки 30 минут на машине B. Каждая единица Y, требуется 24 минуты на обработку на машине A и 33 минуты время обработки на станке Б.

На начало текущей недели 30 единиц X и 90 единиц. Y в наличии.Доступное время обработки на машине A, по прогнозам, будет 40 часов, а на машине B — 35 часов.

Спрос на X на текущей неделе прогнозируется на уровне 75 единиц и для Y прогнозируется 95 единиц. Политика компании заключается в максимальном увеличении совокупного сумма единиц X и единиц Y на складе на конец недели.

Сформулируйте задачу о том, сколько каждого продукта производить. на текущей неделе как линейная программа.
Решите эту линейную программу графически.

Решение

Пусть

x количество единиц X, произведенных на текущей неделе
y — количество единиц Y, произведенных на текущей неделе.

, то ограничения следующие:

50x + 24y <= 40 (60) автомат А время

30x + 33y <= 35 (60) время станка B

x> = 75–30

я.е. x> = 45, поэтому производство X> = спроса (75) — начальный запас (30), что обеспечивает удовлетворение спроса

г> = 95 — 90

т.е. y> = 5, поэтому производство Y> = спроса (95) — начальный запас (90), что обеспечивает удовлетворение спроса

Цель: максимизировать (x + 30-75) + (y + 90-95) = (x + y-50)
т. е. для максимального увеличения количества единиц, остающихся на складе в конце недели

Как видно из приведенной ниже диаграммы, максимум приходится на пересечение из x = 45 и 50x + 24y = 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 получаем:

M ₁ = Y ₁ = 23
M ₂ = 0,7 Y ₂ + 0,3 M ₁ = 0,7 (27) + 0,3 (23) = 25.80
M ₃ = 0,7 Y ₃ + 0,3 M ₂ = 0,7 (34) + 0,3 (25,80) = 31,54
M ₄ = 0,7 Y ₄ + 0,3 M ₃ = 0,7 (40) + 0,3 (31,54) = 37,46

Прогноз на пятую неделю — это просто среднее значение для недели 4 = M ₄ = 37,46 = 31 (поскольку у нас не может быть частичного спроса).

Для продукта 2, применяющего экспоненциальное сглаживание с константой сглаживания из 0,7 получаем:

M ₁ = Y ₁ = 11
М ₂ = 0.7Y ₂ + 0,3M ₁ = 0,7 (13) + 0,3 (11) = 12,40
M ₃ = 0,7 Y ₃ + 0,3 M ₂ = 0,7 (15) + 0,3 (12,40) = 14,22
M ₄ = 0,7 Y ₄ + 0,3 M ₃ = 0,7 (14) + 0,3 (14,22) = 14,07

Прогноз на пятую неделю — это просто среднее значение для недели 4 = M ₄ = 14,07 = 14 (поскольку у нас не может быть частичного спроса).

Теперь мы можем сформулировать LP на 5-ю неделю, используя две цифры спроса. (37 для продукта 1 и 14 для продукта 2), полученные выше.

Пусть

x ₁ — количество произведенных единиц продукта 1

x ₂ — количество произведенных единиц продукта 2

где x ₁, x ₂> = 0

Ограничения:

15x ₁ + 7x ₂ <= 20 (60) станка X

25x ₁ + 45x ₂ <= 15 (60) станка Y

x ₁ <= 37 спрос на товар 1

x ₂ <= 14 спрос на товар 2

Цель состоит в том, чтобы максимизировать прибыль, т.е.е.

увеличить 10x ₁ + 4x ₂ — 3 (37- x ₁) — 1 (14-x ₂)

т. Е. Увеличить 13x ₁ + 5x ₂ — 125

График показан ниже, исходя из имеющегося у нас графика, решение происходит на горизонтальной оси (x ₂ = 0) в x ₁ = 36, в этой точке максимальная прибыль 13 (36) + 5 (0) — 125 = 343 £

Пример линейного программирования 1994 UG экзамен

Компания занимается производством двух изделий (X и Y).В ресурсы, необходимые для производства X и Y, двоякие, а именно машинное время для автоматическая обработка и время мастера для ручной отделки. Таблица ниже дает количество минут, необходимых для каждого элемента:

 Машинное время Мастерское время
Пункт X 13 20
     Y 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) время мастера
x> = 10 договор
х, у> = 0

, чтобы целевая функция стала

увеличить

20x + 30y — 10 (13x + 19y) / 60 — 2 (20x + 29y) / 60

и.е. увеличить

при условии:

13x + 19y <= 2400
20x + 29y <= 2100
х> = 10
х, у> = 0

Как видно из приведенной ниже диаграммы, максимум приходится на пересечение из x = 10 и 20x + 29y <= 2100

Решение одновременно, а не считывание значений с графика, имеем, что x = 10 и y = 65,52 со значением целевой функции составляет 1866 фунтов стерлингов.5

Пример линейного программирования 1992 UG экзамен

Компания производит два продукта (A и B) и прибыль на единицу продано по 3 и 5 фунтов стерлингов соответственно. Каждый продукт должен быть собран на конкретной машине, каждая единица продукта A занимает 12 минут сборки время и каждая единица продукта B 25 минут времени сборки. Компания оценивает, что машина, используемая для сборки, имеет эффективную рабочую неделю всего 30 часов (из-за технического обслуживания / поломки).

Технологические ограничения означают, что на каждые пять единиц продукции A произведено не менее двух единиц продукта B.

Сформулируйте задачу о том, сколько каждого продукта производить в виде линейной программа.
Решите эту линейную программу графически.
Компании была предложена возможность нанять дополнительную машину, тем самым удвоение доступного эффективного времени сборки. Что такое максимум сумма, которую вы готовы платить (в неделю) за аренду этой машины и почему?

Решение

Пусть

x _A = количество произведенных единиц A

x _B = количество произведенных единиц B

, то ограничения следующие:

12x _A + 25x _B <= 30 (60) (время сборки)

x _B> = 2 (x _A/5)

и.е. x _B — 0,4 x _A> = 0

т.е. 5x _B> = 2x _A (технологический)

где x _A, x _B> = 0

, а цель —

увеличить 3x _A + 5x _B

Как видно из приведенной ниже диаграммы, максимум приходится на пересечение из 12x _A + 25x _B = 1800 и x _B — 0.4x _А = 0

Решение одновременно, а не считывание значений с графика, у нас это:

x _A = (1800/22) = 81,8

x _B = 0,4 x _A = 32,7

со значением целевой функции 408,9 £

Удвоение доступного времени сборки означает, что ограничение времени сборки (в настоящее время 12x _A + 25x _B <= 1800) становится 12x _A + 25x _B <= 2 (1800) Это новое ограничение будет параллельно существующее ограничение по времени сборки, так что новое оптимальное решение будет лежать на пересечении 12x _A + 25x _B = 3600 и x _B — 0.4x _A = 0

т.е. при x _A = (3600/22) = 163,6

x _B = 0,4 x _A = 65,4

со значением целевой функции 817,8 £

Таким образом, мы получили дополнительную прибыль в размере (817,8-408,9 фунтов стерлингов) = 408,9 фунтов стерлингов. и это максимум сумм, которые мы готовы заплатить за аренда станка для увеличения времени сборки вдвое.

Это потому, что если мы заплатим больше этой суммы, мы уменьшим наша максимальная прибыль ниже 408 фунтов стерлингов.9 мы бы сделали без новая машина.

Пример линейного программирования 1988 UG экзамен

Решить

минимизировать

при условии

a + b> = 11

а — б <= 5

в — а — б = 0

7a> = 35 — 12b

а> = 0 б> = 0 в> = 0

Решение

Чтобы решить эту LP, мы используем уравнение c-a-b = 0, чтобы положить c = a + b (> = 0 как a> = 0 и b> = 0), поэтому LP уменьшается до

минимизировать

при условии

a + b> = 11

а — б <= 5

7a + 12b> = 35

а> = 0 б> = 0

На диаграмме ниже минимум происходит на пересечении — b = 5 и a + b = 11

и.е. a = 8 и b = 3 с c (= a + b) = 11 и значением цели функция 10a + 11b = 80 + 33 = 113.

Пример линейного программирования 1987 UG экзамен

Решите следующую линейную программу:

увеличить 5x ₁ + 6x ₂

при условии

x ₁ + x ₂ <= 10

x ₁ — x ₂> = 3

5x ₁ + 4x ₂ <= 35

x ₁> = 0

x ₂> = 0

Решение

Как видно из приведенной ниже диаграммы, максимум приходится на пересечение из

5x ₁ + 4x ₂ = 35 и

x ₁ — x ₂ = 3

Решение одновременно, а не считывание значений с графика, у нас это

5 (3 + x ₂) + 4x ₂ = 35

и.е. 15 + 9x ₂ = 35

т.е. x ₂ = (20/9) = 2,222 и

x ₁ = 3 + x ₂ = (47/9) = 5,222

Максимальное значение: 5 (47/9) + 6 (20/9) = (355/9) = 39,444

Пример линейного программирования 1986 UG экзамен

Плотник делает столы и стулья. Каждый стол можно продать с прибылью 30 фунтов стерлингов и каждый стул с прибылью 10 фунтов стерлингов. Плотник может позволить себе тратить до 40 часов в неделю на работу и требуется шесть часов, чтобы сделать стол и три часа сделать стул.Потребительский спрос требует что он делает как минимум в три раза больше стульев, чем столов. Таблицы принимают в четыре раза больше места для хранения, чем стулья, и есть место для чаще всего четыре стола в неделю.

Сформулируйте эту задачу как задачу линейного программирования и решите ее. графически.

Решение

Переменные

Пусть

x _T = количество столов, изготавливаемых в неделю

x _C = количество стульев, изготовленных в неделю

Ограничения

6x _T + 3x _C <= 40

x _C> = 3 x _T

(x _C/4) + x _T <= 4

Цель

увеличить 30x _T + 10x _C

Графическое изображение проблемы дано ниже и из что у нас есть решение лежит на пересечении

(x _C/4) + x _T = 4 и 6x _T + 3x _C = 40

Решая эти два уравнения одновременно, получаем x _C = 10.667, x _T = 1,333 и соответствующая прибыль = 146,667 фунтов стерлингов

3.2a. Графическое решение задач линейного программирования

Разве не было бы хорошо, если бы мы могли просто производить и продавать бесконечно много единиц продукта и, таким образом, зарабатывать бесконечные деньги? В бизнесе (и в повседневной жизни) мы знаем, что не можем просто сделать что-то, потому что имело бы смысл (необоснованно) достичь нашей цели.Вместо этого мы надеемся максимизировать или минимизировать какое-то количество с учетом набора ограничений.

Подумайте об этом: вы путешествуете из Чендлера, штат Аризона, в Сан-Диего, штат Калифорния. Вы надеетесь добраться туда как можно быстрее, а значит, стремитесь минимизировать время в пути. В то же время вы столкнетесь с большей или меньшей загруженностью на определенных отрезках пути, вам нужно будет остановиться на бензин хотя бы один раз (если вы не управляете гибридным автомобилем), а если у вас есть дети, вы определенно нужно остановиться на перерыв в туалете.Хотя мы упомянули лишь некоторые из них, это все
ограничения — вещи, которые ограничивают вас в вашей цели добраться до пункта назначения за как можно меньшее время.

Графическое решение задач линейного программирования

Задача линейного программирования включает ограничения, содержащие неравенства. Неравенство
обозначается знакомыми символами <,>, [латекс] \ le [/ latex] и [latex] \ ge [/ latex]. Из-за трудностей со строгими неравенствами (<и>) мы сосредоточимся только на [latex] \ le [/ latex] и [latex] \ ge [/ latex].

Чтобы иметь задачу линейного программирования, мы должны иметь:

Ограничения неравенства
Целевая функция , то есть функция, значение которой мы либо хотим быть как можно большим (хотим максимизировать), либо как можно меньше (хотим минимизировать).

Пример 1

Авиакомпания предлагает билеты на автобусы и билеты первого класса. Чтобы авиакомпания была прибыльной, она должна продать не менее 25 билетов первого класса и не менее 40 билетов на автобусы.Компания получает прибыль в размере 225 долларов с каждого билета на автобус и 200 долларов с каждого билета в первый класс. Максимум самолет вмещает 150 пассажиров. Сколько билетов нужно продать, чтобы получить максимальную прибыль?

Решение

Первый шаг — определить неизвестные количества. Нас просят найти номер каждого билета, который следует продать. Поскольку есть автобусные билеты и билеты первого класса, мы идентифицируем их как неизвестные. Пусть,

x = количество автобусных билетов

y = количество билетов первого класса

Далее нам нужно определить целевую функцию.Вопрос часто помогает нам определить целевую функцию. Поскольку целью является получение максимальной прибыли, наша цель определена.

Прибыль на автобусные билеты — 225 долларов. Если будет продано
x автобусных билетов, общая прибыль по этим билетам составит 225x.

Прибыль на билеты первого класса — 200 долларов. Аналогично, если продано
лет билетов первого класса, общая прибыль по этим билетам составит 200 лет.

Общая прибыль, P , составляет

P = 225 x + 200 y

Мы хотим сделать значение
как можно большим при соблюдении ограничений.В этом случае у нас есть следующие ограничения:

Продать не менее 25 билетов первого класса
Продать не менее 40 билетов на автобус
Продать можно не более 150 билетов (в самолет может поместиться не более 150 человек)

Нам нужно их количественно оценить.

Минимум 25 билетов первого класса означает, что нужно продать 25 и более. То есть y [латекс] \ ge [/ latex] 25
Не менее 40 билетов на автобус означает, что нужно продать 40 или более билетов.То есть x [латекс] \ ge [/ latex] 40
Сумма билетов первого класса и автобусов должна быть не более 150. То есть x + y [латекс] \ le [/ latex] 150

Таким образом, целевая функция вместе с тремя математическими ограничениями составляет:

Цель Функция: P = 225 x + 200 y

Ограничения: y [латекс] \ ge [/ latex] 25; x [латекс] \ ge [/ латекс] 40; x + y [латекс] \ le [/ латекс] 150

Мы будем работать над графическим представлением этих ограничений, а затем вернемся к целевой функции.Таким образом, мы будем иметь дело со следующим графиком:

Обратите внимание, что нас интересует только первый квадрант, поскольку у нас не может быть отрицательных билетов.

Сначала мы построим каждое из неравенств в виде уравнений, а затем позаботимся о знаках неравенства. То есть первый участок,

x = 25

y = 40

x + y = 150

Первые два уравнения представляют собой горизонтальные и вертикальные линии соответственно.Чтобы построить график x + y = 150, предпочтительно найти горизонтальные и вертикальные точки пересечения.

Чтобы найти точку пересечения по вертикали, положим
x = 0:
y = 150

Ставим нам точку (0,150)

Чтобы найти точку пересечения по горизонтали, положим
y = 0:
x = 150

Ставить нам точку (150,0)

Построение всех трех уравнений дает:

Наша следующая задача — учесть неравенства.

Сперва мы спрашиваем, когда y [latex] \ ge [/ latex] 25? Поскольку это горизонтальная линия, проходящая от до , значение y , равное 25, все, что находится выше этой линии, представляет собой значение больше 25. Мы обозначаем это штриховкой над линией:

Это говорит нам о том, что любая точка в области, заштрихованной зеленым цветом, удовлетворяет ограничению
y [latex] \ ge [/ latex] 25.

Далее имеем дело с
x [латекс] \ ge [/ латекс] 40.Мы спрашиваем, когда значение x больше 40? Значения слева меньше 40, поэтому мы должны закрасить вправо, чтобы получить значения больше 40:

Синяя область удовлетворяет второму ограничению, но поскольку мы должны удовлетворить
всем ограничениям , достаточно будет только зеленой и синей области.

У нас есть еще одно ограничение, которое следует учитывать:
x + y [latex] \ ge [/ latex] 150. У нас есть два варианта: оттенок ниже или оттенок сверху.Чтобы помочь нам лучше понять, что на самом деле нам нужно заштриховать ниже линии , давайте рассмотрим упорядоченную пару в обоих регионах. Выбор упорядоченной пары над линией, например (64, 130), дает:

64 + 130 [латекс] \ ge [/ латекс] 150

Это ложное утверждение, поскольку 64 + 130 = 194, значение больше 150.

Согласно графику, точка (64, 65) находится ниже графика. Ввод этой пары дает выписку:

64 + 65 [латекс] \ ge [/ латекс] 150

Это истинное утверждение, поскольку 64 + 65 равно 129, то есть меньше 150.

Поэтому ниже линии штрихуем:

Область, в которой пересекаются зеленый, синий и фиолетовый оттенки, удовлетворяет всем трем ограничениям. Эта область известна как возможных областей , поскольку этот набор точек возможен с учетом всех ограничений. Мы можем проверить, что точка, выбранная в этой области, удовлетворяет всем трем ограничениям. Например, выбор (64, 65) дает:

64 [латекс] \ ge [/ латекс] 40 ИСТИНА

65 [латекс] \ ge [/ латекс] 25 ИСТИНА

64 + 65 [латекс] \ ge [/ латекс] 150 ИСТИНА

Это подводит нас к важному моменту, но все еще не дает ответа на вопрос:
какая точка максимизирует прибыль? К счастью, математики открыли теорему, которая позволяет нам ответить на этот вопрос.

Прежде всего, мы определяем новый термин: угловая точка — это точка, которая попадает в угол допустимой области. В нашей ситуации у нас есть три угловые точки, показанные на графике сплошными черными точками:

Целевая функция вместе с тремя угловыми точками выше образует ограниченную задачу линейного программирования . То есть представьте, что вы смотрите на три столба забора, соединенные ограждением (черная точка и линии соответственно). Если бы вы поместили свою собаку посередине, вы могли быть уверены, что она не убежит (при условии, что забор достаточно высокий).Если это так, то перед вами проблема ограниченного линейного программирования. Если бы собака могла бесконечно ходить в любом одном направлении, тогда проблема была бы безграничной.

Основная теорема линейного программирования

Если решение задачи ограниченного линейного программирования существует, то оно возникает в одной из угловых точек.
Если допустимая область неограничена, то максимальное значение целевой функции не существует.
Если допустимая область неограничена, а целевая функция имеет только положительные коэффициенты, то существует минимальное значение

Это означает, что мы должны выбрать одну из трех угловых точек.Чтобы проверить «победителя», мы должны увидеть, какая из этих трех точек максимизирует целевую функцию. Чтобы найти угловые точки в виде упорядоченных пар, мы должны решить три системы, состоящие из двух уравнений в каждой:

Система 1

х = 40

x + y = 150

Система 2

х = 40

и = 25

Система 3

и = 25

x + y = 150

Мы можем решить, используя матричные уравнения, но все эти уравнения достаточно просты, чтобы их можно было решить вручную:

Система 1

(40) + y = 150

y = 110

Пункт: (40,110)

Система 2

Балл уже начислен

Балл: (40,25)

Система 3

х + 25 = 150

x = 125

Балл: (125,25)

Мы тестируем каждую из этих трех точек в целевой функции:

Точка	Прибыль
(40,110)	225 (40) + 200 (110) = 31 000 долларов США
(40,25)	225 (40) + 200 (25) = 14 000 долларов США
(125,25)	225 (125) + 200 (25) = 33 125 долларов США

Третья точка (125,25) максимизирует прибыль.Таким образом, мы приходим к выводу, что авиакомпания должна продать 125 автобусных билетов и 25 билетов первого класса, чтобы максимизировать прибыль.

Приведенный выше пример был довольно длинным и требовал выполнения многих шагов. Резюмируем процедуру ниже:

Графическое решение задачи линейного программирования

Определите переменные для оптимизации. Заданный вопрос является хорошим индикатором того, что это будет.
Запишите целевую функцию словами, а затем преобразуйте ее в математическое уравнение
Запишите ограничения словами, затем преобразуйте их в математические неравенства
Изобразите зависимости в виде уравнений
Заштриховать возможные области с учетом знака неравенства и его направления.Если,

а) Вертикальная линия

[латекс] \ le [/ latex], затем растушевываем налево

[латекс] \ ge [/ latex], затем заштрихуйте вправо

б) Горизонтальная линия

[латекс] \ le [/ latex], затем оттенок ниже

[латекс] \ ge [/ latex], затем оттенок выше

c) Линия с ненулевым заданным наклоном

[латекс] \ le [/ латекс], оттенок ниже

[латекс] \ ge [/ латекс], оттенок выше

6. Определите угловые точки, решив системы линейных уравнений, пересечение которых представляет собой угловую точку.

7. Проверьте все угловые точки целевой функции. «Выигрышная» точка — это точка, которая оптимизирует целевую функцию (наибольшая, если максимизация, наименьшая, если минимизация)

Есть один случай, в котором мы должны проявлять большую осторожность. Сначала рассмотрим (истинное) неравенство,

5> 3

Предположим, мы должны разделить обе части на –1. Было бы верно сказать следующее?

[латекс] \ displaystyle \ frac {{5}} {{- {1}}} \ gt \ frac {{3}} {{- {1}}} [/ латекс]

[латекс] \ displaystyle- {5} \ gt- {3} [/ latex]

Понятно, что –5 не больше –3! Чтобы утверждение оставалось верным, мы должны изменить направление знака неравенства так, чтобы,

–5 <–3

По числовой прямой ниже видно, что два набора чисел симметричны относительно 0, за исключением того, что мы описываем размер противоположным образом.Это оправдывает то, что мы также должны использовать противоположный знак, когда мы отражаем значения с другой стороны от 0.

Изменение знака неравенства

При умножении / делении любого неравенства на –1 направление неравенства должно измениться.

Пример 2

Компания по производству здорового питания хотела бы создать смесь сухофруктов с высоким содержанием калия в виде коробки из 10 фруктовых батончиков. Он решает использовать сушеные абрикосы, которые содержат 407 мг калия на порцию, и сушеные финики, которые содержат 271 мг калия на порцию (ИСТОЧНИК: www.thepotassiumrichfoods.com).

Компания может покупать фрукты оптом на сайте
www.driedfruitbaskets.com по разумной цене. Сушеные абрикосы стоят 9,99 долларов за фунт. (около 3 порций) и сушеные финики стоят 7,99 доллара за фунт. (около 4 порций). Компания хотела бы, чтобы в упаковке батончиков было по крайней мере рекомендованное суточное потребление калия около 4700 мг, но хотелось бы, чтобы оно не превышало рекомендуемого суточного потребления вдвое. Сколько порций каждого сухофрукта должно поместиться в коробку батончиков, чтобы минимизировать затраты?

Решение

Начнем с определения переменных.Пусть,
x = количество порций кураги

y = количество порций сушеных фиников

Теперь мы работаем над целевой функцией.

Для абрикосов один фунт составляет 3 порции. Это означает, что стоимость одной порции составляет 9,99 доллара США / 3 = 3,33 доллара США. Стоимость
порций x составит 3,33 x порции.

Для фиников есть 4 порции на фунт. Это означает, что стоимость одной порции составляет 7,99 доллара США / 4
2 доллара США. Таким образом, стоимость порции и составит 2.00 и .

Общая стоимость абрикосов и фиников составит

.
C = 3,33 x + 2,00 y
У нас есть два основных ограничения (в дополнение к ограничениям, что
x [latex] \ ge [/ latex] 0
и y [latex] \ ge [/ latex] 0, учитывая, что отрицательные порции не могут быть использованы ):
Продукт должен содержать не менее 4700 мг калия
Продукт должен содержать не более 4700 × 2 = 9400 мг калия
Математически,
В x порциях абрикосов содержится 407 x мг калия и 271 x мг калия в x порциях фиников.Сумма должна быть больше или равна 4700 мг калия, или 407 x + 271 y [латекс] \ ge [/ латекс] 4700
Та же сумма должна быть меньше или равна 9400 мг калия, или 407 x + 271 y [латекс] \ le [/ latex] 9400.
Таким образом,
Цель Функция : C = 3,33 x + 2,00 y
При соблюдении ограничений:
407 x + 271 y [латекс] \ ge [/ латекс] 4700
407 x + 271 y [латекс] \ le [/ латекс] 9400
x [латекс] \ ge [/ латекс] 0
y [латекс] \ ge [/ латекс] 0
Мы изобразим ограничения в виде уравнений:
Так как первое неравенство имеет [латекс] \ ge [/ latex], мы должны заштриховать сверху, а поскольку второе неравенство имеет [латекс] \ le [/ latex], мы должны заштриховать его снизу (Эту идею можно подтвердить, выбрав точки выше и ниже каждой строки для проверки.):
Возможная область — это участок, заштрихованный зеленым и синим цветом, между двумя линиями. Мы видим, что есть четыре угловые точки, которые образуют перевернутую трапецию, как показано на графике ниже:
Мы должны решить следующие системы, чтобы найти угловые точки (снизу вверх, слева направо)
Система 1
х = 0
407 x + 271 y = 4700
Раствор:
0 + 271
y = 4700
y ≈ 17.3
Балл: (0,17.3)
Система 2
x = 0
407 x + 271 y = 9400
Раствор:
0 + 271 и = 9400
y ≈ 34,7
Балл: (0,34.7)
Система 3
y = 0
407 x + 271 y = 4700
Раствор:
407 x + 0 = 4700
x ≈ 11.5
Балл: (11.5,0)
Система 4
y = 0
407 x + 271 y = 9400
Раствор:
407 x + 0 = 9400
x ≈ 23,1
Балл: (23.1,0)
Опять же, мы могли бы решить, используя матричные уравнения, но системы несложно решить с помощью подстановки. Поскольку проблема ограничена, мы теперь проверяем, какая из них минимизирует затраты:
Точка Стоимость
(0,17.3) 33,3 (0) = 2,00 (17,3) = 34,60 доллара США
(0,34,7) 33,3 (0) = 2,00 (34,7) = 69,40 долл. США
(11,5,0) 33,3 (11,5) = 2,00 (0) = 38,30 долл. США
(23,1,0) 33,3 (23,1) = 2,00 (0) = 76,92 доллара США
Самым дешевым способом для компании будет создание батончиков без кураги и 17,3 порции сушеных фиников.
Интересно отметить, что каждая из угловых точек соответствует либо горизонтальному, либо вертикальному пересечению.
Почему мы видим то, что видим? Это действительно случай создания реального продукта! Конечно, нет смысла увеличивать дневную норму для упаковки, так как это будет означать увеличение количества сухофруктов и, следовательно, увеличение стоимости. Поскольку стоимость сушеных фиников ниже (2 доллара США за порцию) и поскольку по цене одной порции абрикосов (3,33 доллара США за порцию) мы можем заплатить:
[латекс] \ displaystyle \ frac {{{407} {m} {g}}} {{$ {3.33}}} \ приблизительно {122.2} [/ latex] мг на доллар для абрикосов
и
[латекс] \ displaystyle \ frac {{{271} {m} {g}}} {{$ {2.00}}} \ приблизительно {135,5} [/ латекс] мг на доллар для фиников
Совершенно логично покупать финики, поскольку при той же сумме в долларах повышается содержание калия.
Остается вопрос: желательно ли требовать большее количество фиников по меньшей цене или желательно меньшее количество абрикосов по более высокой цене? Это действительно зависит от ограничений. Компания может захотеть рассмотреть объем упаковки / обработки / и т. Д. требуется в обоих случаях.Возможно, затраты на производство и упаковку могут добавить ограничения, которые повлияют на процесс принятия решений. Подобная проблема будет оставлена читателю в качестве домашнего задания.
В качестве математического примечания: то, что мы видим, происходит в результате наличия параллельных линий ограничений.
Есть два термина, с которыми мы должны быть знакомы, имея дело с неравенствами: ограниченное и неограниченное . Допустимая область называется ограниченной, если ограничения охватывают допустимую область.
То есть, если штриховка не продолжает покрывать всю плоскость, мы имеем дело с проблемой ограниченного линейного программирования.
Оба примера до сих пор были примерами задач ограниченного линейного программирования, поскольку первая допустимая область имела форму треугольника, а вторая — форму трапеции.
Если допустимая область не может быть заключена между линиями, образованными ограничениями, она называется неограниченной. Пример неограниченной задачи линейного программирования:
Пример 3
Отдел кадров работает над повышением стартовой заработной платы для новых административных секретарей и преподавателей местного колледжа.Административный секретарь начинается с 28 000 долларов, а новые преподаватели получают 40 000 долларов. Колледж хотел бы определить процентное увеличение для каждой группы, учитывая, что в следующем учебном году колледж будет нанимать 8 секретарей и 7 преподавателей. Колледж может потратить не более 5000 долларов на прибавку к зарплате. Какой должен быть процент увеличения для каждой группы?
Решение
Наша цель — определить процентное увеличение для административных секретарей и преподавателей, поэтому пусть
x = процентное увеличение для секретарей
y = процентное увеличение для профессорско-преподавательского состава
Колледж хотел бы минимизировать свои общие расходы, поэтому целевая функция должна включать общую сумму оттока денег.Поскольку для новых секретарей потребуется общий бюджет в размере
долларов США × 8 = 224000 долларов США, а для преподавателей — общий бюджет в размере 40000 долларов США × 7 = 280000 долларов США, общая стоимость будет равна проценту повышения для каждой группы, умноженному на общую зарплату:
С = 224x + 280y
Существует одно ограничение: общая сумма рейзов должна быть не более 5000 долларов. То есть
224 x + 280 y [латекс] \ le [/ латекс] 5
Конечно, в колледже не хотят снижать зарплаты, поэтому
x [latex] \ ge [/ latex] 0 и y [latex] \ ge [/ latex] 0.
Чтобы визуализировать ситуацию, мы изобразим ограничение в виде уравнения. Чтобы помочь нам найти точки, мы сначала находим точки перехвата:
Горизонтальное пересечение:
224 (0) + 280
y = 5
y ≈ 0,018
Пересечение по вертикали
224 x + 280 (0) = 5
x ≈ 0,022
Затем мы наносим точки и соединяем их прямой линией:
Так как знак неравенства [латекс] \ le [/ latex], заштриховываем под линией:
Это дает нам три угловых точки, как показано выше.Мы тестируем каждую, чтобы проверить, какая из пар процентов дает минимальную стоимость:
доллара США
Точка Стоимость
(0,0) 224 (0) + 280 (0) = 0
(0, 0,018) 224 (0) + 280 (0,018) = 5,04 доллара США
(0,020,0) 224 (0,020) + 280 (0) = 4,48 доллара США
Очевидно, что первый вариант дает наименьшую стоимость; однако эта комбинация говорит нам о повышении 0% для обеих групп, что, конечно, нецелесообразно, поскольку цель компании состояла в том, чтобы повысить прибавку для каждой группы.
Почему это произошло и что нам делать, чтобы это исправить? Что ж, когда мы думаем об ограничении тратить 5000 долларов или меньше и надеяться сделать расходы как можно меньшими, разве не имеет смысла сказать «ничего не трать!»? Этот результат будет происходить каждый раз, когда мы минимизируем, имеем ограничения со знаком неравенства
le и когда начало координат включено в допустимую область. Чтобы решить эту проблему, компания должна сделать дополнительные спецификации, например, каков минимальный процент надбавки для каждой группы? Желательно ли, чтобы один из рейзов был больше другого? Это вопросы, которые аналитик должен обсудить с отделом кадров и администрацией.
1) Решите каждую из следующих задач линейного программирования.
a) Развернуть R = 2 x + 3 y
Согласно
–2 x — y [латекс] \ ge [/ latex] –10
x + 3y [латекс] \ ge [/ латекс] 6
x [латекс] \ ge [/ латекс] 0
y [латекс] \ ge [/ латекс] 0
Решение: R = 30 при (0,10)
B) Свернуть T = 3 x + y
Согласно
x + 2 y [латекс] \ ge [/ латекс] 4
x + 3 y [латекс] \ ge [/ латекс] 6
x [латекс] \ ge [/ латекс] 0
y [латекс] \ ge [/ латекс] 0
Решение: R = 2 при (0,2)
2) Правление местной школы утверждает новую программу обучения математике, которая должна быть реализована в ряде начальных школ округа.Деньги на программу будут поступать из двух разных бюджетов: бюджета государственных расходов и бюджета инициатив начальной школы. Правление готово платить по крайней мере половину того, что поступает из бюджета инициативы из своего бюджета государственных расходов. Поскольку эта программа считается инициативой, правительство требует, чтобы не менее 2000 долларов поступало из бюджета местных инициатив. Оба бюджета частично финансируются за счет федерального чрезвычайного финансирования. Для бюджета государственных расходов процентная доля составляет 55% и 23% для бюджета инициатив начальной школы.Чтобы правильно использовать чрезвычайное финансирование, округ хотел бы свести к минимуму использование федеральных долларов. Сколько должно поступать из каждого бюджета?
Решение: x = сумма расходов на публикацию; y = сумма от инициатив начальной школы
Свернуть: C = 0,55x + 0,23y
(1/2) x≥y или {(1/2) x-y≥0}
года ≥2000
х, y≥0
Решение: C = 2660, x = 4000, y = 2000
3) Директор по связям с общественностью гомеопата стремится рекламировать продукцию своей компании на двух разных веб-сайтах: один является поставщиком медицинских запчастей, а другой — электронным журналом о фитнесе (веб-журналом).Веб-сайт поставщиков медицинских запчастей получает в среднем около 1 200 000 посещений в день на страницу, в то время как электронный журнал о фитнесе получает около 2 000 000 посещений в день на страницу. Ежедневная стоимость рекламы составляет 1100 долларов за рекламу и 1600 долларов за рекламу, соответственно. Режиссер хочет как минимум 15 рекламных роликов и может выделить на рекламу до 50 000 долларов. На каждом сайте должно быть размещено минимум 3 объявления. Сколько объявлений нужно разместить на каждом веб-сайте, чтобы увеличить потенциальное количество читателей (даже если некоторые зрители видят добавление на разных страницах сайта)?
x = номер на медицинском сайте; y = номер на сайте фитнеса.
Развернуть: R = 1200000x + 2000000y
При условии:
х + у≥15
1100x + 1600y≤50000
x≥3
года ≥3
х, y≥0
Угловые точки R = 1200000x + 2000000y
(3,12) 27 600 000
(12,3) 20 400 000
(3,29,2) 62 000 000
(41.1,3) 55 320 000
Оптимальное решение
См. Другие примеры в следующем разделе.
Линейное программирование: примеры проблем со словами
линейный Программирование: проблемы со словами (стр. 3 из 5)
Разделы: Оптимизация линейные системы, Постановка задач со словами
Расчетная компания производит научный калькулятор и графический калькулятор.Долгосрочное прогнозы указывают на ожидаемый спрос не менее 100 научный и 80 графические калькуляторы каждый день. Из-за ограничений на производство вместимость, не более 200 научный и 170 Графические калькуляторы можно делать ежедневно. Для выполнения договора на отгрузку, всего не менее 200 калькуляторы будут поставляться каждый день.
Если каждый научный калькулятор продано результаты в $ 2 убыток, но каждый графический калькулятор дает $ 5 прибыль, сколько каждого вида должно производиться ежедневно, чтобы максимизировать чистую прибыль?
В вопросе задается оптимальное количество калькуляторов, поэтому мои переменные будут соответствовать:
Поскольку они не могут производить отрицательные числа калькуляторов, у меня есть два ограничения, x > 0 и y > 0.Но в этом случае я могу игнорировать эти ограничения, потому что я уже иметь это x > 100 и y > 80. Также упражнение дает максимумы: x < 200 и y < 170. Минимальная доставка требование дает мне x + и > 200; в другом слова, y > х + 200.Отношение прибыли будет моим уравнением оптимизации: P = 2 x + 5 y . Итак вся система:
P = 2 x + 5 y , при условии:
100 < x < 200
80 < y < 170
y > x + 200
График выполнимости области выглядит следующим образом: Авторские права Элизабет Стапель 2006-2011 Все права защищены
Когда вы проверяете угловые точки в (100, 170), (200, 170), (200, 80), (120, 80), и (100, 100), вы должны получить максимальное значение P = 650 при ( x , y ) = (100, 170).Это решение «100 научные калькуляторы и 170 графические калькуляторы ».
Вам нужно купить шкафы. Вы знаете, что шкаф X стоит 10 долларов за единицу, требует шесть квадратных футов площади и вмещает восемь кубических футов файлов. Шкаф Y стоит 20 долларов за единицу, требует восьми квадратных футов площади пола, и вмещает двенадцать кубических футов файлов. Вам дали 140 долларов за это покупка, хотя вам не нужно тратить так много.В офисе есть комната для шкафов площадью не более 72 квадратных футов. Сколько какой модели стоит ли покупать, чтобы максимально увеличить объем хранилища?
Вопрос задайте по количеству шкафов Мне нужно купить, поэтому мои переменные будут соответствовать:
Естественно, x > 0 и y > 0. Надо учесть стоимость и площадь пола («площадь основания» каждой единицы), в то время как максимальное увеличение объема хранилища, поэтому мои ограничения будут ограничиваться расходами и занимаемой площадью, а объем будет моим уравнением оптимизации.
Стоимость: 10 x + 20 y < 140, или y < (¹/₂) x + 7
пространство: 6 x + 8 y < 72, или y < (³/₄) x + 9
объем: В = 8 x + 12 y
Эта система (вместе с первыми двумя ограничения) графики как:
Когда вы проверяете угловые точки в (8, 3), (0, 7) и (12, 0), вы должны получить максимальную громкость из 100 кубических футов, купив восемь моделей X и три модели Y.
<< Предыдущая Вверх | 1 | 2 | 3 | 4 | 5 | Вернуться к указателю Далее >>
Цитируйте эту статью как:
Стапель, Елизавета. «Линейное программирование: проблемы со словами». Purplemath . Доступно по номеру
https: // www.purplemath.com/modules/linprog3.htm . Доступ [Дата] [Месяц] 2016 г.
примеров линейного программирования | Суперпроф
Что такое линейное программирование?
Линейное программирование используется для оптимизации линейной целевой функции и системы линейных неравенств или уравнений. Ограничения, установленные для целевой функции, называются ограничениями.Целевая функция представляет собой количество, которое необходимо минимизировать или максимизировать. Основная цель линейного программирования — оптимизировать целевую функцию.
Допущения для задачи линейного программирования приведены ниже:
Ограничения целевой функции, известные как ограничения, записываются в форме количественных значений.
Целевая функция должна быть линейной функцией.
Связь между целевой функцией и ограничениями должна быть линейной.
Задачи линейного программирования могут быть решены несколькими методами. Наиболее распространенными методами являются симплексный метод, решение задач с использованием R или открытого решателя и графический метод. В этой статье мы будем решать задачи линейного программирования с использованием графического метода.
Пример 1
Магазин попросил производителя произвести брюки и спортивные куртки.
Для материалов производитель имеет
хлопчатобумажных тканей и полиэстера. Каждая пара брюк (1 шт.) Должна быть из хлопка и полиэстера.Каждой куртке нужен хлопок и полиэстер. Цена на брюки установлена на уровне 50 долларов, а на куртку — 40 долларов. Какое количество брюк и курток производитель должен отдать в магазины, чтобы эти предметы получили максимальную распродажу?
Лучшие доступные репетиторы по математике
Первый урок бесплатно
Решение
Шаг 1. Определите переменные решения
Выберите неизвестные.
x = количество брюк
y = количество курток
Шаг 2 —
Запишите целевую функцию .
Шаг 3 — Определите набор ограничений
Чтобы записать ограничения, используйте таблицу:
_{7 ₉}_{9 1}_{9 5}
брюки куртки доступны хлопок
750
полиэстер 2 1 1,000
Так как количество брюк и курток — натуральные числа, 2000, есть еще два ограничения: 0
y ≥ 0
Шаг 4 — Выберите метод решения задачи
Существует множество методов решения метода линейного программирования.В этой задаче мы найдем решение проблемы графически.
Шаг 5 — Постройте график
Изобразите ограничения графически.
Поскольку x ≥ 0 и y ≥ 0, работать в первом квадранте.
Изобразите прямые линии от их точек пересечения с осями.
Пример 1 — График
Решите неравенство графически:
и возьмите точку на плоскости, например (0,0).
Начиная с
, точка (0,0) находится в полуплоскости, где выполняется неравенство.
Аналогично решите
.
Шаг 6 — Определите допустимую область
Область пересечения решений неравенств будет решением системы неравенств, которая представляет собой набор из возможных решений .
Шаг 7 — Найдите оптимальную точку
Вычислите координаты вершин из набора возможных решений.
Оптимальное решение, если оно уникально, находится в вершине.Это решения для систем:
;
Теперь мы вычислим значение целевой функции в каждой из вершин, чтобы определить, какая из них имеет максимальное или минимальное значение. Необходимо учитывать возможное отсутствие решения, если соединение не ограничено.
В целевой функции поместите каждую из вершин, которые были определены на предыдущем шаге.
Максимум
Оптимальное решение — изготовить 375 брюк и 250 курток, чтобы получить прибыль в размере 28 750 долларов.
Решение не всегда уникальное, поэтому мы можем найти и другие решения.
Пример 2
У Марии есть интернет-магазин, где она продает картины и открытки ручной работы. Она продает картину за 50 долларов, а карту — за 20 долларов. Ей нужно 2 часа, чтобы закончить 1 картину, и 45 минут, чтобы сделать одну открытку. У нее также есть дневная работа, а в свободное время она рисует картины и открытки. Она не может тратить более 15 часов в неделю на создание картин и открыток. Дополнительно она должна делать не более 10 картин и открыток в неделю.
Она получает прибыль в 25 долларов на рисовании и 15 долларов на каждой карточке. Сколько картин и открыток ей нужно делать каждую неделю, чтобы получать максимальную прибыль.
Решение
Выполните следующие действия, чтобы решить указанную выше проблему.
Шаг 1 — Определите переменные решения
x = количество картин
y = количество карточек
Шаг 2 — Напишите целевую функцию
Так как она получает 25 долларов прибыли с каждой проданной картины и 15 долларов на каждой проданной картине. каждая проданная карта, поэтому целевая функция:
Шаг 3 — Определите набор ограничений
Ей требуется 2 часа, чтобы закончить картину, и 45 минут, чтобы сделать карту.Она не может тратить более 15 часов в неделю на изготовление открыток и рисование.
Она должна делать не более 10 картин и открыток в неделю.
У нас также есть два других ограничения:
и
Шаг 4 — Выберите метод решения задачи
Мы будем использовать графический метод для решения этой проблемы.
Шаг 5 — Построение графика
График — Пример 2
Шаг 6 — Определите допустимую область
Зеленая выделенная область — это область выполнимости графика
Область возможности графика
Шаг 7 — Найдите оптимальную точку
Используйте координаты вершин и подставьте их в целевую функцию, чтобы получить точку максимума.
Максимум
Приведенные выше расчеты показывают, что Мария может получить максимальную прибыль в 210 долларов в неделю, сделав 6 картин и 4 карты .
Страница не найдена | MIT
Перейти к содержанию ↓
Образование
Исследовать
Инновации
Прием + помощь
Студенческая жизнь
Новости
Выпускников
О MIT
Подробнее ↓
Прием + помощь
Студенческая жизнь
Новости
Выпускников
О MIT
Меню ↓ Поиск Меню Ой, похоже, мы не смогли найти то, что вы искали!
Попробуйте поискать что-нибудь еще! Что вы ищете? Увидеть больше результатов
Предложения или отзывы?
Страница не найдена | MIT
Перейти к содержанию ↓
Образование
Исследовать
Инновации
Прием + помощь
Студенческая жизнь
Новости
Выпускников
О MIT
Подробнее ↓
Прием + помощь
Студенческая жизнь
Новости
Выпускников
О MIT
Меню ↓ Поиск Меню Ой, похоже, мы не смогли найти то, что вы искали!
Попробуйте поискать что-нибудь еще! Что вы ищете? Увидеть больше результатов
Предложения или отзывы?
примеров задач линейного программирования
примеров задач линейного программирования
Задачи линейного программирования
1.У фермера есть 10 акров земли для посадки пшеницы и рожь. Он должен посадить не менее 7 соток. Однако у него всего 1200 долларов. потратить, и каждый акр пшеницы стоит 200 долларов, чтобы посадить, а каждый акр посадка ржи стоит 100 долларов. Более того, фермер должен получить посадку сделано за 12 часов, и требуется час, чтобы засеять гектар пшеницы, и 2 часов, чтобы засеять гектар ржи. Если прибыль составляет 500 долларов с акра пшеницы и 300 долларов за акр ржи, сколько акров каждого должно быть посадили для максимальной прибыли?
2.У переработчика золота есть два источника золотая руда, источник A и источник B. ежедневно необходимо перерабатывать не менее трех тонн руды. Руда из Стоимость переработки источника A составляет 20 долларов США за тонну, а стоимость переработки руды из источника B 10 долларов за тонну на переработку. Затраты не должны превышать 80 долларов в день. Более того, Федеральные правила требуют, чтобы количество руды из источник B не может превышать удвоенное количество руды из источника A. Если руда из источника A дает 2 унции. золота на тонну и руды из источника B дает 3 унции.золота на тонну, сколько тонн руды из обоих источников должны обрабатываться каждый день, чтобы максимизировать количество добытого золота с учетом вышеуказанных ограничений?
3. У издателя есть заказы на 600 экземпляров определенного текста из Сан-Франциско и 400 экземпляров из Сакраменто. Компания имеет 700 экземпляров на складе в Новато и 800 экземпляров на складе в Лоди. Доставка текста из Новато в Сан-Франциско стоит 5 долларов, а доставка в Сакраменто стоит 10 долларов.Доставка текста из Лоди в Сан-Франциско стоит 15 долларов, а из Лоди в Сакраменто — 4 доллара. Сколько копий компания должна отправить с каждого склада в Сан-Франциско и Сакраменто, чтобы выполнить заказ с наименьшими затратами?
.

	брюки	куртки	доступны	хлопок
750
полиэстер	2	1	1,000

РубрикаРазное

Точка	Стоимость
(0,17.3)	33,3 (0) = 2,00 (17,3) = 34,60 доллара США
(0,34,7)	33,3 (0) = 2,00 (34,7) = 69,40 долл. США
(11,5,0)	33,3 (11,5) = 2,00 (0) = 38,30 долл. США
(23,1,0)	33,3 (23,1) = 2,00 (0) = 76,92 доллара США

Точка	Стоимость
(0,0)	224 (0) + 280 (0) = 0
(0, 0,018)	224 (0) + 280 (0,018) = 5,04 доллара США
(0,020,0)	224 (0,020) + 280 (0) = 4,48 доллара США

Угловые точки	R = 1200000x + 2000000y
(3,12)	27 600 000
(12,3)	20 400 000
(3,29,2)	62 000 000
(41.1,3)	55 320 000