<<
>>

15.1. ПРОСТОЙ ПРИМЕР ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Рассмотрим задачу о питании с экономической точки зрения, как это сделал Штиглер [15]. Потребитель покупает ряд продуктов питания: хлеб, мясо, молоко и т. п. Как это обычно предусматривается теорией поведения потребителей, в определении производимых им закупок играют роль, например, рыночные цены, уровень его дохода, а также «предпочтение», оказываемое им различным продуктам.

Чем же вызывается такое предпочтение? Частично его вкусами и привычками в потреблении (а также привычками его соседей). Однако частично оно может также являться отражением его потребности в питательных веществах (по калорийности, содержанию белков, витаминов и т. п.).

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

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

Рассмотрим простой пример для двух продуктов: Х1 (хлеб) и Х2 (сыр), которые характеризуются двумя показателями питательной ценности — калорийностью (в калориях) и содержанием белка (в граммах). Известны следующие данные: 1 фунт хлеба дает 1000 калорий и содержит 25 г белка, 1 фунт сыра — 2000 калорий и 100 г белка. Минимально необходимая суточ- Суточная потребность

.Единица продукта

Х\ (хлеб) Хч (сыр) 21 2

6

3

1

Цена (пенсов за фунт) Калорий (тыс.) . . . . Белков (единиц; 1 еди- 1

4

4

ница=25 г) . . . . ная норма равна 3000 калорий и 100 г белка. По рыночным ценам 1 фунт хлеба стоит 6 пенсов, 1 фунт сыра — 1 шиллинг 9 пенсов (или 21 пенс). Эти данные можно упорядоченно записать в виде таблицы (стр. 440), предварительно введя более удобные единицы измерения (тысячу калорий; единицу, равную 25 г белка; 1 фунт хлеба или сыра). Тогда задача формулируется следующим образом. Найти значения суточных покупок хг и х2 (в фунтах), минимизирующие выражение

z = 6хг + 21я2

при условии

я1 + 2Я2>3, ^

хх + 4Х2 > 4, хг >0, х2 > 0. ,

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

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

z = 6хг + 2\х2

при условии, ЧТО (2)

хх -J- 2х2== 3,

хх + 4Х2 = 4.

Трудность заключается в том, что система уравнений (2) содержит слишком много ограничений; любые два из трех уравнений системы дают «решение».

Например, можно определить минимум z при условии выполнения одного ограничения хг + 2х2 = 3. Подставим в уравнение z = 6хг + 21х2 значение хг = 3—2х2 из этой же системы уравнений:

z = 6хх + 21Х2 = 18 + 9я2,

и минимум выражения z (при неотрицательных хЛ получится при х2 = 0, а значит хх = 3. Следовательно, минимальная стоимость питания составит 18 пенсов в сутки, если покупать 3 фунта хлеба, а сыра не покупать вовсе. При таком «решении» достигается (в соответствии с использованным нами одним ограничением) требуемая калорийность питания (3000 калорий в сутки), но не удовлетворяется суточная потребность в белках (100 г), что легко проверить — рацион питания содержит лишь 75 г белков. С другой стороны, два ограничивающих условия сами по себе также дают «решение». Из системы уравнений хг + 2х2 = 3 и х1 + 4я2 = 4 мы получаем хг = 2 и х2 = 88/2. При этом решении удовлетворяются оба требования (в отношении калорийности и содержания белка), но совершенно не принимается во внимание стоимость рациона.

Приведенную нами простую задачу линейного программирования (1) можно решить графически (рис. 50). В плоскости Охгх2 прямая А А' соответствует уравнению хх + 2Х2 = 3, а прямая ВВ' — уравнению хх + 4я2 = 4. Наличие неравенств в задаче (1) свидетельствует о том, что допустимые решения образуют множество точек (х19 х2) на заштрихованной области рис. 50. Остается выбрать ту из точек заштрихованной области, которая соответствует минимальной стоимости рациона питания. Нанесем на рис. 50 (пунктиром) прямые, соответствующие постоянной стоимости рациона:

z = + 21Я2 = const.

Это — параллельные прямые, и тангенс угла их наклона относительно оси абсцисс равен (—89/7). Стоимость питания, характеризуемая такой прямой, тем меньше, чем ближе прямая к точке О. Следовательно, стоимость питания является минимальной в Р, точке пересечения прямых АА' и ВВ'. Оптимальным допустимым решением будет:

1 1

хх = 2, ж2 = — z = 22 у (минимум). Если мы ежедневно покупаем 2 фунта хлеба и г/2 фунта сыра, удовлетворяется потребность организма в питательных веществах, причем стоимость питания будет минимальной, а именно 22V2 пенса в сутки.

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

Это совпадение объясняется тем, что угол наклона прямых, характеризующих постоянную стоимость, является промежуточным: он больше угла А'Ахи но меньше угла В'Вх^ Однако при изменении цен продуктов или их питательной ценности могло бы случиться, что угол наклона прямых, характеризующих постоянную стоимость,

дневно 4 фунта; при этом требования в отношении питательной ценности продуктов перевыполняются при минимальной стоимости. 2.

Аналогичным образом рассмотреть задачу (1) в тексте и ее решение, если цена 1 фунта сыра снижена до: а) 12 пенсов; б) 9 пенсов. Показать, что решения этих вариантов задачи совпадают с решениями для случая, когда цена сыра останется на уровпе 21 пенса, но хлеб подорожает до: а) 10У2 пенсов за фунт; б) 12 пенсов за фунт. 3.

Сформулировать задачу (1) в тексте, если цены хлеба и сыра соответственно равны pi и р2 (цены считаются заданными, но численные значения их не установлены). Показать, что в оптимальном решении покупается только хлеб, если pi < 1/4р2, и только сыр, если pi > У2Р2. Показать также, что оба продукта входят в набор, если 1/4/?2 < Pi < < кръ и ЧТО имеется множество решений, если pi = 1/^p2 или 4.

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

Рассмотреть задачу питания, приведенную в тексте главы, в которой продукты остаются теми же (хлеб и сыр), однако учитывается и потребность в третьем питательном веществе — в углеводах. Суточная потребность в углеводах составляет 400 г. 1 фунт хлеба содержит 250 г, а 1 фунт сыра — 50 г углеводов. Сформулировать новую задачу линейного программирования, где требуется минимизировать стоимость пищевого рациона; решить ее графически. Сравнить полученное решение с решением для случая двух показателей питательной ценности (содержание калорий и белка). Показать, что область допустимых решений на графике в зависимости * от величины «технологических коэффициентов» может быть обозначена отрезками одной прямой, двух прямых или же всех трех прямых.

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

Вернемся к задаче питания, приведенной в тексте раздела. Пусть число показателей питательной ценности по-прежнему равно двум, но для составления нормального рациона такой же питательности добавляется третий продукт, скажем мясной фарш или же макароны. Калорийность 1 фунта этого продукта равна 2000 калорий, содержание белка — 75 г, цена — 18 пенсов. Сформулировать задачу линейного программирования, если минимизируется стоимость питания. Какой вид принимает в этом случае диаграмма и графическое решение? 7.

Ниже излагается упрощенный вариант транспортной задачи, рассматриваемой в сборнике [9]. Суда совершают рейсы между портами Р и Q, и переменными являются количества рейсов (путь в оба конца) в месяц, проделанных при различных условиях:

xi — число рейсов, в которых груз перевозится в обоих направлениях;

а?2 — число рейсов, в которых груз перевозится только из Р в Q, а обратный рейс — без груза;

х3 — число рейсов, в которых суда совершают переход из Р в Q порожняком, а возвращаются с грузом;

а?4 — число рейсов без груза в оба конца.

Продолжительность в месяцах каждого из вариантов рейса соответственно составляет *2, t3 и г4. Ежемесячно необходимо перевезти из Р в Q количество груза, равное fci, а из Q в Р— равное 62. Единицей измерения количества перевозимого груза служит грузоподъемность одного судна. Требуется (при неотрицательных х) минимизировать число судов z, занятых на перевозках между портами Р и Q, то есть минимизировать

z = txXi -f- t2X2-\- = min

при условии

Что означает знак в ограничивающих условиях; можно ли без потери

общности заменить его знаком равенства? С какой целью введена переменная #4? Можно ли приравнять ее нулю? 8.

В другой простой транспортной задаче требуется минимизировать стоимость перевозки некоторого однородного продукта из портов Pi и Р2 в порты Qx и Q2- Всего груза в порту Рх имеется аг, а в порту Р2—груза а2\ необходимо Ьх продукта перевезти в порт Qx, а Ъ2— в Q2. Переменные х суть количества грузов, перевозимые между портами по каждому маршруту: Перевозки В порт Всего перевозится Qi Q2 Из порта Pi . . » » Р2 xii ^21 ^22 «1

а2 Всего . . Ьі h al+a2 = &l + &2 Стоимость перевозки единицы продукта по каждому из маршрутов равна crs (гу 5=1, 2). Показать, что отыскиваются такие неотрицательные значения х, что

Г 8

при условии

2*rs = Яг (г=1, 2),

3

2Xrs = bs (5=1,2). г

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

<< | >>
Источник: Р. Аллен. МАТЕМАТИЧЕСКАЯ ЭКОНОМИЯ. 1963

Еще по теме 15.1. ПРОСТОЙ ПРИМЕР ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ:

  1. ГЛАВА 15 ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ
  2. 15.1. ПРОСТОЙ ПРИМЕР ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
  3. 15.2. ПРОСТОЙ ПРИМЕР: ДВОЙСТВЕННАЯ ЗАДАЧА
  4. 15.3. ПРИВЕДЕНИЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ К РЕШЕНИЮ ИГРЫ
  5. 15.4. ОБЩАЯ ПРЯМАЯ И ДВОЙСТВЕННАЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
  6. 15.5. ЭКВИВАЛЕНТНОСТЬ ОБЩИХ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ И ИГРЫ С ДВУМЯ УЧАСТНИКАМИ И НУЛЕВОЙ СУММОЙ
  7. 15.6. ПРЕОБРАЗОВАНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ДЛЯ ВЫЧИСЛИТЕЛЬНЫХ ОПЕРАЦИЙ
  8. 15.9. РЕШЕНИЕ СИМПЛЕКСНЫМ МЕТОДОМ ПРОСТОЙ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
  9. 16.3. ПРЕДСТАВЛЕНИЕ ОТКРЫТОЙ СИСТЕМЫ ЛЕОНТЬЕВА В ВИДЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ПРОИЗВОДСТВЕННЫХ ОТРАСЛЕЙ
  10. 17.3. ПРЕДЕЛЬНЫЙ АНАЛИЗ И ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ ДЕЯТЕЛЬНОСТИ ФИРМЫ
  11. 17.5. ДВЕ ИЛЛЮСТРАТИВНЫЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
  12. 17.6. ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ДЛЯ ФИКСИРОВАННЫХ ФАКТОРОВ И ЗАДАННЫХ ЦЕН НА ПРОДУКТЫ
  13. 17.8. ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ДЛЯ СЛУЧАЯ НЕИЗМЕННОЙ 3 СТРУКТУРЫ СПРОСА