Модель линейного программирования


Формально выражаясь, задача линейного программирования связана с оптимизацией процесса, в ходе которого отбираются неотрицательные искомые переменные X], Х2, ..., Х3, используемые затем для максимизации (или минимизации) целевой функции в следующей форме.

Максимизировать (минимизировать) целевую функцию

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

где Сп, Атп и Вт — заданные постоянные величины.
В зависимости от типа задачи ограничения могут указываться также с использованием знака равенства (=) или знака "больше или равно" (gt;).
Графическое линейное программирование
Несмотря на то, что графическое линейное программирование (Graphical Linear Programming) применяется только для решения задач с двумя искомыми переменными (или в случае с трехмерными графиками — тремя), этот метод позволяет быстро понять основную суть линейного программирования и иллюстрирует, что происходит при использовании симплексного метода, описанного дальше в этой главе.
Порядок решения задач графическим методом описывается ниже в контексте задачи, связанной с деятельностью компании Puck and Pawn, специализированной на производстве хоккейных клюшек и наборов шахмат. Каждая клюшка приносит компании прибыль в размере 2 долл., а каждый шахматный набор — 4 долл. На изготовление одной клюшки требуется четыре часа работы на участке А и два часа на участке В. Шахматный набор изготавливается с затратами шести часов работы на участке A, шести часов на участке В и одного часа на участке С. Доступная производственная мощность (Capacity Available), выраженная в рабочих часах, участка А составляет максимум 120 часов в день; участка В — 72 часа, а участка С— 10 часов.
Вопрос: сколько клюшек и шахматных наборов должна выпускать в день компания, чтобы получать максимальную прибыль? Сформулируйте задачу с использованием математических символов. Если

обозначить количество хоккейных клюшек через H, а количество шахматных наборов — G, то целевую функцию (Objective Function) для достижения максимальной прибыли можно выразить следующим образом.
Максимизировать Z = $2H + $4G;
при условии следующих ограничений по мощностям: 4Н + 6G lt; 120 (ограничение по участку А); 2H + 6G lt; 72 (ограничение по участку В); 1G lt; 10 (ограничение по участку C); и при условии, что Н, G gt; 0.
Такая формулировка удовлетворяет всем пяти условиям, предъявляемым к задачам линейного программирования, описанным ниже. Речь идет об ограниченных ресурсах (конечное число рабочих часов по каждому из участков). Точно сформулирована целевая функция (известны значения каждой переменной и цель задачи). Все уравнения носят линейный характер (в них отсутствуют экспоненты и комбинационные составляющие). Ресурсы однородны (для их оценки использована одна и та же единица измерения, т.е. рабочее время). Искомые переменные — делимые и неотрицательные значения (можно изготовлять и части хоккейной клюшки или шахматного набора; однако не забывайте, что если такой подход нежелателен, то следует воспользоваться методом целочисленного программирования).
2. Построите график уравнений ограничений. Уравнения ограничений легко отображаются на графике при присвоении одной из переменных нулевого значения и нахождении значения другой на соответствующей оси координат. (Нецелые части в неравенствах ограничений на данном этапе игнорируются.) Так, для уравнения ограничений по участку А при R = 0, G = 20, а при G = 0, Н = 30. Для уравнения ограничений по участку В при Н = 0 имеем G= 12, а при G= 0, Н= 36. Для уравнения ограничений по участку С G= 10 при любых значениях Н. Соответствующие прямые показаны на рис. 7д.1.

Рис. 7д. 1. Графическое решение задачи о хоккейных клюшках и шахматных наборах


H

G

Пояснение

0

120/6=20

Пересечение ограничения (1) с осью G

120/4=30

0

Пересечение ограничения (1) с осью Н

0

72/6=12

Пересечение ограничения (2) с осью G

72/2=36

0

Пересечение ограничения (2) с осью Н

0

10

Пересечение ограничения (3) с осью G

0

32/4=8

Пересечение линии равной прибыли (целевой функции), соответствующей $32, с осью G

32/2=16

0

Пересечение линии равной прибыли, соответствующей $32, с осью Н

0

64/4=16

Пересечение линии равной прибыли, соответствующей $64, с осью G

64/2=32

0

Пересечение линии равной прибыли, соответствующей $64, с осью Н
Определите допустимую область.
Направление знака неравенства в каждом ограничении определяет область, в которой следует искать допустимое решение. В данном случае все неравенства носят характер "меньше или равно", что означает, что недопустимо искать любую комбинацию изделий, расположенную на графике справа и сверху от линий ограничений. Область допустимых решений на графике рис. 7д. 1 закрашена серым и имеет форму выпуклого многоугольника. Такой многоугольник бывает выпуклым только при условии, что прямая линия, соединяющая любые две точки в нем, остается в его пределах. При невыполнении данного условия задача либо неправильно сформулирована, либо не подлежит решению методом линейного программирования. Постройте график целевой функции. Целевая функция отображается на графике следующим образом. Задайте какую-то произвольную величину общей прибыли и найдите отрезки на осях координат, отсекаемые целевой функцией, как это было сделано для уравнений ограничений. Целевую функцию в данном контексте часто называют линией равной прибыли, или линией равносильного вклада, поскольку она отображает все возможные комбинации двух видов продукции для заданной прибыли. Так, например, на штриховой прямой, на графике ближе всех расположенной к началу координат, мы можем определить все возможные комбинации хоккейных клюшек и шахматных наборов, которые дадут прибыль в 32 долл., выбрав для этого любую точку на прямой и найдя соответствующие количества каждого из производимых изделий по ее координатам. Так, для точки а комбинация, которая принесет компании прибыль в 32 долл., будет 10 клюшек и 3 набора. Этот результат можно проверить подстановкой полученных с помощью графика значений Н — 10, G = 3 в уравнение целевой функции:
($2 х 10) + ($4 х 3) = $20 + $12 = $32. Найдите оптимальную точку. Можно математически доказать, что оптимальная комбинация искомых переменных всегда находится в крайней (угловой) точке выпуклого многоугольника. На графике рис. 7д.1 таких точек четыре (исключая точку начала оси координат), и для определения того, какая из них оптимальная, существует два способа. Первый заключается в алгебраическом поиске решений для разных вершин многоугольника и отыскании среди них вершины с максимальной прибылью. Такой метод предполагает
одновременное решение уравнений для разных пар пересекающихся прямых и подстановку полученных параметров переменных в целевую функцию. Так, например, вычисления для пересечения линий 2Н +6(7= 72 и G = 10 будут следующими. Поставив G = 10 в 2Н + 6G = 72, получаем
2Н+ (6х 10) = 72.
Следовательно, 2H= 12, а Н= 6. Подставив в целевую функцию значения H=6 и G = 10, получаем
прибыль = $2# + $4G = ($2 х 6) + ($4 х 10) =
$12 + $40 = $52.
Этот метод можно немного видоизменить, взяв параметры Н и G непосредственно из графика и подставляя их в целевую функцию, как это делалось в процессе предыдущих вычислений. Недостаток данного подхода: при решении задач с большим количеством ограничительных уравнений возможных точек для оценки бывает очень много, и процедура математического тестирования каждой из них становится просто неэффективной.
Второй метод, который обычно предпочитают специалисты, заключается в непосредственном поиске оптимальной точки на линии равной прибыли. Эта процедура состоит в том, что на графике проводится прямая, параллельная любой произвольно выбранной исходной прямой равной прибыли, но наиболее удаленной от начала координат графика в пределах области допустимых значений. (В задачах на минимизацию затрат прямая равной прибыли должна проходить через точку, самую близкую к началу координат.) На рис. 7д.1 крайнюю (угловую) точку пересекает штриховая линия, соответствующая уравнению $2H+ $4G= $64. Обратите внимание, что исходная произвольно выбранная прямая равной прибыли обязательна, поскольку она отображает угол наклона целевой функции для конкретной задачи2.
2              Угол наклона целевой функции определяется коэффициентом, который в данном примере равен —
2. Обозначив прибыль через Р, имеем P=$2H+$4G;$2H=P-$4G, H=pl2-2G. Из этого следует, что значение коэффициента наклона равно — 2.
Это очень важно, так как при другой целевой функции (например, попробуйте подставить в значение прибыли 3Н+ 3G) наиболее удаленной от начала оси координат может быть другая точка. При условии, что уравнение $2H+$4G=$64 является оптимальным, значение каждой переменной, указывающее, какое количество изделий следует производить, можно определить по графику для оптимальной точки: 24 хоккейные клюшки и 4 шахматных набора. Любые другие комбинации дадут компании меньшую прибыль.
<< | >>
Источник: Ричард Чейз, Николас Дж. Эквилайн, Роберт Ф. Якобс. Производственный и операционный менеджмент. 8-е издание. 2004

Еще по теме Модель линейного программирования:

  1. МЕТОДЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
  2. Применение линейного программирования
  3. Метод линейного программирования в решении управленческих задач
  4. § 36.1. ПРОСТАЯ МОДЕЛЬ ЛИНЕЙНОЙ РЕГРЕССИИ
  5. § 36.4. ПРЕДСКАЗАНИЯ И ПРОГНОЗЫ НА ОСНОВЕ ЛИНЕЙНОЙ МОДЕЛИ РЕГРЕССИИ
  6. ГЛАВА 36.ЛИНЕЙНАЯ РЕГРЕССИЯ
  7. Глава 4 НАЦИОНАЛЬНОЕ ПРОГРАММИРОВАНИЕ
  8. Превращение линейных менеджеров в лидеров персонала
  9. Линейные многокаскадные системы снабжения
  10. Линейные графики в упорядочении плановых действий
  11. § 36.7. ИСПЫТАНИЕ ГИПОТЕЗЫ ДЛЯ ОЦЕНКИ ЛИНЕЙНОСТИ СВЯЗИ
  12. § 36.8. ДОВЕРИТЕЛЬНЫЕ ИНТЕРВАЛЫ В ЛИНЕЙНОМ РЕГРЕССИОННОМ АНАЛИЗЕ
- Cвязи с общественностью - PR - Бренд-маркетинг - Деловая коммуникация - Деловое общение и этикет - Делопроизводство - Интернет - маркетинг - Информационные технологии - Консалтинг - Контроллинг - Корпоративное управление - Культура организации - Лидерство - Литература по маркетингу - Логистика - Маркетинг в бизнесе - Маркетинг в отраслях - Маркетинг на предприятии - Маркетинговые коммуникации - Международный маркетинг - Менеджмент - Менеджмент организации - Менеджмент руководителей - Моделирование бизнес-процессов - Мотивация - Организационное поведение - Основы маркетинга - Производственный менеджмент - Реклама - Сбалансированная система показателей - Сетевой маркетинг - Стратегический менеджмент - Тайм-менеджмент - Телекоммуникации - Теория организации - Товароведение и экспертиза товаров - Управление бизнес-процессами - Управление знаниями - Управление инновационными проектами - Управление качеством товара - Управление персоналом - Управление продажами - Управление проектами - Управленческие решения -