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

Применение к линейному программированию  

 

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

 

1) Случай только двух переменных: геометрический подход

Общая задача При заданном линейном выражении z=ax+by в двух переменных x и y найти значения x и y, которые либо максимизируют. Либо минимизируют z с учетом линейных ограничений:

 

 

и

 

(В приведенных выше условиях может быть использован любой из символов). Функция z в приведенной выше задаче называется целевой функцией. Если (x, y) удовлетворяет всем ограничениям, то это называется допустимым решением. Множество всех допустимых решений является подмножеством плоскости xy, называемой допустимой областью.

 

Заметим, что каждое ограничение вида ax+by=c представляет собой прямую линию в плоскости xy, тогда как каждое ограничение вида

 определяет полуплоскость, включающую свою граничную линию .

 

Допустимая область тогда является пересечением конечного числа прямых и полуплоскостей. Если допустимая область может быть заключена в достаточно большой круг. То она называется ограниченной; в противном случае она называется неограниченной.

 

 

 

 

 

 

 

 

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

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

 

Пример 1 Производитель конфет имеет на складе 130 фунтов вишен в шоколаде и 170 фунтов мятных леденцов в шоколаде. Он решает продавать их в виде двух разных смесей. Одна смесь будет содержать половину вишни и половину мяты по весу и будет продаваться по 2,00 доллара за фунт. Другая смесь будет содержать одну треть вишни и две трети мяты по весу и будет продаваться по 1,25 доллара за фунт. Сколько фунтов каждой смеси должен приготовить производитель конфет. Чтобы максимизировать свой доход от продаж?

 

Решение Для простоты назовем А смесью половины вишни и половины мяты, а Б смесью. Которая состоит из одной трети вишни и двух третей мяты. Пусть x-количество фунтов А, которое нужно приготовить, а y-количество фунтов В. Которое нужно приготовить. Затем функция дохода может быть записана в виде

 

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

 

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

 

Теперь, поскольку производитель может использовать не более 130 фунтов вишни и 170 фунтов мяты. У нас есть ограничения:

 

 

Кроме того, мы должны иметь , следовательно. Приведенную выше задачу можно сформулировать следующим образом: найти x и y. Которые максимизируются  с учетом ограничений:

 

 

 

 

 

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

 

 

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

 

Крайняя точка

Значение z=2x+1.25 y

(0, 0)

0

(0, 255)

318.75

(180, 120)

510.00

(260, 0)

520.00

 

Из таблицы видно, что наибольшее значение для z равно 520,00, а соответствующее оптимальное решение равно (260, 0). Таким образом, производитель конфет достигает максимального объема продаж в 520 долларов. Когда он производит 260 фунтов смеси А и ни одной смеси В.

 

Пример 2 Мусорный департамент округа Осгуд управляет двумя центрами переработки отходов. Центр 1 стоит 40 долларов за восьмичасовой рабочий день. В обычный день 140 фунтов стекла и 60 фунтов алюминия осаждаются в Центре 1. Центр 2 стоит 50 долларов за восьмичасовой рабочий день. При этом 100 фунтов стекла и 180 фунтов алюминия осаждаются в день. Округ обязался поставлять не менее 1540 фунтов стекла и 1440 фунтов алюминия в неделю. Чтобы побудить переработчика открыть завод в городе. Сколько дней в неделю округ должен открывать каждый центр. Чтобы минимизировать его стоимость и при этом удовлетворить потребности переработчика?

 

Решение. Пусть x — количество дней в неделю. Когда открыт Центр 1, а y-количество дней в неделю. Когда открыт Центр 2. Задача линейного программирования. Связанная с этим вопросом. Заключается в следующем:

 

Минимизируйте функцию                        

 (Стоимость эксплуатации двух центров)

 

с учетом ограничений:

 

 

 

 

 

 

 

 

Допустимая область задачи вместе с экстремальными точками показана на следующей диаграмме

 

 

 

 

 

Область неограниченна, с тремя конечными крайними точками. Два из них легко получить из графика:

 (0, 15.4) и (24, 0). Третий обнаруживается алгебраически: (6.94, 5.69). Кроме того, мы можем предположить, что существуют и другие  “бесконечные экстремальные точки”. Поскольку область неограниченна. Можно видеть  , что эти бесконечные крайние точки не будут “оптимальными”, поскольку мы минимизируем. А не максимизируем. Таким образом, мы оцениваем целевую функцию в каждой из конечных экстремальных точек:

 

 

Крайняя точка

Значение z=40x+50y

(0, 15.4)

770

(24, 0)

960

(6.94, 5.69)

562.10

 

 

Таким образом, минимальная стоимость составляет $562,10, и она достигается. Когда Центр 1 открыт около 7 дней в неделю (восемь часов в день). А Центр 2 открыт около 6 дней в неделю (восемь часов в день) .

2) Линейное программирование с более чем двумя переменными

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

 

Симплексный алгоритм, открытый Джорджем Данцигом в 40-х годах. Является эффективным методом решения задач линейного программирования. Который делает именно это. Идея состоит в том, чтобы определить некоторые “базовые” выполнимые точки и доказать. Что максимальное значение (если оно существует) целевой функции f происходит в одной из этих точек. Мы объясним алгоритм только для стандартной задачи линейного программирования которую можно сформулировать следующим образом:

 

Максимизация целевой функции:

 

 

переменных x1, x2,…, xn с учетом ограничений:

 

 

 


 

 

 

В приведенной выше форме тот факт. Что целевая функция линейна, имеет решающее значение. Но условие неотрицательности переменных и тот факт. Что мы максимизируем f, а не минимизируем его. Не являются строгими ограничениями. Условие, что константы bj неотрицательны, является серьезным. Хотя оно выполняется во многих практических приложениях. Для нестандартного случая, пожалуйста, смотрите некоторые ссылки ниже.

 

Опишем этот алгоритм на примере:

 

Максимизировать:

с учетом ограничений:

 

 

Решение Первым шагом является преобразование неравенств в указанных выше ограничениях в равенства. Это можно сделать , добавив новые переменные: x4, x5и x6, называемые переменными slack, по одной в каждом ограничении.   Таким образом, мы получаем новую задачу:

 

Максимизировать:

 

 

 

с учетом ограничений:

 

 

 

 

 

 

 

 

 

Если (x1 , x2 ,…, x6) является решением этой новой задачи, то (x1, x2, x3) является решением исходной задачи. Действительно, ограничения явно удовлетворены. Более того, если бы (y1, y2, y3) были еще одной допустимой точкой для исходной задачи. Дающей большее значение f, то принимая

 

 

 

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

 

 

 

 

 

 

 

Дополненная матрица вышеприведенной системы:

 

 

 

 

 

 

 

 

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

 

Обратите внимание. Что способ введения переменных slack гарантирует, что столбцы. Соответствующие этим переменным. Все состоят из 0 и одного 1 и что 1 находятся в разных строках. Эти столбцы будут называться базовыми столбцами, а переменные slack-базовыми переменными в исходной таблице (они обозначены  в приведенной выше таблице). Из-за этого существует одно очевидное решение уравнений: установите все неосновные переменные равными нулю и решите для основных переменных:

 

 

Другими словами, (0,0,0,6,9,20) является допустимым решением, дающим f=0. Такое решение (со всеми неосновными переменными, равными нулю) называется базовым допустимым решением. Обратите внимание. Что нижняя запись в последнем столбце-это значение f  при базовом допустимом решении (в данном случае 0). Ключом ко всему алгоритму является следующая теорема (для доказательства читатель обращается к любому учебнику по линейному программированию, такому как S. I. Gass, Linear Programming, 4 издание):

 

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

 

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

 

Нижняя строка исходной таблицы дает f в терминах неосновных переменных

 

 

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

 

Эта модификация выполняется путем выполнения элементарных операций с строками для преобразования сводного столбца в базовый. Вопрос в том, где найти 1. Мы не помещаем 1 в последнюю строку , потому что не хотим мешать f, но его можно поместить в любое другое место в сводном столбце. Где текущая запись ненулевая (в приведенном выше примере они все квалифицируются). Выбранный вход называется pivot, и его выбирают следующим образом:

1.      Вход pivot должен быть положительным.

2.      Среди доступных положительных входов pivot-это тот. Который производит наименьшее соотношение при делении на самый правый вход в своей строке.

 

Возвращаясь к нашему примеру. Мы переписываем исходную таблицу и помещаем  символ вокруг точки разворота. Коэффициенты, соответствующие двум положительным записям в сводном столбце (здесь столбец 2). Показаны справа. Для строки 2 коэффициент не вычисляется, так как соответствующая запись в сводном столбце отрицательна. Тогда можно видеть, что ось равна 2.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Теперь выполните элементарные операции, чтобы преобразовать pivot в 1, а все остальные записи в его столбце в 0. Это приводит к:

 

 

 

 

 

 

 

 

 

Обратите внимание. Что прежняя базовая переменная x4 больше не является базовой. Потому что она имела 1 в той же строке. Что и pivot. Это называется переменная ухода. Новые базовые переменные-x2, x5и x6, а новое допустимое решение (принимая новые неосновные переменные равными нулю) — x2=0, x5=12, x6=11 и f=9. Другими словами, (0, 3, 0, 0, 12, 11) является возможным решением, дающим f=9.

 

Это лучше, чем раньше; f увеличилось с 0 до 9.

 

Теперь повторите процесс. Последний ряд здесь дает

 

 

таким образом, все еще есть надежда увеличить f , сделав x1 базовым (он имеет положительный коэффициент). Следовательно, первый столбец является сводным столбцом. И все три записи над нижней строкой являются положительными. Таблица отображается еще раз, с заданными соотношениями. И следующий поворот (с наименьшим соотношением) помечается:

 

 

 

 

 

 

 

 

 

 

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

 

 

 

 

 

 

 

Соответствующее базовое допустимое решение (установка x3=x4=x5=0) имеет вид

 

 

 

 

 

 

Другими словами, (24/7, 9/7, 0, 0, 0, 65/7) является выполнимым решением, дающим f=75/7.

 

 

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

 

 

 

 

 

таким образом, поскольку x3, x4 и x5 неотрицательны, f не может быть больше 75/7. Предыдущее решение достигает f=75/5, поэтому оно должно быть оптимальным. На этом решение примера завершается.

 

 

 

Для получения дополнительной информации о симплексном методе обратитесь к следующим страницам:

1.      Симплексный метод (пошаговое описание алгоритма)

2.      Симплексный алгоритм в 3D (Нажмите, чтобы увидеть графический подход в 3D)

3.      Интерактивная демонстрация (Используйте эту программу Java-апплета для решения вашей задачи линейного программирования) 

 

 

 

 

 

 

Рекомендации

 

АНТОН, Х. и К. РОРРЕС. Элементарная линейная алгебра: Версия приложений, 8-е изд. Нью-Йорк: John Wiley & Sons, Inc., 2000.

 

КИТ НИКОЛСОН. Линейная алгебра с приложениями, третье изд. Издательство PWS. Бостон, 1993.