|
Рассмотрим примеры преобразования задач коммерческой деятельности к общей задаче линейного программирования и построения экономико-математических моделей.
Коммерческая деятельность предприятия
Коммерческому отделу поручили проанализировать совместную деятельность подразделений фабрики по изготовлению и продаже двух видов краски для внутренних (В) и наружных (Н) работ, которая поступает в продажу по цене 3 тыс. руб. и 2 тыс. руб. за 1 т. Для производства красок используют два вида сырья А и В, максимально возможные суточные запасы которых составляют 3 т и 4 т. Изучение конъюнктуры спроса на рынке сбыта показало, что суточный спрос на краску для внутренних работ никогда не превышал спроса на краску для наружных работ более чем на 1,5 т, а спрос на краску для внутренних работ никогда не превышал 2 т в сутки. Какое количество краски каждого вида необходимо производить фабрике, чтобы доход от ее реализации был максимальным?
Построение экономико-математической модели задачи
Поскольку в задаче необходимо определить объемы производства для продажи краски, то суточные объемы производства красок для наружных и внутренних работ обозначим хп и хь тонн соответственно.
Критерием, по которому определяется степень достижения поставленной цели, является доход от продажи краски, который должен быть максимально возможным.
Решение любой задачи осуществляется в рамках ограниченных ресурсов. В данном случае необходимо учесть ограничения на расход сырья, запасы которого на фабрике не бесконечны, а также ограничения на спрос краски. Объемы производства и соответственно продажи краски не могут принимать отрицательных значений. В связи с этим необходимо записать условие неотрицательности переменных: Xн 0; XB 0.
Кроме того, известно, что план фабрики предусматривает обязательный выпуск красок указанных видов, производство которых за всю историю не опускалось ниже, чем хн 0,25 т, хв 0,5 т.
Таким образом, в целом экономико-математическую модель задачи можно представить в таком виде.
Полученная модель является задачей линейного программирования, так как все входящие в нее функции линейны.
Решение какой-либо задачи управления можно разбить на несколько этапов:
формулировка задачи;
разработка математической модели изучаемой системы;
выбор метода и отыскание решения с помощью этой модели;
проверка решения.
В каждой задаче мы должны ясно определить цели, поставленные перед системой, изучить обстановку, освоиться с терминологией, процессом, определить различные способы действия, приемлемые для ситуации, дать в какой-то форме постановку задачи. Построить подходящую логическую, или математическую модель, которая свяжет переменные задачи с реальными ограничениями, целями задачи, мерой эффективности. Затем, исходя из полученной модели, выбрать метод, и найти решение, оптимизирующее эту меру эффективности, т. е. оптимальное решение. И сравнить это полученное с помощью математической модели решение с действительностью, чтобы выяснить, в самом ли деле мы сформулировали и решали ту реальную задачу, с которой начали? Когда меняется ситуация, какие изменения надо вносить в математическую модель? Можно ли улучшить модель, что привело бы к новым решениям, более реалистичным и точным.
Итак, математическая модель означает перевод задачи на язык количественных терминов.
В линейном программировании математическая модель представляет собой систему линейных соотношений между переменными (ресурсами, ограничениями) и целевую функцию (меру эффективности).
Математические модели позволяют привнести научную методологию в те области управления, где ранее господствовала интуиция и опыт. Математическая модель позволяет лучше понять исследуемую задачу и процессы, оценить и сравнить между собой решения, оценить эффект, который оказывает изменение одной переменной на остальные, понять численные, количественные характеристики процесса, которые ранее понимались интуитивно-приближенно.
Когда задача ЛП поставлена, главная мера эффективности выбрана, функциональная форма математической модели определена. Нужно указать, как выбранные нами переменные связаны с данными задачи. для этого необходимы некоторые эксперименты, позволяющие выявить структуру. В одних случаях, достаточно открыть бухгалтерскую книгу, заглянуть в нужный файл компьютера и получить необходимую информацию; в других, затратить силы и средства. Но в любом случае между переменными и структурой модели существует связь.
Именно посредством модели задачи связана с предлагаемым решением. Насколько точна модель, настолько и реально решение. С помощью математической модели и меры эффективности можно оценить разные решения и выбрать лучшее. В линейном программировании, благодаря вычислительным методам, эта задача решается автоматически.
Двойственная задача линейного программирования
Каждой задаче линейного программирования можно поставить в соответствие другую задачу линейного программирования. Решая одну из них, автоматически решается и другая задача. Такие задачи называют взаимодвойственными. Покажем по данной задаче, будем называть ее исходной, построить двойственную ей.
Построим ей двойственную задачу по следующим правилам:
Количество переменных в двойственной задаче равно количеству неравенств в исходной.
Матрица коэффициентов двойственной задачи является транспонированной к матрице коэффициентов исходной.
Столбец свободных членов исходной является строкой коэффициентов для целевой функции двойственной. Целевая функция в одной задаче максимизируется, в другой минимизируется.
Условиям неотрицательности переменных исходной задачи соответствуют неравенства ограничения двойственной, направленные в другую сторону. И наоборот, неравенствам-ограничениям в исходной соответствуют условия неотрицательности в двойственной.
Транспонированной называется матрица, у которой строки и столбцы меняются местами. Поэтому коэффициенты при переменных yi в задаче II это, соответственно, коэффициенты i-ого неравенства в задаче I. Неравенства, находящиеся напротив друг друга, называются сопряженными .
Двойственность является фундаментальным понятием в теории линейного программирования. Основные результаты теории двойственности заключены в двух теоремах, называемых теоремами двойственности.
Теорема 1 (первая теорема двойственности)
Если одна из пары двойственных задач I и II разрешима, то разрешима и другая, причем значения целевых функций на оптимальных планах совпадают, F(x*)=G(y*), где х*, у* - оптимальные решения задачи I и II
Теорема 2 (вторая теорема двойственности)
Планы х* и у* оптимальны в задачах I и II тогда и только тогда, когда при подстановке их в систему ограничений задачи I и II соответственно, хотя бы одно из любой пары сопряженных неравенств обращается в равенство.
| 
