Математические методы. 9

ВВЕДЕНИЕ

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

Целочисленное программирование возникло в 50-60-е годы нашего века из нужд практики - главным образом в работах американских математиков Дж.Данцига и Р.Гомори. Первоначально целочисленное программирование развивалось независимо от геометрии чисел на основе теории и методов математической оптимизации, прежде всего линейного программирования. Однако в последние время исследования в этом направлении все чаще проводятся средствами математики целых чисел.

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

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

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

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

Таковы, например, задачи об оптимизации комплекса средств доставки грузов, о нахождении минимального порожнего пробега автомобилей при выполнении заданного плана перевозок, об определении оптимального машинного парка и его оптимального распределения по указанным работам при условии минимизации суммарной стоимости (машинного парка и производимых работ), о нахождении минимального количества судов для осуществления данного графика перевозок и т. п.

Другим важным толчком к построению теории целочисленного программирования стал новый подход к некоторым экстремальным комбинаторным задачам. В них требуется найти экстремум целочисленной линейной функции, заданной на конечном множестве элементов. Такие задачи принято называть задачами с альтернативными переменными. В качестве примеров можно назвать задачи коммивояжера (бродячего торговца), об оптимальном назначении, теории расписания, или календарного планирования, и задачи с дополнительными логическими условиями (например, типа «или – или», «если – то» и т. п.).

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

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

1 ПОСТАНОВКА ЗАДАЧИ

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

Компания по производству игрушек изготавливает две различные игрушки А и В. Каждая игрушка должна производиться тремя машинами: 1,2 и 3. Эти машины могут обрабатывать только одну игрушку в каждый момент времени. Изготовление одной единицы А требует 40 мин. – 1 машины, 20 мин. – 2 машины, 10 мин. – 3 машины. Для изготовления одной единицы В необходимо 20 мин. – 1 машины, 30 мин. – 2 машины, 30 мин. – 3 машины. Каждая машина может работать 40 часов в неделю. Игрушка А приносит 4 рубля прибыли на единицу, а В – 3 рубля. Полагают, что спрос на эти игрушки превышает предложение компании. Сколько каждого вида игрушек должна делать компания каждую неделю, чтобы максимизировать прибыль?

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

Приведём экономическую задачу в математическую форму, для этого введём следующие переменные:

х1 – игрушка А;

х2 – игрушка В;

Переведем часы в минуты : 40 часов в неделю=2400 минут в неделю.

Математический вид:

F(х)=4 х1+ 3х2 →max

при ограничениях

40x1 + 20x2≤2400

20x1 + 30x2≤2400

10x1 + 30x2≤2400

Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).

В 1-м неравенстве смысла (≤) вводим базисную переменную x3. В 2-м неравенстве смысла (≤) вводим базисную переменную x4. В 3-м неравенстве смысла (≤) вводим базисную переменную x5. 

40x1 + 20x2 + 1x3 + 0x4 + 0x5 = 2400

20x1 + 30x2 + 0x3 + 1x4 + 0x5 = 2400

10x1 + 30x2 + 0x3 + 0x4 + 1x5 = 2400

2 МЕТОД ОПТИМИЗАЦИИ

Оптимизация - целенаправленная деятельность, заключающаяся в получении наилучших результатов при соответствующих условиях.

Постановка задачи оптимизации предполагает существование конкурирующих свойств процесса, например:

• количество продукции - расход сырья
• количество продукции - качество продукции

Для постановки задачи оптимизации необходимо:

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

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

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

4. Учет ограничений.

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

2.1 Характеристика линейного  программирования

Термин "программирование" в названии дисциплины ничего общего с термином "программирование (т.е. составление программ) для ЭВМ" не имеет, так как дисциплина "линейное программирование" возникла еще до того времени, когда ЭВМ стали широко применяться при решении математических, инженерных, экономических и др. задач. Термин "линейное программирование" возник в результате неточного перевода английского "linear programming". Одно из значений слова "programming" - составление планов, планирование. Следовательно, правильным переводом "linear programming" было бы не "линейное программирование", а "линейное планирование", что более точно отражает содержание дисциплины. Однако, термин линейное программирование, нелинейное программирование и т.д. в нашей литературе стали общепринятыми.

Итак, линейное программирование возникло после Второй Мировой Войны и стал быстро развиваться, привлекая внимание математиков, экономистов и инженеров благодаря возможности широкого практического применения, а так же математической "стройности".

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

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

Так, по оценкам американских экспертов, около 75% от общего числа применяемых оптимизационных методов приходится на линейное программирование. Около четверти машинного времени, затраченного в последние годы на проведение научных исследований, было отведено решению задач линейного программирования и их многочисленных модификаций.

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

Значительное развитие теория и алгоритмический аппарат линейного программирования получили с изобретением и распространением ЭВМ и формулировкой американским математиком Дж. Дансингом симплекс-метода.

В развитие и совершенствование этих систем вложен труд и талант многих математиков, аккумулирован опыт решения тысяч задач. Владение аппаратом линейного программирования необходимо каждому специалисту в области математического программирования. Линейное программирование тесно связано с другими методами математического программирования (например, нелинейного программирования, где целевая функция нелинейная).

Задачи с нелинейной целевой функцией и линейными ограничениями называют задачами нелинейного программирования с линейными ограничениями. Оптимизационные задачи такого рода можно классифицировать на основе структурных особенностей нелинейных целевых функций. Если целевая функция Е - квадратичная функция, то мы имеем дело с задачей квадратичного программирования; если Е - это отношение линейных функций, то соответствующая задача носит название задачи дробно-линейного программирования, и т.д. Деление оптимизационных задач на эти классы представляет значительный интерес, поскольку специфические особенности тех или иных задач играют важную роль при разработке методов их решения.

2.2 Характеристика целочисленного  программирования

Под задачей целочисленного программирования (ЦП) понимается задача, в которой все или некоторые переменные должны принимать целые значения. В том случае, когда ограничения и целевая функция задачи представляют собой линейные зависимости, задачу называют целочисленной задачей линейного программирования. В противном случае, когда хотя бы одна зависимость будет нелинейной, это будет целочисленной задачей нелинейного программирования.

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

• задачи оптимизации раскроя;
• оптимальное проектирование лесных машин и оборудования;
• оптимизации системы сервиса и технического обслуживания машинно-тракторного парка;
• и т.д.

Как уже отмечалось, часто задачу ЦП решают без учета условий целочисленности переменных, а затем округляют полученное решение с избытком или недостатком. Это не гарантирует получение оптимального целочисленного решения задачи. Поэтому для нахождения оптимального решения целочисленных задач применяют специальные методы, в которых учитывается, что число возможных решений любой целочисленной задачи является конечным. Следовательно, можно рассмотреть все возможные сочетания целочисленных переменных и проверить, удовлетворяют ли они ограничениям, и из числа удовлетворяющих ограничениям, выбрать наилучшее с точки зрения целевой функции. Такой метод называют методом полного перебора. Его трудоемкость с ростом числа переменных и расширением области граничных условий значительно возрастает. Поэтому для реальных задач он неприменим.

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

2.3 Понятие симплекс-метода

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

Пусть стоит задача максимизации (минимизации)

при условиях

где Aj (j=1,...,n) , B - m-мерные векторы. 
Напомним несколько ключевых определений и свойств задачи.

Вектор X=(X1,X2,..,Xn) , удовлетворяющий условиям (1.2) и (1.3), называется планом. Множество планов в геометрической интерпретации представляет собой выпуклый многогранник.

План, который обращает в равенство хотя бы n независимых ограничений задачи, называется опорным планом. Опорный план соответствует некоторой вершине многогранника планов.

Опорный план содержит не свыше m положительных компонент (m - число независимых ограничений задачи). Опорный план, содержащий менее m положительных компонент, называют вырожденным.

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

Система m векторов Aj при положительных компонентах опорного плана называется базисом этого плана. Симплекс- метод - это метод упорядоченного перебора опорных планов. Упорядоченность в данном случае обеспечивается последовательным перебором опорных планов с монотонным изменением значения целевой функции в сторону возрастания (убывания).

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

Предположим, что исходная задача приведена к канонической форме (1.1)-(1.3) при В 0 и первые m векторов начального базиса образуют единичную матрицу (их можно принять за базис).

Для единообразия описания вычислительной процедуры в дальнейшем будем пользоваться т. н. симплексными таблицами вида:

В первом столбце таблицы (С баз) записывают коэффициенты целевой функции (С1, С2 …Сm) при базисных переменных (напомним, что в базис входят только векторы, образующую единичную подматрицу, как в нашем случае А1 / Аm). Во втором столбце (Базис плана) должны находиться базисные векторы данного опорного плана, а в третьем столбце (План Х) - правая часть ограничений задачи (базисные компоненты плана). Таким образом, перемножая элементы первого столбца таблицы со столбцом - "План Х", и суммируя эти произведения, мы получаем значение целевой функции (ячейка - L(X)=С1*В1 + С2*В2+…+ +Сm*Bm).

Первая строка симплексной таблицы содержит коэффициенты линейной функции нашей задачи и остается неизменной на протяжении всего решения (С1, С2, …, Сn).

В центральной части таблицы записывают коэффициенты при неизвестных в ограничениях исходной задачи (Z11,…, Z1n,…, Zm1,…, Zmn). При этом следует заметить, что коэффициенты при базисных переменных в ограничениях задачи составляют единичную подматрицу. 
Строку Zk рассчитывают по формуле 

Известно, что при переходе к новому опорному плану X(Θ), в котором k-я компонента равна Θ>0 (станет базисной), значение целевой функции изменится и будет равно 
 

Выводы относительно данного опорного плана делают на основании содержимого последней строки таблицы по следующим критериям.  
Критерий 1 (критерий оптимальности). Если все Δk >= 0 , то выбранный план для задачи максимизации является оптимальным (для задачи на минимум признак оптимальности - неположительность всех Δk ).

Критерий 2 . Если обнаруживается некоторое Δk < 0 (для задачи минимизации Δk>0) и хотя бы одно из значений Zjk >0, то переход к новому опорному плану увеличит (уменьшит) значение целевой функции. При этом в базис будет вводиться новый вектор, выбор которого определяется по критерию максимального по модулю произведения Θ*Δk. Ес-ли к тому же учесть, что число положительных (базисных) компонент опорного плана должно оставаться равным m, то одну из m базисных компонент исходного плана обращаем в нуль выбором 

 
где Xjo- компоненты опорного плана; 
Zjk- коэффициенты при k-й переменной в ограничениях задачи.

Критерий 3 . Если обнаруживается некоторое Δk < 0, но все Zjk<=0, то линейная форма задачи не ограничена по максимуму (неограничен-ность по минимуму устанавливается аналогично при Δk>0 и всех Zjk <=0).

Переход к очередной симплексной таблице сводится к тому, чтобы выразить Xk из уравнения, соответствующего минимуму для Θ, и исключить из остальных уравнений (в итоге получаем единичный вектор при новой базисной компоненте и тем самым сохраняется единичная подматрица при базисных векторах):

1. Строку, соответствующую  вектору, выводимому из базиса (главная  строка), делим на коэффициент (главный  элемент), находящийся на пересечении этой строки и столбца, соответствующего вектору, вводимому в базис (главный столбец).

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

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

2.3.1 Каноническая форма  решения задач 

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

 Правило приведения задачи линейного программирования к каноническому виду состоит в следующем:

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

если в ограничениях правая часть отрицательна, то следует умножить это ограничение на -1;

если среди ограничений имеются неравенства, то путем введения дополнительных неотрицательных переменных они преобразуются в равенства;

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

2.4 Алгоритм метода оптимизации

Оптимизация - целенаправленная деятельность, заключающаяся в получении наилучших результатов при соответствующих условиях.

Поиски оптимальных решений привели к созданию специальных математических методов и уже в 18 веке были заложены математические основы оптимизации (вариационное исчисление, численные методы и др.). Однако до второй половины 20 века методы оптимизации во многих областях науки и техники применялись очень редко, поскольку практическое использование математических методов оптимизации требовало огромной вычислительной работы, которую без ЭВМ реализовать было крайне трудно, а в ряде случаев - невозможно.

Постановка задачи оптимизации предполагает существование конкурирующих свойств процесса, например:

• количество продукции - расход сырья
• количество продукции - качество продукции

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

Критерием оптимальности называется количественная оценка оптимизируемого качества объекта.

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

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

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

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

Задачами линейного программирования называются задачи, в которых линейны как целевая функция, так и ограничения в виде равенств и неравенств.

Линейное программирование представляет собой наиболее часто используемый метод оптимизации. К числу задач линейного программирования можно отнести задачи:

рационального использования сырья и материалов; задачи оптимизации раскроя;

оптимизации производственной программы предприятий;

оптимального размещения и концентрации производства;

составления оптимального плана перевозок, работы транспорта;

управления производственными запасами;

и многие другие, принадлежащие сфере оптимального планирования. 
3 РЕШЕНИЕ ЗАДАЧИ

Строим симплексную таблицу используя каноническую форму задачи

Таблица 1. Шаг I

1. Проверка критерия  оптимальности.

Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.

2. Определение  новой базисной переменной.

В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент по модулю.

3. Определение  новой свободной переменной.

Вычислим значения Di по строкам как частное от деления: bi / ai1

и из них выберем наименьшее:

min (2400 : 40 , 2400 : 20 , 2400 : 10 ) = 60

Следовательно, 1-ая строка является ведущей.

Разрешающий элемент равен (40) и находится на пересечении ведущего столбца и ведущей строки.

4. Пересчет симплекс-таблицы.

Формируем следующую часть симплексной таблицы.

Вместо переменной x3 в план 1 войдет переменная x1.

Строка, соответствующая переменной x1 в плане 1, получена в результате деления всех элементов строки x3 плана 0 на разрешающий элемент РЭ=40

На месте разрешающего элемента в плане 1 получаем 1.

В остальных клетках столбца x1 плана 1 записываем нули.

Таким образом, в новом плане 1 заполнены строка x1 и столбец x1.

Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника.

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

НЭ = СЭ - (А*В)/РЭ

СТЭ - элемент старого плана, РЭ - разрешающий элемент (40), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.

Получаем симплекс таблицу:

Таблица 2. Шаг II

1. Проверка критерия  оптимальности.

Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.

2. Определение  новой базисной переменной.

В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент по модулю.