К элементам модели линейного программирования относятся. Модель линейного программирования
МОДЕЛИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
- математические модели решения экономических задан, представленные в форме задач линейного программирования. Целевая функция, связи и в такой модели выражены в виде линейных уравнений.
Экономика и право: словарь-справочник. - М.: Вуз и школа . Л. П. Кураков, В. Л. Кураков, А. Л. Кураков . 2004 .
Смотреть что такое "МОДЕЛИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ" в других словарях:
Математические модели решения экономических задач, представленные в форме задач линейного программирования. Целевая функция, связи и ограничения в такой модели выражены в виде линейных соотношений. Райзберг Б.А., Лозовский Л.Ш., Стародубцева Е.Б … Экономический словарь
модели линейного программирования - математические модели решения экономических задач, представленные в форме задач линейного программирования. Целевая функция, связи и ограничения в такой модели выражены в виде линейных соотношений … Словарь экономических терминов
МОДЕЛЬ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ В МЕНЕДЖМЕНТЕ - вид модели, который применяют для определения оптимального способа распределения дефицитных ресурсов при наличии конкурирующих потребностей. Некоторые типичные применения этого метода в управлении производством: планирование ассортимента изделий; … Большой экономический словарь
Модели в экономике используются начиная с 18 в. В «Экономических таблицах» Ф. Кенэ, которые К. Маркс назвал идеей «...бесспорно самой гениальной из всех, какие только выдвинула до сего времени политическая экономия» (Маркс К. и Энгельс Ф., Соч.,… …
I Модели в биологии применяются для моделирования (См. Моделирование) биологических структур, функций и процессов на разных уровнях организации живого: молекулярном, субклеточном, клеточном, органно системном, организменном и популяционно … Большая советская энциклопедия
Модели экономических объектов или процессов, при описании которых используются математические средства. Цели создания Э. м. м. разнообразны: они строятся для анализа тех или иных предпосылок и положений экономической теории, логического… … Большая советская энциклопедия
- (scarcity) Свойство (товаров или производственных факторов), состоящее в том, что при нулевой цене спрос на них (по сравнению с предложением) будет чрезмерно высоким. Это значит, что в условиях равновесия цена дефицитного товара или фактора… … Экономический словарь
Построение, разработка и приложения математич. моделей принятия оптимальных решений. Содержанием теоретич. аспекта И. о. являются анализ и решение математич. задач выбора в заданном множестве допустимых решений Xэлемента, удовлетворяющего тем или … Математическая энциклопедия
- (НИР и ОКР, applied research, research and development R D) – научные исследования, направленные на решение социально практических проблем. Наука (science) сфера человеческой деятельности, функцией которой является выработка и теоретическая… … Википедия
Математическая дисциплина, предметом к рой являются модели экономич. объектов и процессов и методы их исследования. Однако понятия, результаты, методы М. э. удобно и принято излагать в тесной связи с их экономич. происхождением, интерпретацией и… … Математическая энциклопедия
Книги
- Экономико-математические методы и модели в коммерческой деятельности. Учебник , Г. П. Фомин. В учебнике рассмотрены операции, экономические показатели, схема образования прибыли, структура связи экономических и математических методов, методы и модели изучения, анализа и…
- Методы и модели оптимизации управленческих решений. Учебное пособие , А. Р. Урубков, И. В. Федотов. В учебном пособии изложены принципы оптимизации управленческих решений на основе методов и моделей линейного программирования. На примерах реальных бизнес-ситуаций показано, как, используя…
Экстремальные задачи
Напомним, что латинское слово extremum означает "крайнее". Оно в математике имеет два конкретных значения: maximum (сокращенно max ) - наибольшее и minimum (сокращенно min ) - наименьшее. В таком понимании extremum имеет более узкий смысл, чем optimum , переводимый от латинского как "наилучшее".Задача нахождения максимального или минимального значения заданной функции на заданном множестве называется экстремальной задачей .
Имеется два вида экстремальных задач - задача на максимум и задача на минимум. Символически они записываются так:
Функция f(x) называется целевой функцией
, а Х - множеством допустимых решений
. Оптимальным решением
задач называется пара (x*,f(x*)) , где x* - точка максимума (минимума), а f(x*) , - значение функции f в этой точке, то есть ее максимальное (минимальное) значение на множестве Х
.
Решить задачи это значит: либо найти оптимальное решение; либо убедиться, что оптимальное решение не существует.
Решение задачи требует разрешения трех проблем: 1) проблему существования оптимального решения; 2) проблему установления необходимых и достаточных признаков оптимальности (то есть характерных свойств, присущих точкам максимума и минимума); 3) проблему численного вычисления оптимальных решений.
Пример №1 . Построить математическую модель следующей задачи экономической деятельности. Для этого:
- Выявить проблему и сформулировать цель исследования.
- Провести описание переменных экономического процесса или объекта.
- Записать математическую формулировку функции цели.
- Сформулировать ограничения накладываемые условиями задачи и записать систему ограничений.
- Предложить метод решения.
Перед проектировщиками автомобиля поставлена задача сконструировать самый дешевый кузов, используя листовой материал, стекло и пластмассу. Основные характеристики материалов представлены в таблице.
| Характеристики | Материалы | ||
| Металл | Стекло | Пластмасса | |
| Стоимость (тыс. руб./м 2) | 25 | 20 | 40 |
| Масса (кг/м 2) | 10 | 15 | 3 |
Общая поверхность кузова (вместе с дверьми и окнами) должна составлять 14 м 2: из них не менее 3,5 м 2 и не более 5 м 2 следует отвести под стекло. Масса кузова не должна превышать 150 кг, а масса пластмассы не должна превышать 20% от массы кузова. Металлическая составляющая поверхности кузова должна превышать стеклянную поверхность не менее, чем в два раза. Сколько металла, стекла и пластмассы должен использовать наилучший проект.
Проблема заключается в ограниченных ресурсах для получения оптимального результата.
Описание переменных.
x 1 - количество металла, м 2
x 2 - количество стекла, м 2
x 3 - количество пластмассы, м 2
Функция цели.
Ограничения:
- Общая поверхность кузова
x 1 + x 2 + x 3 ≥ 14 - Требования по стеклу
x 2 ≥ 3,5
x 2 ≤ 5 - Ограничения по массе
10x 1 + 15x 2 + 3x 3 ≤ 150 - Требования по массе пластмассы
3x 3 ≤ (10x 1 + 15x 2 + 3x 3)*20% - Ограничения по поверхности
x 1 ≥ 2x 2
Система ограничений.
x 1 + x 2 + x 3 ≥ 14
10x 1 + 15x 2 + 3x 3 ≤ 150
2x 1 + 3x 2 - 2,4x 3 ≥ 0
x 1 - 2x 2 ≥ 0
x 2 ≥ 3,5
x 2 ≤ 5
x 1 , x 2 , x 2 ≥ 0
F(x) = 25x 1 + 20x 2 + 40x 3 → min
Пример №2 . На фабрике производится ткань двух артикулов. Каждая из этих тканей проходит последовательную обработку на станках их трех типов. Ниже указаны: производительность станка каждого типа при изготовлении тканей артикулов 1 и 2; суммарные мощности станочного парка фабрики в расчете на одну рабочую неделю; трудовые затраты по обслуживанию станков в минутах рабочего времени на 1 час работы станка; цена метра ткани каждого артикула. Известно также, что недельный ресурс трудозатрат на обслуживание станков равен 14800 ч.
| Тип станков | Мощность (тыс. ч) | Трудозатраты (мин/ч) | Производительность, м/ч | |
| Артикул 1 | Артикула2 | |||
| 1 | 22 | 10 | 20 | 15 |
| 2 | 40 | 6 | 12 | 6 |
| 3 | 75 | 6 | 6 | 4 |
| Цена 1 м ткани (тыс.руб.) | 18 | 25 | ||
Требуется составить недельный план выпуска тканей с целью максимизации прибыли изготовленной продукции, если 1 час оплачивается в размере 5400 рублей, а 1 час простоя станка 1-го типа составляет 1800 рублей, 2-го типа составляет 2000 рублей, 3-го типа составляет 1400 рублей. Стоимость сырья в расчет не принимать. При решении задачи следует учесть, что выпуск ткани артикула 1 должен не мене чем в 2 раза превышать выпуск ткани артикула 2.
Описание переменных.
x 1 - выпуск тканей артикула 1, м
x 2 - выпуск тканей артикула 2, м
y 1 - время работы 1-го станка, час.
y 2 - время работы 2-го станка, час.
y 3 - время работы 3-го станка, час.
y 1 =x 1 /20 + x 2 /15
y 2 =x 1 /12 + x 2 /6
y 3 =x 1 /6 + x 2 /4
x 1, x 2 , y 1 , y 2 , y 3 ≥ 0
Ограничения:
- по структуре выпуска
x 1 ≥ 2x 2 - по трудозатратам
10/60y 1 + 6/60y 2 +6/60y 3 ≤ 14800
или
1/6y 1 + 1/10y 2 +1/10y 3 ≤ 14800 - по имеющимся мощностям:
y 1 ≤ 22000
y 2 ≤ 40000
y 3 ≤ 75000
Функция цели.
Прибыль = Выручка - Затраты = Цена*Количество - Затраты на простой станков - Трудозатраты
Выручка = 18x 1 + 25x 2
Затраты на простой станков =1,8y 1 + 2y 1 + 1,4y 3
Трудозатраты = 5,4(1/6y 1 + 1/10y 2 +1/10y 3)
F(x) = 18x 1 + 25x 2 - 1,8y 1 - 2y 2 - 1,4y 3 - 5,4(1/6y 1 + 1/10y 2 +1/10y 3)→ max
или
F(x) = 1/50 (900x 1 +1250x 2 -135y 1 -127y 2 -97y 3) → max
С учетом
y 1 =x 1 /20 + x 2 /15
y 2 =x 1 /12 + x 2 /6
y 3 =x 1 /6 + x 2 /4
имеем:
Система ограничений.
x 1 ≥ 2x 2
1/6(x 1 /20 + x 2 /15) + 1/10(x 1 /12 + x 2 /6) +1/10(x 1 /6 + x 2 /4) ≤ 14800
x 1 /20 + x 2 /15≤ 22000
x 1 /12 + x 2 /6 ≤ 40000
x 1 /6 + x 2 /4 ≤ 75000
x 1 ≥ 2x 2
x 1 /30+19x 2 /360 ≤ 14800
x 1 /20 + x 2 /15≤ 22000
x 1 /12 + x 2 /6 ≤ 40000
x 1 /6 + x 2 /4 ≤ 75000
F(x) = 17.33x 1 +23.91x 2 → max
Пример №3
. На предприятии имеется два цеха. В первом цеху работают 50 рабочих, из них 20 имеют 6 разряд и 30 - третий разряд. Во втором цеху, из 100 рабочих 50 имеют 6 разряд и остальные - третий. Требуется выполнить заказ на изготовление 2 типов деталей. На изготовление одной детали первого типа рабочий 6 разряда тратит 10 мин., а рабочий 3 разряда - 15 мин. На изготовление одной детали второго типа рабочий 6 разряда тратит 25 мин., а рабочий третьего - 30 мин.
13) составить план выпуска продукции для каждого из цехов на неделю, исходя из стандартной продолжительности рабочей недели, максимизирующий общий объем выпуска продукции с учетом того, что потребность в детали второго типа в два раза меньше потребности в деталях первого типа.
14) Определить план выпуска продукции для каждого из цехов на неделю, исходя из стандартной продолжительности рабочей недели, максимизируя прибыль, с учетом того, что рабочий 6 разряда получает 300 руб./мес., а рабочий 3 разряда - 200 руб./мес., притом, что цена реализации детали 1 типа равна 20 руб./шт, а второго типа - 34 руб./шт.
Решение.
x 11 - количество деталей 1 типа, изготовленные рабочими 6 разряда за неделю,
x 12 - количество деталей 2 типа, изготовленные рабочими 6 разряда за неделю,
x 21 - количество деталей 1 типа, изготовленные рабочими 3 разряда за неделю,
x 22 - количество деталей 2 типа, изготовленные рабочими 3 разряда за неделю,
13) Целевая функция
20x 11 + 50x 21 + 30x 12 + 50x 22 = max
Ограничения:
2(x 12 +x 22) ≤ x 11 +x 21
14) Целевая функция: Прибыль = Доход - Затраты = Количество деталей * Цена реализации - ЗП работников
Затраты на заработную плату рабочим приведем к недельным, т.е разделим месячный заработок на 4.
F(x) = 20(20x 11 + 50x 21) + 23(30x 12 + 50x 22) - [(20+50)*300 + (30+50)*200]/4 = max
Ограничения:
2(x 12 +x 22) ≤ x 11 +x 21
10/60x 11 + 15/60x 21 + 25/60x 11 + 30/60x 21 ≤ N
N - недельный фонд времени в часах.
Модели линейного программирования применяют для определения оптимального способа распределения дефицитных ресурсов при наличии конкурирующих потребностей. Данный вид модели наиболее распространен на промышленных предприятиях. Он заключается в том, что помогает
максимизировать прибыль при наличии одного нескольких ресурсов, каждый из которых используется для производства нескольких видов товара. Обычно при решении оптимизации данного типа моделей обычно используется Симплекс-метод.
Имитационное моделирование
Имитационное моделирование означает процесс создания модели и ее экспериментальное использование для определения изменений реальной ситуации. Имитация используется в ситуациях, слишком сложных для математических методов типа линейного программирования. Экспериментируя на модели системы, можно установить, как она будет реагировать на определенные изменения или события, в то время, когда отсутствует возможность наблюдать эту систему в реальности.
Экономический анализ один из самых распространенных методов моделирования, хотя он и не воспринимается как моделирование. Экономический анализ вбирает в себя почти все методы оценки издержек и экономических выгод, а также относительной рентабельности деятельности предприятия. Экономический анализ включает в себя анализ безубыточности, определение прибыли на инвестированный капитал, величину чистой прибыли на данный момент времени и т.д. эти модели широко применяются в бухгалтерском и финансовом учете.
При принятии решения вне зависимости от применяемых моделей существуют некоторые правила принятия решений. Правило принятия решения – это критерий, по которому выносится суждение об оптимальности данного конкретного исхода. Существует два типа правил. Один использует численные значения вероятных исходов, второй – использует данные значения.
К первому типу относятся следующие правила принятия решений:Максимаксное решение –это решение,при котором принимается решениепо максимизации максимально возможных доходов. Данный метод очень оптимистичен, то есть не учитывает возможные потери и, следовательно, самый рискованный.
Максиминное решение –это решение,при котором максимизируетсяминимально возможный доход. Данный метод в большей степени учитывает отрицательные моменты различных исходов и является более осторожным подходом к принятию решений.
Минимаксное решение –это решение,при котором минимизируютсямаксимальные потери. Это наиболее осторожный подход к принятию решений и наиболее учитывающий все возможные риски. Под потерями здесь учитываются не только реальные потери, но и упущенные
возможности.
Критерий Гурвича. Данный критерий является компромиссом междумаксиминным и максимаксным решениями и является одним из самых оптимальных.
Ко второму типу принятия решений относятся решения, при которых кроме самих возможных доходов и потерь учитываются вероятности возникновения каждого исхода. К данному типу принятия решений относятся, например, правило максимальной вероятности и правило оптимизации математического ожидания. При данных методах обычно составляется таблица доходов, в которой указываются все возможные варианты доходов и вероятности их наступления. При использовании правила максимальной вероятности соответственно выбирается по одному из правил первого типа один из исходов, имеющий максимальную вероятность.
При использовании правила оптимизации математических ожиданий, высчитываются математические ожидания для доходов или потерь и затем выбирается оптимальный вариант.
Так как значения вероятностей со временем изменяются, при применении правил второго типа обычно используется проверка правил на чувствительность к изменениям вероятностей исходов.
Кроме того, для определения отношения к риску используется понятие полезности. То есть для каждого возможного исхода кроме вероятности рассчитывается полезность данного исхода, которая также учитывается при принятии решений.
Для принятия оптимальных решений применяются следующие методы:
платежная матрица;
дерево решений;
методы прогнозирования.
Платежная матрица –один из методов статистической теории решений,оказывающий помощь руководителю в выборе одного из нескольких вариантов. Особенно полезен в ситуации, когда руководитель должен установить, какая стратегий в наибольшей мере будет способствовать достижению целей. В самом общем виде матрица означает, что платеж зависит от определенных событий, которые фактически совершаются. Если событие или состояние природы не случается на деле, платеж неизменно будет другим.
В целом платежная матрица полезна, когда:
имеется разумно ограниченное число альтернатив или вариантов стратегии для выбора между ними.
То, что может случиться, с полной определенностью не известно. Результаты принятого решения зависят от того, какая именно выбрана альтернатива, и какие события в действительности имеют место.
Кроме того, руководитель должен иметь возможность объективно оценить вероятность релевантных событий и рассчитать ожидаемое значение такой вероятности.
Вероятность прямо влияет на определение ожидаемого значения – основного понятия платежной матрицы. Ожидаемое значение альтернативы или варианта – это сумма возможных значений, умноженных на соответствующие вероятности.
Определив ожидаемое значение каждой альтернативы и расположив результаты в виде матрицы, руководитель без труда может выбрать наиболее оптимальный вариант.
Дерево решений –метод науки управления–схематичное представлениепроблемы принятия решений – используется для выбора наилучшего направления действий из имеющихся вариантов.
Метод дерева решений может применяться как в ситуациях, в которых применяется платежная матрица, так и в более сложных ситуациях, в которых результаты одного решения влияют на последующие решения. То есть дерево решений – удобный метод для принятия последовательных решений.
Методы прогнозирования
Прогнозирование – метод, в котором используется как накопленный в прошлом опыт, так и текущие допущения насчет будущего с целью его определения. Результат качественного прогнозирования может служить основой планирования. Существуют различные разновидности прогнозов: экономические прогнозы, прогнозы развития технологии, прогнозы развития конкуренции, прогнозы на основе опросов и исследований, социальное прогнозирование.
Все типы прогнозов используют различные методы прогнозирования.
Методы прогнозирования включают в себя:
неформальные методы;
количественные методы;
качественные методы.
Неформальные методы включают в себя следующие виды информации:Вербальная информация –это наиболее часто используемая информация дляанализа внешней среды. Сюда относят информацию из радио- и телепередач, от поставщиков, от потребителей, от конкурентов, на различных совещаниях и конференциях, от юристов, бухгалтеров и консультантов. Данная
информация легкодоступна, затрагивает все основные факторы внешнего окружения, представляющие интерес для организации. Однако она очень изменчива и нередко неточна.
Письменная информация –это информация из газет,журналов,
информационных бюллетеней, годовых отчетов. Эта информация обладает
теми же достоинствами и недостатками, что и вербальная информация.
Промышленный шпионаж
Количественные методы прогнозирования используются,когда естьоснования считать, что деятельность в прошлом имела определенную тенденцию, которая может продолжиться и в будущем, и когда достаточно информации для выявления таких тенденций. К количественным методам относятся:
Анализ временных рядов. Он основан на допущении,согласно которомуслучившееся в прошлом дает достаточно хорошее приближение к оценке будущего. Проводится с помощью таблицы или графика. Причинно-следственное (казуальное) моделирование. Наиболеематематически сложный количественный метод прогнозирования. Используется в ситуациях с более чем одной переменной. Казуальное моделирование – прогнозирование путем исследования статистической зависимости между рассматриваемым фактором и другими переменными. Из казуальных прогностических моделей самыми сложными являются эконометрические модели, разработанные с целью прогнозирования динамики экономики.
Качественные методы прогнозирования подразумевает прогнозированиебудущего экспертами. Существует 4 наиболее распространенных метода качественного прогнозирования:
Мнение жюри –соединение и усреднение мнений экспертов в релевантныхсферах. Неформальная разновидность данного метода – «мозговой штурм». Совокупное мнение сбытовиков. Мнение дилеров или предприятий сбыта очень ценно, так как они имеют дело непосредственно с конечными потребителями и знают их потребности.
Модель ожидания потребителя –прогноз,основанный на результатахопроса клиентов организации.
Метод экспертных оценок. Он представляет собой процедуру,позволяющуюгруппу экспертов приходить к согласию. По данному методу эксперты из различных областей заполняют опросник по данной проблеме. Затем им дают опросники, заполненные другими экспертами, и просят пересмотреть свое мнение либо аргументировать первоначальное. Процедура проходит 3-4 раза, пока в результате не будет выработано общее решение. Причем все опросники анонимны, как и анонимны сами эксперты, то есть эксперты не
знают, кто еще входит в группу.
Ситуация с принятием стратегических решений усугубляется тем, что в республике еще нет достаточного количества высококвалифицированного управленческого персонала, то есть менеджеров, подготовленных управлять
и принимать решения в условиях рыночной экономики. Это касается как предприятий и организаций, так и Правительства. Кроме того, постоянно изменяющаяся правовая база не позволяет делать долговременных прогнозов, на основе которых могли бы приниматься стратегические решения.
База для обучения менеджеров только складывается, но из-за общего кризиса
и кризиса системы образования, ВУЗы не в состоянии подготовить достаточно квалифицированных менеджеров. Кроме всего прочего, чтобы быть настоящим менеджером необходимо иметь большой стаж работы. Что касается принятия тактических решений, то с этим ситуация складывается лучше. Тактические решения менее зависят от времени, следовательно, быстро изменяющаяся и не очень предсказуемая ситуация создают меньше препятствий для принятия правильного решения. Однако и здесь не все гладко. Это связано с тем, что из-за недостатка релевантной информации не всегда возможно принимать решения, используя научные методы (моделирование, прогнозирование, и т.д.). Большое количество руководителей вообще незнакомо с научными методами принятия решений, используемыми в науке управления.
Кроме того, в нашей стране отсутствует информационная инфраструктура, которая бы позволила в короткие сроки и с небольшими затратами получить информацию, необходимую для принятия решений. На достаточно низком уровне находится компьютерная грамотность. Недостаточно специализированных организаций по проведению различных исследований. Большим минусом также является несовершенная и постоянно изменяющаяся правовая база, наличие коррупции в структуре управления государством.
Однако не во всех отраслях экономики дела обстоят таким образом. В финансово-банковском секторе, жестко контролируемом НБМ, ситуация с принятием решений, несмотря на кризис, лучше. Это связано с тем, что в банках, наряду с поколением руководителей, получивших образование в период существования административно-командной системы управления, очень много молодых кадров (25-35 лет). Новое поколение, изучавшее менеджмент и результаты его применения в развитых странах, стремится использовать полученные знания. Недостаток опыта у них компенсируется наличием более опытных руководителей. Кроме того, здесь в большей степени используется принцип делегирования полномочий, что также увеличивает оптимальность принимаемых решений. Банки Молдовы
поддерживают связи с банками развитых стран, что позволяет руководителям различных уровней банковского сектора на практике ознакомиться с работой менеджеров в развитых странах.
Процесс принятия решений – процесс психологический. Люди, принимая решения, не всегда принимают логичные решения. Решения варьируются от спонтанных до высокологичных. Поэтому процессы принятия решений делятся на имеющий интуитивный, основанный на суждениях и рациональный характер, хотя решение редко относится к какой либо одной категории.
Интуитивное решение –это решение,принятое только на основе того,чторуководитель имеет ощущение того, что оно правильно. При этом руководитель не рассматривает все возможные варианты, не учитывает все их преимущества и недостатки и не нуждается в понимании ситуации. Решения, основанные на суждениях, часто кажутся интуитивными,так каких логика не очевидна. Такое решение – это выбор, обусловленный знаниями или накопленным опытом. Человек использует знание о том, что случалось в сходных ситуациях раньше для того, чтобы спрогнозировать результат альтернативных решений в существующей ситуации. Такой метод принятия решений обладает как положительными, так и отрицательными сторонами. Положительным является то, что действительно многие ситуации имеют тенденцию к повторению и применение такого метода принятия решений позволяет сэкономить время и деньги, так как решение принимается руководителем очень быстро и без сбора дополнительной информации и ее анализа. Однако такие решения принимаются на базе здравого смысла, который в истинном его понимании встречается очень редко. Кроме того, информация, на основе которой принимается данное решение, может быть искажена потребностями людей и другими факторами. Также суждения не позволяют принимать правильные решения в уникальных или абсолютно новых ситуациях, так как лицо, принимающее решение не обладает необходимым опытом для обоснования выбора. Так как суждение всегда опирается на опыт, оно смещает ориентацию принятия решения в направление, знакомое руководителю по предыдущим ситуациям. Это может привести к тому, что руководитель упустит новые альтернативы.
Решение принимается в условиях определенности, когда руководитель может
с точностью определить результат каждого альтернативного решения, возможного в данной ситуации. Сравнительно мало организационных или персональных решений принимается в условиях определенности. Однако они все-таки имеют место. Кроме того, элементы сложных крупных решений можно рассматривать как определенные. Уровень определенности при принятии решений зависит от внешней среды. Он увеличивается при наличии
твердой правовой базы, ограничивающей количество альтернатив и снижающей уровень риска.
Математическое программирование ("планирование") – это раздел математики, занимающийся разработкой методов отыскания экстремальных значений функции, на аргументы которой наложены ограничения. Идея линейного программирования возникла в 1939г., когда была напечатана брошюра Леонида Витальевича Канторовича "Математические методы организации и планирования производства". Американский математик А. Данциг в 1947 году разработал весьма эффективный конкретный метод численного решения задач линейного программирования (он получил название симплекс метода ).
Дальнейшее изложение материала предполагает, что студенты изучали теорию линейного программирования в курсе математики. В связи с этим рекомендуется совмещать чтение этой главы с просмотром презентаций. Электронные версии презентаций размещены в папке «Линейное программирование». При этом часть материала предназначена для восстановления знаний, полученных в курсе математики, а часть для их расширения и углубления с акцентом на прикладные возможности теоретических моделей.
Теория линейного программирования
Общая постановка задачи
Идея линейного программирования представлена в формате презентаций, электронная версия которых размещена в файле «Идея - линейное программирование».
Геометрическая интерпретация и графический метод решения
Графически способ решения задач линейного программирования целесообразно использовать:
1. Для решения задач с двумя переменными, когда ограничения выражены неравенствами.
2. Решения задач со многими переменными при условии, что в их канонической записи содержится не более двух свободных переменных.
Геометрический метод решения задач линейного программирования представлен в формате презентации - файл «Геометрический метод ЛП»
2.2. Симплекс-метод, общая характеристика, критерий оптимальности допустимого базисного плана
Графический способ решения задачи линейного программирования показывает, что оптимальное решение этой задачи всегда ассоциируется с угловой точкой пространства решений (в математике она также называется крайней точкой множества ). Это является ключевой идеей при разработке общего алгебраического симплекс-метода для решения любой задачи линейного программирования.
Переход от геометрического способа решения задачи линейного программирования к симплекс-методу лежит через алгебраическое описание крайних точек пространства решений. Для реализации этого перехода сначала надо привести задачу линейного программирования к стандартной (канонической) форме:
· преобразовать неравенства ограничений в равенства путем введения дополнительных переменных;
· преобразовать свободные переменные в неотрицательные;
· преобразовать задачу максимизации в задачу минимизации.
Стандартная форма задачи линейного программирования необходима, потому что она позволяет получить базисное решение (используя систему уравнений, порожденную ограничениями). Это (алгебраическое) базисное решение полностью определяет все (геометрические) крайние точки пространства решений. Симплекс-метод позволяет эффективно найти оптимальное решение среди всех базисных.
Восстановить знания по решению задач симплекс-методом можно с помощью презентации «Симплекс метод».
Двойственные задачи
Любая задача линейного программирования имеет двойственную природу. Правило построения двойственной задачи:
Если исходная задача на max, то двойственная на min и наоборот.
В двойственной задаче столько переменных, сколько ограничений в исходной постановке. При этом переменные соответствуют ограничениям и наоборот.
Коэффициентами целевой функции двойственной задачи являются правые части ограничений исходной задачи.
Матрица коэффициентов ограничений двойственной задачи получается транспонированием матрицы коэффициентов ограничений исходной задачи.
Правыми частями ограничений двойственной задачи являются коэффициенты целевой функции исходной.
Ограничениям неравенствам исходной задачи соответствуют неотрицательные переменные двойственной задачи, а ограничениям равенствам – переменные любого знака и наоборот.
Теорема 1: Если исходная задача имеет оптимальный план x*, то двойственная задача также имеет оптимальный план y*, причем значения функций на этих планах равны: f(x*)=g(y*).
Теорема 2: Если исходная и двойственная задачи имеют планы, то они имеют и оптимальные планы, причем f(x*)=g(y*).
Признаки оптимальности для двойственных задач:
Признак 1: Если исходная и двойственная задачи имеют планы X и Y, причем f(X)=g(Y), то эти планы оптимальные.
Определение: Ограничения, расположенные на одной строке в схеме пары двойственных задач, называют сопряженными.
Признак 2: Для того, чтобы планы X и Y исходной и двойственной задач были оптимальны, необходимо и достаточно чтобы на этих планах хотя бы одно из каждой пары сопряженных ограничений являлось равенством.
Второй признак позволяет, зная оптимальный план одной из задач, найти оптимальный план другой задачи.
Основные положения двойственной задачи изложены в презентациях «Теория двойственности» и «Двойственная задача».
Транспортные задачи
Транспортная задача является одной из наиболее распространенных специальных задач линейного программирования. Первая строгая постановка транспортной задачи принадлежит Ф. Хичкоку, а первый точный метод решения разработан Л. В. Канторовичем и М. К. Гавуриным.
Под названием “транспортная задача” объединяется широкий круг задач с единой математической моделью. Данные задачи относятся к задачам линейного программирования и могут быть решены симплексным методом. Однако матрица системы ограничений транспортной задачи настолько своеобразна, что для ее решения разработаны специальные методы. Эти методы, как и симплексный метод, позволяют найти начальное опорное решение, а затем, улучшая его, получить оптимальное решение.
Под термином "транспортные задачи" понимается широкий круг задач не только транспортного характера. Общим для них является, как правило, распределение ресурсов, находящихся у m производителей (поставщиков), по n потребителям этих ресурсов. Различают два типа транспортных задач: по критерию стоимости (план перевозок оптимален, если достигнут минимум затрат на его реализацию) и по критерию времени (план оптимален, если на его реализацию затрачивается минимум времени).
Наиболее часто встречаются следующие задачи, относящиеся к транспортным:
· прикрепление потребителей ресурса к производителям;
· привязка пунктов отправления к пунктам назначения;
· взаимная привязка грузопотоков прямого и обратного направлений;
· отдельные задачи оптимальной загрузки промышленного оборудования;
· оптимальное распределение объемов выпуска промышленной продукции между заводами-изготовителями и др.
Постановки задач транспортного типа, алгоритмы их решения и примеры практического использования представлены в трех презентациях:
1. «Обобщенная транспортная задача (λ-задача)».
2. «Закрытая транспортная задача. Метод потенциалов».
3. «Усложнённые постановки транспортной задачи».
Экономические приложения
Многообразие экономических приложений математического моделирования методами линейного программирования рассмотрим на примерах формулирования конкретных постановок прикладных задач (заимствовано из курса лекций Диязитдиновой А.П.).
Задача 1
Для сохранения нормальной жизнедеятельности человек должен в сутки потреблять белков не менее 120 условных единиц (усл. ед.), жиров – не менее 70 и витаминов – не менее 10 усл. ед. Содержание их в каждой единице продуктов П 1 и П 2 равно соответственно (0,2; 0,075; 0) и (0,1; 0,1; 0,1) усл. ед.
Стоимость 1 ед. продукта П 1 – 2 руб., П 2 –3 руб.
Постройте математическую модель задачи, позволяющую так организовать питание, чтобы его стоимость была минимальной, а организм получил необходимое количество питательных веществ.
Задача 2
Из пункта А в пункт В ежедневно отправляются пассажирские и скорые поезда. Данные об организации перевозок следующие:
Сколько должно быть сформировано скорых и пассажирских поездов, чтобы перевезти наибольшее количество пассажиров?
Задача 3
Четыре овощехранилища каждый день обеспечивают картофелем три магазина. Магазины подали заявки соответственно на 17, 12 и 32 тонны. Овощехранилища имеют соответственно 20, 20 ,15 и 25 тонн. Тарифы (в д.е. за 1 тонну) указаны в следующей таблице:
Задача 4
Имеются два склада готовой продукции: А 1 и А 2 с запасами однородного груза 200 и 300 тонн. Этот груз необходимо доставить трем потребителям В 1 , В 2 и В 3 в количестве 100, 150 и 250 тонн соответственно. Стоимость перевозки 1 тонны груза из склада А 1 потребителям В 1 , В 2 и В 3 равна 5, 3 ,6 д.е., а из склада А 2 тем же потребителям – 3, 4, 2 д.е. соответственно.
Составьте план перевозок, минимизирующий суммарные транспортные расходы.
Задача 5
При откорме каждое животное должно получить не менее 9 ед. белков, 8 ед. углеводов и 11 ед. протеина. Для составления рациона используют два вида корма, представленных в следующей таблице.
Стоимость 1 кг корма первого вида – 4 д.е., второго – 6 д.е.
Составьте дневной рацион питательности, имеющий минимальную стоимость.
Задача 6
Хозяйство располагает следующими ресурсами: площадь – 100 ед., труд – 120 ед., тяга – 80 ед. Хозяйство производит четыре вида продукции: П 1 , П 2 , П 3 и П 4 . Организация производства характеризуется следующей таблицей:
Составьте план выпуска продукции, обеспечивающий хозяйству максимальную прибыль.
Задача 7.
Цех выпускает трансформаторы двух видов. Для изготовления трансформаторов обоих видов используются железо и проволока. Общий запас железа – 3 тонны, проволоки – 18 тонн. На один трансформатор первого вида расходуются 5 кг железа и 3 кг проволоки, а на один трансформатор второго вида расходуются 3 кг железа и 2 кг проволоки. За каждый реализованный трансформатор первого вида завод получает прибыль 3 д.е., второго – 4 д.е.
Составьте план выпуска трансформаторов, обеспечивающий заводу максимальную прибыль.
Задача 8
Совхоз отвел три земельный массива размером 5000, 8000 и 9000 га на посевы ржи, пшеницы, кукурузы. Средняя урожайность в центнерах на 1 га по массивам указана в следующей таблице:
| Посевы | Массивы | ||
| I | II | III | |
| рожь | |||
| пшеница | |||
| кукуруза |
За 1 центнер ржи совхоз получает 2 д.е., за 1 центнер пшеницы – 2,8 д.е., за 1 центнер кукурузы – 1,4 д.е. Сколько гектаров и на каких массивах совхоз должен отвести на каждую культуру, чтобы получить максимальную выручку, если по плану он обязан сдать не менее 1900 тонны ржи, 158 000 тонны пшеницы и 30 000 тонн кукурузы?
Задача 9
Из трех продуктов – I, II, III составляется смесь. В состав смеси должно входить не менее 6 ед. химического вещества А, 8 ед. – вещества В и не менее 12 ед. вещества С. Структура химических веществ приведена в следующей таблице:
| Продукт | Содержание химического вещества в 1 ед. продукции | Стоимость 1 ед. продукции | ||
| А | В | С | ||
| I | ||||
| II | ||||
| III | 1,5 | 2,5 |
Составьте наиболее дешевую смесь.
Задача 10
В школе проводится конкурс на лучшую стенгазету. Одному школьнику дано следующее поручение:
купить акварельной краски по цене 30 д.е. за коробку, цветные карандаши по цене 20 д.е. за коробку, линейки по цене 12 д.е., блокноты по цене 10 д.е.;
красок нужно купить не менее трех коробок, блокнотов – столько, сколько коробок карандашей и красок вместе, линеек не более пяти. На покупки выделяется не менее 300 д.е.
В каком количестве школьник должен купить указанные предметы, чтобы общее число предметов было наименьшим?
Задача 11
Имеются три специализированные мастерские по ремонту двигателей. Их производственные мощности равны соответственно 100, 700, 980 ремонтов в год. В пяти районах, обслуживаемых этими мастерскими, потребность в ремонте равна соответственно 90, 180, 150, 120, 80 двигателей в год. Затраты на перевозу одного двигателя из районов к мастерским следующие:
| Районы | Мастерские | ||
| 4,5 | 3,7 | 8,3 | |
| 2,1 | 4,3 | 2,4 | |
| 7,5 | 7,1 | 4,2 | |
| 5,3 | 1,2 | 6,2 | |
| 4,1 | 6,7 | 3,1 |
Спланируйте количество ремонтов каждой мастерской для каждого из районов, минимизирующее суммарные транспортные расходы.
Задача 12
Нефтеперерабатывающий завод получает четыре полуфабриката: 400 тыс. л алкилата, 250 тыс. л крекинг-бензина, 350 тыс. л бензина прямой перегонки и 100 тыс. л изопентона. В результате смешивания этих четырех компонентов в разных пропорциях образуются три сорта авиационного бензина: бензин А-2:3:5:2, бензин В-3:1:2:1, бензин С-2:2:1:3. Стоимость 1 тыс. л указанных сортов бензина характеризуется числами 120 д.е., 100 д.е., 150 д.е.
Составьте план выпуска разных сортов авиационного бензина из условия получения максимальной стоимости всей продукции.
Задача 13
Для участия в соревнованиях спортклуб должен выставить команду, состоящую из спортсменов I и II разрядов. Соревнования проводятся по Буге, пряжкам в высоту, прыжкам в длину. В беге должны участвовать 5 спортсменов, в прыжках в длину – 8 спортсменов, а в прыжках в высоту – не более 10. количество очков, гарантируемых спортсмену каждого разряда по каждому виду, указано в таблице:
Распределите спортсменов в команды так, чтобы сумма очков команды была наибольшей, если известно, что в команде I разряд имеют только 10 спортсменов.
Задача 14
Звероферма выращивает черно-бурых лисиц и песцов. На звероферме имеется 10 000 клеток. В одной клетке могут быть либо 2 лисицы, либо 1 песец. По плану на ферме должно быть не менее 3000 лис и 6000 песцов. В одни сутки необходимо выдавать каждой лисе корма – 4 ед., а каждому песцу – 5 ед. Ферма ежедневно может иметь не более 200 000 единиц корма. От реализации одной шкурки лисы ферма получает прибыль 10 д.е., а от реализации одной шкурки песца – 5 д.е.
Какое количество лисиц и песцов нужно держать не ферме, чтобы получить наибольшую прибыль?
Задача 15
Имеются два элеватора, в которых сосредоточено соответственно 4200 и 1200 тонн зерна. Зерна необходимо перевезти трем хлебозаводам в количестве 1000, 2000 и 1600 тонн каждому. Расстояние от элеватора до хлебозавода указано в следующей таблице:
Затраты на перевозку 1 тонны продукта на 1 км составляют 25 д.е. Спланируйте перевозки зерна из условия минимизации транспортных расходов.
Задача 16
Из двух сортов бензина образуются две смеси – А и В. Смесь А содержит Бензина 60% 1-го сорта и 40% 2-го сорта; смесь В – 80% 1-го сорта и 20% 2-го сорта. Цена 1 кг смеси А – 10 д.е., а смеси В – 12 д.е.
Составьте план образования смесей, при котором будет получен максимальный доход, если в наличии имеется бензин 50 т 1-госорта и 30 т второго сорта.
Задача 17
Имеются две почвенно-климатические зоны, площади которых соответственно равны 0,8 и 0,6 млн. га. Данные об урожайности зерновых культур приведены в таблице:
Определите размеры посевных площадей озимых и яровых культур, необходимые для достижения максимального выхода продукции в стоимостном выражении.
Задача 18
На заводе выпускают изделия четырех типов. От реализации 1 ед. каждого изделия завод получает прибыль соответственно 2, 1, 3, 5 д.е. На изготовление изделий расходуются ресурсы трех видов: энергия, материалы, труд.
Данные о технологическом процессе приведены в следующей таблице:
Спланируйте производство так, чтобы прибыль от их реализации была наибольшей.
Модели линейного программирования используются: а) при коммерческих воздушных сообщениях для составления графиков полетов и графиков выходов летного состава;
б) для оптимизации составных частей смесей при разработке пищевых рационов;
в) дня оптимизации параметров производственных процессов в промышленности;
г) коммерческими банками при управлении финансовыми балансами;
д) при перспективном планировании производственных мощностей предприятия;
е) для оптимизации портфеля заказов фирм при инвестировании; ж) для оптимизации транспортных потоков.
С точки зрения управления задачи линейного программирования - это задачи оптимального использования ресурсов. В каждом случае планирования производства необходимо иметь в виду, что различные производственные ресурсы (рабочая сила, сырье, материалы, орудия производства) ограничены, известная норма расхода этих ресурсов на различные виды продукции и возможны многочисленные варианты распределения производственных ресурсов. Задача состоит в том, чтобы найти оптимальное распределение производственных ресурсов. При этом критериями могут быть, например, максимум выпуска продукции, максимум прибыли, минимум производственных затрат и тому подобное.
Пример разработки модели линейного программирования для производства двух изделий
Предположим, что химический завод производит два вида товаров - А и Б в количестве, соответственно равной X и У. Менеджер проработали соответствующую информацию, получили данные, сведенные в таблицу 5.9. Его целью является получение максимальной прибыли (Пр). При этом целевая функция имеет вид:
Таблица 5.9. Стоимостные показатели товаров
ФОРМУЛИРОВКИ ОГРАНИЧЕНИЙ
Рабочее время оборудования при производстве товаров характеризуется следующими цифрами:
Рисунок 5.20. Графический решение линейной оптимизационной модели (5.17) - (5.22)
Привлекательность использования резервных переменных (в нашем случае - это продолжительность простоев оборудования) можно продемонстрировать на следующем примере. Предположим, что товара А произведено 9 единиц, а товара Б - 14 единиц. Тогда, на основе уравнения (5.23) получаем, что
Транспортная задача
Стоимость перевозок 1 т груза в гривнах с каждого пункта отправления А1 и А2 в каждый пункт назначения В1, В2 и ВЗ задана в таком виде (цифры условные):
Нужно составить такой план перевозок, при котором общая их стоимость была бы наименьшей.
Обозначим через Х1, Х2 и Х3 количество грузов, которые нужно перевезти из пункта А1, соответственно в пункты В1, В2 и В3, а через Y1, Y2 и Y3 - количество грузов, которые нужно перевезти из пункта А2 в пункты В1, В2 и В3 . Запишем это в таком виде:
Таким образом, математическая формулировка транспортной задачи (по критерию стоимости транспортных перевозок) имеет вид данной системы пяти уравнений первой степени с шестью неизвестными
ГЕОМЕТРИЧЕСКОЕ РЕШЕНИЯ ТРАНСПОРТНОЙ ЗАДАЧИ
Рассмотрим систему (а). Если сложить почленно первые три уравнения и отнять четвертых, то получим пятый уравнения. Это означает, что в системе (а) пятую уравнения лишнее. О таком уравнения говорят, что оно - результат четырех уравнений, а о всей системе говорят, что она линейно зависима. Если исключить пятого уравнения, то четыре уравнения, оставшиеся являются линейно независимыми. Таким образом, получаем четыре линейно независимые уравнения первой степени с шестью неизвестными. В этих уравнениях четыре неизвестные можно выразить через два последние. В этом случае говорят, что система имеет четыре зависимые неизвестные и два свободных неизвестны. Выберем свободными неизвестными Х1 и Х2 и получаем:
Среди решений системы (а ") нужно найти такой, при котором линейная форма F приобретает малейшего значения. Для решения этой задачи возьмем на плоскости прямоугольную систему координат и построим многоугольник abсd возможных решений системы неравенств а "(рисунок 5.21). Запишем целевую функцию в матричном виде:
Рисунок 5.21. Графическое решение транспортной задачи
На рисунке 5.21 целевая функция изображена штриховыми линиями F. Значение функции уменьшается с увеличением абсолютной величины свободного члена в уравнении целевой функции. Смешивая линию целевой функции вправо параллельно самой себе и отдаляя ее при этом от начала координат, видим, что наименьшее значение она имеет в точке пересечения прямых (I) и (III). Это соответствует оптимальному решения: Х1 = 200, Х2 = 200 (точка С). При этом F = 12000. Из уравнений (а ") находим, что Х3 = 0, Y1 = 0, Y2 = 400, К3 = 200 Таким образом, оптимальным планом перевозки грузов такой доставка из пункта А1 по 200 т в В1 и в В2, а из пункта А2 400 т в В2 и 200 т в В3. Стоимость перевозок при этом наименьшее (12000 грн.).
Недостатком графического (ручного) метода решения модели линейного программирования является то, что он пригоден для задач только с двумя или максимум с тремя переменными. Для большего количества переменных нужно использовать так называемый симплекс-метод.