Региональная и национальная экономика / Анализ финансово-хозяйственной деятельности предприятия / Арендные отношения / Аудит / Бизнес-планирование / Бухгалтерский учет и контроль / Бюджетная система / Инвестирование / Инновационная деятельность / Институциональная экономика / Информационные системы в экономике / Кризисная экономика / Лизинг / Логистика / Математические методы и и моделирование в экономике / Национальная экономика / Организация производства / Оценка и оценочная деятельность / Политическая экономия / Потребительская кооперация / Страховое дело / Теория управления экономическими системами / Теория экономики / Управление финансами на предприятии / Экономика горной промышленности / Экономика городского и сельского хозяйства / Экономика недвижимости / Экономика нефтегазовых отраслей промышленности / Экономика общественного сектора / Экономика природопользования и природоохранной деятельности / Экономика, организация и управление предприятиями / Экономическая безопасность / Экономическая статистики / Экономическая теория / Экономический анализ / Экономическое прогнозирование
<< Предыдушая Следующая >>

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. 17. КОНТРОЛЬНЫЕ ВОПРОСЫ ДЛЯ ПОДГОТОВКИ К ЭКЗАМЕНУ
    1. Введение в сетевое планирование. Программа. Операция. Некоторые сведения о графах. 2. Сетевое представление программы. Правила построения сетевого графика. 3. Критический путь, критическое время, ранние и поздние сроки свершения события. 4. Теория игр с природой. Критерии Байеса, Лапласа, Вальда, Сэвиджа, Гурвица. 5. Матричные игры двух лиц с нулевой суммой. Оптимальные решения в играх
  2. Симплекс-метод с искусственным базисом (М-метод).
    Применяется в тех случаях, когда затруднительно найти первоначальный опорный план исходной задачи ЛП, записанной в канонической форме. М-метод заключается в применении правил симплекс- метода к так называемой М-задаче. Она получается из исходной добавлением к левой части системы уравнений в канонической форме исходной ЗЛП таких искусственных единичных векторов с соответствующими
  3. ПОСТАНОВКА ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
    1.1.1. Формы задачи линейного программирования. В общем виде задача линейного программирования* (в дальнейшем ЗЛП) может быть сформулирована как задача нахождения наибольшего значения линейной функции на некотором множестве D ( Rn, где х ( D удовлетворяют системе ограничений и, возможно, ограничениям х1 ?0, х2 ?0,..., хj ?0,..., хn ?0. (1.3)
  4. 1.3. БАЗИСНЫЕ РЕШЕНИЯ И ВТОРАЯ ГЕОМЕТРИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ ЗЛП
    1.3.1. Векторная форма записи КЗЛП и ее применение. Рассмотрим каноническую задачу линейного программирования Обозначим через аj столбцы матрицы А и будем рассматривать их как векторы пространства Rm. Тогда каждому допустимому плану КЗЛП — n-мерному вектору х — соответствует неотрицательная линейная комбинация столбцов аj, равная столбцу b( Rm: Такое
  5. • Принцип оптимальности в планировании и управлении, общая задача оптимального программирования • Формы записи задачи линейного программирования и ее экономическая интерпретация • Математический аппарат • Геометрическая интерпретация задачи • Симплексный метод решения задачи 2.1. Принцип оптимальности в планировании и управлении, общая задача оптимального программирования
    Линейное программирование — это частный раздел оптимального программирования. В свою очередь оптимальное (математическое) программирование — раздел прикладной математики, изучающий задачи условной оптимизации. В экономике такие задачи возникают при практической реали- -зации принципа оптимальности в планировании и управлении. Необходимым условием использования оптимального подхода к
  6. КЛЮЧЕВЫЕ ПОНЯТИЯ
    > Игра, игрок, стратегия. > Игры с нулевой суммой. > Матричные игры. > Антагонистические игры. > Принципы максимина и минимакcа. > Седловая точка игры. > Цена игры. > Смешанная стратегия. > Основная теорема матричных игр. > Динамическая транспортная задача. > Простейшая динамическая модель макроэкономики. > Простейшая задача оптимального управления. > Дискретный принцип
  7. Содержание
    Стр. 12. Основы сетевого планирования и управления …………….. 4 13. Игры с природой. Критерии для принятия решений ………. 16 14. Элементы теории игр ………………………………………… 21 15. Параметрическое программирование ………………………. 38 16. Основы динамического программирования ………………... 50 17. Контрольные вопросы для подготовки к экзамену ………... 68 18. Контрольная работа по математическому
  8. 15. ПАРАМЕТРИЧЕСКОЕ ПРОГРАММИРОВАНИЕ
    15.1. Экономическая и геометрическая интерпретации задачи ПП. В математических моделях оптимизационных задач, рассмотренных ранее, все заданные коэффициенты были постоянными числами. Однако на практике нередко возникают задачи, при математической постановке которых необходимо учитывать зависимость коэффициентов модели от некоторых параметров. Меняться могут либо коэффициенты целевой функции, либо
  9. ПРЕДИСЛОВИЕ
    Учебное пособие подготовлено в соответствии с программой дисциплины «Экономико-математические методы и прикладные модели», утвержденной Научно-методическим советом Всероссийского заочного финансово-экономического института для специальностей «Финансы и кредит», «Бухгалтерский учет и аудит», «Менеджмент», «Маркетинг», «Государственное и муниципальное управление», «Экономика и социология труда» на
  10. 1.7. ДВОЙСТВЕННЫЙ СИМПЛЕКС-МЕТОД
    1.7.1. Основные идеи двойственного симплекс-метода. Непосредственное приложение теории двойственности к вычислительным алгоритмам линейного программирования позволило разработать еще один метод решения ЗЛП, получивший название двойственного симплекс-метода, или метода последовательного уточнения оценок. Впервые он был предложен Лемке в 1954 г. В процессе изложения идей, положенных в основу
  11. 1.2. ОСНОВНЫЕ СВОЙСТВА ЗЛП И ЕЕ ПЕРВАЯ ГЕОМЕТРИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ
    1.2.1. Основные понятия линейной алгебры и выпуклого анализа, применяемые в теории математического программирования. Кратко напомним некоторые фундаментальные определения и теоремы линейной алгебры и выпуклого анализа, которые широко применяются при решении проблем как линейного, так и нелинейного программирования. Фундаментальным понятием линейной алгебры является линейное (вещественное)
  12. 3.2. Транспортная задача
    Как показано выше, многие прикладные модели в экономике сводятся к задачам линейного программирования. Практически все задачи линейного программирования можно решить, используя ту или иную модификацию симплексного метода. Однако существуют более эффективные вычислительные процедуры решения некоторых типов задач линейного программирования, основанные на специфике ограничений этих задач. Рассмотрим
  13. Библиографический список 16.
    Френкель АЛ. Прогнозирование производительности труда: методы и модели.— М.: Экономика, 1989. 17. Четыркин Е.М. Статистические методы прогнозирования. — М.: Финансы и статистка, 1979. 18. Эконолшко-математические методы и прикладные модели: Учебно-методическое пособие. /В.А. Половников, И.В. Орлова, А.Н. Гармаш, В.В. Федосеев. — М.: Финстатин- форм, 1997. 19. Смирнов К А. Нормирование
  14. 2 Математическая школа как интерпретация теории предельной полезности
    Теория предельной полезности, разработанная "австрийцами", получила свою интерпретацию в работах представителей так называемой математической школы - О.Курно, У.С.Джевонса, Ф.Эджуорта, Л.Валъраса, В.К.Дмитриева, В.Парето, М.И. Туган-Баранов- ского, Л.В.Канторовича, Е.Е.Слуцкого и др. Собственно говоря, математическая школа и сформировалась на базе этой интерпретации. Надо отметить, что речь идет
  15. -Ф- Оптимизация портфеля инвестиций при ограниченном бюджете
    Решая проблему выбора инвестиционных проектов в условиях ограниченного бюджета из примера 2.4, мы использовали индекс рентабельности в качестве ранга с целью отбора вариантов, обеспечивающих максимальную рентабельность вложенных средств. Более эффективный подход к решению подобных проблем заключается в применении методов математического программирования и, в частности, линейной оптимизации.
  16. .Кадровая политика.
    Кадровая политика - это система теоретических взглядов, идей, принципов, определяющих направления работы с персоналом, ее формы и методы(94]. Ее целью является обеспечение оптимального баланса процессов обновления и сохранения численного и качественного состава кадров в его развитии в соответствии с потребностями самой организации и требованиями действующего законодательства. Мы формулируем
  17. 16.5. Задача динамического программирования в терминах теории графов.
      Сформулируем задачу динамического программирования в терминах теории графов. Пусть G=(V,E) – взвешенный орграф с множеством вершин V={s0, s1, …, sп}, в котором пара {si, sk} является дугой, если и только если в ?(si) существует управление Xik (см. разд. «Задача о кратчайшем пути»). Вес дуги (si, sk) равен fik и непременно kgt;i. Обозначим через D+(si) и D-(si) множества дуг орграфа с концом si
  18. 2.2. ДВОЙСТВЕННОСТЬ В НЕЛИНЕЙНОМ ПРОГРАММИРОВАНИИ
    2.2.1. Понятие седловой точки. В настоящем параграфе мы кратко остановимся на некоторых фундаментальных моментах теории нелинейного программирования. Отправной точкой для них является распространение метода Лагранжа для решения ЗНП с ограничениями в форме неравенств: где X — некоторая область в пространстве Rn. По аналогии с п. 2.1.2 определим для задачи (2.28) функцию
Портал "ЭКОНОМИСТЪ" © 2014
info@economuch.com
Рейтинг@Mail.ru