<< Предыдушая Следующая >>

2.2. Формы записи задачи линейного программирования и ее экономическая интерпретация

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

В задаче линейного программирования (ЗЛП) требуется найти экстремум (максимум или минимум) линейной целевой функции фс):

max(min) /(х) = Сіхг + с2х2 + ... + спхп (2.9)

при ограничениях (условиях):

«11*1 + «12*2 + •?•+ ainXn {<,=,>} &1,

«21*1 + «22*2 + •••+ «2Л*л{-'='-}Ь2. (2.10)

«ml* 1 + «т2*2 + •••+ атпХп {<, =, >} Ьт,

(2.11)

где ац, bt, Cj(i=l,m;j—l,n) — заданные постоянные величины.

Так записывается общая задача линейного программирования в развернутой форме; знак {<,=,>} означает, что в кон- кретной ЗЛП возможно ограничение типа равенства или неравенства (в ту или иную сторону).

Систему ограничений (2.10) называют функциональными ограничениями ЗЛП, а ограничения (2.11) — прямыми.

Вектор X = • •?» удовлетворяющий системе ог

раничений (2.10), (2.11), называется допустимым решением, или планом ЗЛП, т.е. ограничения (2.10), (2.11) определяют область допустимых решений, или планов задачи линейного программирования (область определения ЗЛП).

План (допустимое решение), который доставляет максимум или минимум целевой функции (2.9), называется оптимальным планом (оптимальным решением) ЗЛП.

Канонической формой записи задачи линейного программирования (КЗЛП) называют задачу вида (запись с использованием знаков суммирования):

п

Найти шах f(x) = ? сjXj (2.12)

;=1

п

при ограничениях ^ aijxj ~ ^і, і =1,т, (2.13)

/=1

х} > 0, Ьі > 0, і =1, т,; j =1, п . (2.14)

Векторная форма записи КЗЛП имеет вид:

Найти шах f(x) = СХ

при ограничениях А\Х\ + А2х2 + ... + Апхп = В, х > 0,

где С = (сь с2, ..., сп), X = (хь х2, ..., хп),

СХ — скалярное произведение векторов С,Х; А; и В — вектор-столбцы: ґ \ ап ґ \ а12 ( L \ а2\ ,А2 = а22 Um2J , ... ,Ап а2п \amnJ ,В = Ь2

\brnJ Матричная форма записи КЗЛП:

max СХ

при условиях АХ = В, X > 0.

Здесь С = (ci, C2,.--, сп) — вектор-строка; А = (аф — матрица размерности тхп, столбцами которой являются вектор- столбцы Af,

f h ^ X =

вектор-столбец.

вектор-столбец, В тУ

U Иногда используется стандартная форма записи ЗЛП: max(min) f(x) = СХ,

АХ < (>)В, Х>0.

При этом запись X > 0 понимают как вектор (или вектор-столбец в зависимости от контекста), у которого все компоненты (элементы) неотрицательны.

Приведение ЗЛП к каноническому виду осуществляется введением в левую часть соответствующего ограничения вида (2.10) k-й дополнительной переменной xn+h >0 со знаком - в случае ограничения типа > и знаком + в случае ограничения типа <.

Если на некоторую переменную хг не накладывается условие неотрицательности, то делают замену переменных хг = х'г - х", х'г > 0, х" > 0. В преобразованной задаче все переменные неотрицательные. Переход к задаче на максимум достигается изменением в случае необходимости знака у целевой функции.

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

кь. Пример 1 (задача о смесях). Стандартом предусмотрено, что октановое число автомобильного бензина А-76 должно быть не ниже 76, а содержание серы в нем — не более 0,3%. Для изготовления такого бензина на заводе используется смесь из четырех компонентов. Данные о ресурсах смешиваемых компонентов, их себестоимости и их октановом числе, а также о содержании серы приведены в таблице

Характеристика

Компонент автомобильного бензина № 1 № 2 № 3 № 4 Октановое число 68 72 80 90 Содержание серы, % 0,35 0,35 0,3 0,2 Ресурсы, т 700 600 500 300 Себестоимость, ден.ед./т 40 45 60 90 Требуется определить, сколько тонн каждого компонента следует использовать для получения 1000 т автомобильного бензина А-76, чтобы его себестоимость была минимальной.

Решение.

Для решения этой задачи сформулируем ее экономико-математическую модель, т.е. сформулируем задачу математически. Введем необходимые обозначения: пусть Xj (j = 1,2,3,4) — количество в смеси компонента с номером j. С учетом этих обозначений имеем задачу (критерий оптимальности — «минимум себестоимости»):

min /(Z) = 40*! + 45*2 + 60*3 + 90*4,

xi + х2 + х3 + х4 = 1000, (1)

68*1 + 72*2 + 80*3 + 90*4 > 76 • 1000, (2)

0,35*1 + 0,35*2 + 0,3*з + 0,2*4 < 0,3 • 1000, (3) *i < 700, х2< 600, *3 < 500, х4< 300,

xj >0,7 = 1,2,3,4.

Функциональное ограничение (1) отражает необходимость получения заданного количества смеси (1 ООО т), (2) и (3) — ограничения по октановому числу и содержанию серы в смеси, остальные — ограничения на имеющиеся объемы соответствующих ресурсов (компонентов). Прямые ограничения очевидны, но принципиально важны для выбора метода решения.

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

1it . ifc ^f ^ * v ^ м и ^

X = (хг, х2, х3, х4 ) : хг = 571 т,

х*= 0, х*3= 143 т, х*= 286 т.

Подставляя найденное решение в целевую функцию, имеем

/(х*) - 40-571 + 45-0 + 60-143 + 90-286 =57 160,0 (ден. ед.).

*

Таким образом, оптимальному решению X будет отве- « чать минимальная себестоимость в 57160,0 ден. ед.

Пример 2 (использование ограниченных ресурсов).

На участок строящейся дороги необходимо вывезти 20 000 м3 каменных материалов. В районе строительства имеются три карьера с запасами 8 000 м3, 9 000 м3 и 10 000 м3. Для погрузки материалов используются экскаваторы, имеющие производительность 250 м3 в смену в карьерах 1 и 2 и 500 м3 в смену в карьере 3.

Эти карьеры обеспечивают каменными материалами также ряд других строящихся объектов. На погрузку материалов для рассматриваемого участка выделен для экскаваторов общий лимит 60 машино-смен с правом использования его по усмотрению строителей.

Транспортные затраты на перевозку материалов характеризуются показателями: для перевозки 10 000 м3 материалов из карьера 1 требуется 1 000 автомобиле-смен, из карь- ера 2 — 1 350, из карьера 3 — 1 700 автомобиле-смен. Требуется найти оптимальный план перевозок, обеспечивающий минимальные транспортные затраты.

Решение. Сформулируем экономико-математическую модель задачи. Примем за единицу измерения количества материалов 10 ООО м3.

Обозначим через Х\ объем добычи материалов в карьере 1, *2 — в карьере 2, *з — в карьере 3. Необходимо минимизировать транспортные затраты:

min f(x) = 1 OOOxj + 1 350*2 + 1 700*3,

при ограничениях *i + + *з = 2,0, (1)

40*! + 40*2 + 20*з ? 60, (2)

0 < *! < 0,8, (3)

0 < *2 < 0,9, (4)

0<*3<1,0. (5)

Условие (1) отражает потребность в материалах, (2) — ограничение по наличию ресурса «фонд рабочего времени экскаваторов» (мы не можем использовать больше того, что у нас в наличии). Условия (3)-(5) отражают тот факт, что добыча материалов идет в условиях ограниченности запасов материалов в соответствующих карьерах. Полученная задача — задача ЛП; решив ее симплекс-методом (см. ниже), найдем оптимальный план (решение)

(*;,*2,*з) :*;= 0,8 (8 000м3);

**= 0,2 (2 000м3); х*я= 1,0 (10 000 м3).

Таким образом, из карьера 1 следует вывезти 8 000 м3 материалов, из карьера 2 — 2 000 м3, из карьера 3 — 10 000 м3. Это управленческое решение будет связано с минимальными транспортными затратами

f(X*) = 1 000-0,8 + 1 350-0,2 + 1 700-1,0 = 2 770 м (автомобиле-смен).

<< Предыдушая Следующая >>
= Перейти к содержанию учебника =

2.2. Формы записи задачи линейного программирования и ее экономическая интерпретация

  1. • Принцип оптимальности в планировании и управлении, общая задача оптимального программирования • Формы записи задачи линейного программирования и ее экономическая интерпретация • Математический аппарат • Геометрическая интерпретация задачи • Симплексный метод решения задачи 2.1. Принцип оптимальности в планировании и управлении, общая задача оптимального программирования
    Линейное программирование — это частный раздел оптимального программирования. В свою очередь оптимальное (математическое) программирование — раздел прикладной математики, изучающий задачи условной оптимизации. В экономике такие задачи возникают при практической реали- -зации принципа оптимальности в планировании и управлении. Необходимым условием использования оптимального подхода к
  2. ПОСТАНОВКА ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
    1.1.1. Формы задачи линейного программирования. В общем виде задача линейного программирования* (в дальнейшем ЗЛП) может быть сформулирована как задача нахождения наибольшего значения линейной функции на некотором множестве D ( Rn, где х ( D удовлетворяют системе ограничений и, возможно, ограничениям х1 ?0, х2 ?0,..., хj ?0,..., хn ?0. (1.3)
  3. Решение задач линейного программирования в MS Excel
    Инструментом для решений задач оптимизации в MS Excel служит надстройка Поиск решения. Процедура поиска решения позволяет найти оптимальное значение формулы, содержащейся в ячейке, которая называется целевой. Эта процедура работает с группой ячеек, прямо или косвенно связанных с формулой в целевой ячейке. Чтобы получить по формуле, содержащейся в целевой ячейке, заданный результат, процедура
  4. 14.3.3. Приведение матричной игры т?п к задаче линейного программирования.
    Пусть имеем игру размерности т?п с матрицей . Обозначим через р*=(p1;...;рт), q*=(q1;...;qn) оптимальные смешанные стратегии игроков А и В. Стратегия р* игрока А гарантирует ему выигрыш не меньше v, независимо от выбора стратегии Bj игроком В (теор. 3). Это можно записать так: ,                                     (13) где p1+p2+...+рт=1; рi?0 (i=1,…,m). Аналогично стратегия q* игрока В
  5. ГЛАВА 1. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ
    ГЛАВА 1. ЛИНЕЙНОЕ
  6. Глава 2 ОСНОВЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
    Глава 2 ОСНОВЫ ЛИНЕЙНОГО
  7. б.              Линейное программирование
    Возражение против абсолютной подвижности факторных пропорций — не более, чем отрицание абсолютной гладкости и непрерывности производственных функций. До недавнего времени закономерное пристрастие экономической науки к непрерывным дифференцируемым функциям препятствовало объективной оценке этого возражения. Тем не менее, ясно, что общее предположение о монотонном и непрерывном характере замещения
  8. 1.6. ТЕОРИЯ ДВОЙСТВЕННОСТИ В ЛИНЕЙНОМ ПРОГРАММИРОВАНИИ
    1.6.1. Понятие двойственной задачи ЛП. Пусть задана КЗЛП (1.7). Если целевая функция f(x) = cx достигает максимального значения на множестве D, то обоснованным представляется вопрос о том, каким образом можно построить верхнюю оценку для нее. Очевидно, что если через и обозначить некоторый m-мерный вектор, то Предположим, что и можно выбрать таким образом, чтобы иА ? с. Тогда
  9. 2.4. Геометрическая интерпретация задачи
    Рассмотрим задачу ЛП в стандартной форме записи: max(min)/(X)= с\Хх + с2х 2 + ?•? + спхп (2.18) при ограничениях а\\Х\ + аі2л:2 +... + ainxn < Ъ\ (2.19) (2.20) ат1х1 + ат2х2 + ... + атпхп < Ьт хj >0,j = 1,2 «21*1 + а22*2 + ••• + а2п*п ^ Ъ2 Рассмотрим эту задачу на плоскости, т.е. при га = 2. Пусть система неравенств (2.19), (2.20) совместна (имеет хотя бы одно решение): «11*1 +
  10. 4.1. ТИПЫ ЗАДАЧ ДИСКРЕТНОГО ПРОГРАММИРОВАНИЯ
    4.1.1. Основные понятия. Многие экономические задачи характеризуются тем, что объемы управляемых ресурсов (в силу тех или иных объективных свойств) могут принимать только целые значения. Математическая формализация данных ситуаций приводит к моделям дискретного программирования. В общем виде задача дискретного программирования может быть сформулирована как задача нахождения максимума (или
  11. Общая постановка задачи динамического программирования
    Пусть некоторая физическая управляемая система S находится в первоначальном состоянии s0 0. С течением времени ее состояние меняется и система приходит в конечное состояние sk k. С процессом изменения состояния системы связан некоторый численный критерий W. Необходимо так организовать процесс, чтобы критерий достиг оптимального значения. Обозначим множество возможных управлений через U. Тогда
  12. 5.2. ПРИМЕРЫ ЗАДАЧ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ
    5.2.1. Задача о найме работников. Приступим к рассмотрению вопросов применения методов динамического программирования в конкретных экономико-математических моделях. Отдельно отметим, что данные вычислительные схемы, вообще говоря, достаточно часто используются для решения некоторых задач, которые уже были затронуты в других главах. Это, прежде всего, задача о ранце, задача о кратчайшем пути,
  13. 2.1. МЕТОДЫ РЕШЕНИЯ ЗАДАЧ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
    2.1.1. Постановка задачи. Как уже упоминалось во введении, предположение о возможности описать зависимости между управляемыми переменными с помощью линейных функций далеко не всегда адекватно природе моделируемого объекта. Например, в рассмотренных в главе 1 моделях цена товара считается независимой от количества произведенного продукта, однако в повседневной жизни мы постоянно сталкиваемся с
  14. 16.5. Задача динамического программирования в терминах теории графов.
      Сформулируем задачу динамического программирования в терминах теории графов. Пусть G=(V,E) – взвешенный орграф с множеством вершин V={s0, s1, …, sп}, в котором пара {si, sk} является дугой, если и только если в ?(si) существует управление Xik (см. разд. «Задача о кратчайшем пути»). Вес дуги (si, sk) равен fik и непременно kgt;i. Обозначим через D+(si) и D-(si) множества дуг орграфа с концом si
  15. 16.4. Решение задачи о кратчайшем пути методами динамического программирования.
    Задача 2. На данной сети дорог (рис. 6) указаны расстояния из пункта в пункт. Найти кратчайший маршрут перевозки груза пункта 1 в пункт 10. ¦ Разобьем все пункты сети на группы (состояния, табл. 1). К группе 0 отнесем пункт 1, к группе 1 пункты, в которые можно попасть непосред-ственно из пункта 1 (таковыми будут 2 и 3), к группе 2 отне-сем пункты, в которые можно попасть непосредственно из
  16. 5.2. Предельная полезность и цены 5.2.1. Двойственные оценки в задачах математического программирования
    Как уже отмечалось ранее, проблема оптимизации народнохозяйственных планов тесно связана с проблемами ценообразования. В научной литературе есть мнение, настолько распространенное, что его излагают как трюизм: цены оптимального плана — это двойственные оценки, полученные в результате решения задачи, двойственной к задаче оптимального планирования (см., например, [185], [197], [317], [438], [476]
  17. Основные этапы развития технологий программирования Программирование в кодах и ассемблер
    Любая программа для ЭВМ — системная или прикладная — воспринимается (распознается) процессором только в том случае, если она состоит из специальных команд, коды которых известны процессору определенного типа. Команды записаны в памяти компьютера в специальном формате. Каждая команда состоит из ее кода, определяющего действие (сложение, вычитание и т.д.) и адресов операндов, над которыми это
  18. Интерпретация древнекитайской традиции с позиций современной экономической теории
    В наши дни китайские ученые интересуются не только применением западного теоретического инструментария к решению практических проблем экономического развития, но и возможностью осмысления заимствуемых зарубежных теорий в национальном культурно-цивилизационном контексте. Новые тенденции в развитии мировой экономической науки привносят новые акценты в процесс ее контекстуализации в Китае.
Портал "ЭКОНОМИСТЪ" © 2014-2015
info@finlit.online




Рейтинг@Mail.ru