21266

Понятие математической модели

Лекция

Экономическая теория и математическое моделирование

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

Русский

2013-08-02

342.5 KB

24 чел.

ВВЕДЕНИЕ

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

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

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

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

В самых разных областях нашей жизни и деятельности мы постоянно сталкиваемся по сути дела с одним и тем же классом задач. Нам известна полностью или частично ситуация, в которой мы находимся, и множество возможных альтернативных вариантов нашего дальнейшего поведения. Естественно возникает вопрос, какой из вариантов выбрать, а от каких отказаться? Грубо говоря, в решении этого вопроса и заключается проблема управления. Она с равным основанием может относится к поведению отдельного человека, или группы людей, к развитию тех или иных хозяйственных процессов или экономики в целом, к разработке каких-либо операций и т. п. Итак, необходимо остановиться на одном из допустимых вариантов, т. е. отыскать план. Здравый смысл подсказывает нам, что нужно выбрать «наилучший»вариант, который принесет наибольшую выгоду.

Сам по себе вопрос «какой вариант выбрать?» ни на йоту не приближает нас к решению задачи управления, он даже не формулирует ее, поскольку абсолютно неясно, что значит снова «наилучший вариант», «наилучшая выгода».

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

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

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

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

Если сформулированы система ограничений и целевая функция, это значит, что задача управления поставлена. Те задачи, в которых целевая функция связана с переменными линейной зависимостью, и область ограничений задана линейными уравнениями и неравенствами, называются задачами линейного программирования (ЗЛП). Слово «программирование» отнюдь не означает какую-то связь с ЭВМ, языками программирования и т. д. Оно означает, что в результате решения задачи вы получите некоторую программу действий – оптимальный план для достижения «наилучшего» результата.

Говоря об области применения этого научного направления, можно вспомнить слова одного из величайших математиков мира Леонарда Эйлера: «В мире не происходит ничего, в чем бы не был бы виден смысл какого-нибудь максимума или минимума».

Линейное программирование зародилось в нашей стране. В работе выдающегося советского математика и экономиста лауреата Ленинской и Нобелевской премий академика А, В. Канторовича «Математические методы организации  и планирования производства» (1939 г.), впервые была сформулирована задача ЛП, описывающая реальную экономическую ситуацию, и разработан алгоритм ее решения. В США исследование операций зародилось в годы второй мировой войны, прежде всего для решения военных вопросов. Казалось бы, невинные задачи, о составлении смесей орехов, первоначально возникли при планировании военных операций. Позже появились и их мирные приложения, когда выяснилось, что использование линейного программирования способно дать большой экономический эффект для решения разнообразных вопросов. Из американских математиков, внесших вклад в развитие ЛП нужно отметить Дж. Данцига и его книгу «Линейное программирование, его применения и обобщения».

Как же решать задачи линейного программирования?

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

Понятие математической модели

Решение какой-либо задачи управления можно разбить на несколько этапов:

  1.  формулировка задачи;
  2.  разработка математической модели изучаемой системы;
  3.  выбор метода и отыскание решения с помощью этой модели;
  4.  проверка решения.

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

Итак, математическая модель означает перевод задачи на язык количественных терминов.

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

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

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

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

Формулировка основных типов задач ЛП,

построение их математических моделей

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

  1.  транспортные задачи;
  2.  задачи о составлении плана;
  3.  задачи о смеси (о диете).

Рассмотрим примеры конкретных экономических задач каждого типа, подробно остановимся на построении модели к каждой задачи.

Транспортная задача

Задача 1

На двух торговых базах А и В имеется 30 гарнитуров мебели, по 15 на каждой. Всю мебель требуется доставить в два мебельных магазина С и Д, причем в С надо доставить 10 гарнитуров, а в Д – 20 штук. Известно, что доставка одного гарнитура с базы А в магазин С обходится в 1 денежную единицу, в магазин Д – в три денежных единиц. Соответственно с базы В в магазин С и Д: 2 и 5 денежных единиц. Составить план перевозок так, чтобы стоимость всех перевозок так, чтобы стоимость всех перевозок была наименьшей.

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

магазины

базы

С

Д

отправлено

гарнитуров

А

1

3

15

В

2

5

15

получено гарнитуров

10

20

30

30

Составим математическую модель задачи.

Необходимо ввести переменные. В формулировке вопроса говорится, что необходимо составить план перевозок. Обозначим через х12 количество гарнитуров, перевозимых с базы А в магазины С и Д соответственно, а через у12 – количество гарнитуров, перевозимых с базы В в магазины С и Д соответственно. Тогда, количество мебели, вывозимое со склада А, равно (х+ х2), а со склада В: (у+ у2). Потребность магазина С равна 10 гарнитурам, и в него привезли (х+ у1) штук, т. е. х1 + у= 10. Аналогично, для магазина Д, имеем х+ у= 20. Заметим, что потребности магазинов в точности равны количеству гарнитуров, имеющихся на складах, поэтому х1 + у2 = 15, и у1 +у2 = 15. Если бы со складов вы увезли меньше, чем по 15 комплектов, то магазинам не хватило бы мебели для удовлетворения их потребностей.

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

   (1)

Обозначив, через F – транспортные расходы, посчитаем их. на перевозку 1 комплекта мебели из А в С тратится 1 ден. ед. на перевозку x1 комплектов –x1 ден. ед. Аналогично, на перевозку x2 комплектов из А в Д затратится 3x2 ден. ед.; из В в С: 2y1 ден. ед., из В в Д: 5y2 ден. ед.

Итак,

F=1x1+3x2+2y1+5y2min                                    (2)

(мы хотим, чтобы общая стоимость перевозок была минимальной).

Функция F называется целевой функцией.

Сформулируем задачу математически:

На множестве решений системы ограничений (1) найти такое решение, которое обращает в минимум целевую функцию F (2); или, найти оптимальный план (x1, x2, y1, y2), определяемый системой ограничений (1) и целевой функцией (2).

Задача, которую мы рассмотрели может быть представлена в более общем виде, с любым числом поставщиков и потребителей.

В рассмотренной нами задаче наличие груза у поставщиков (15+15) равно общей потребности потребителей (10+20). Такая модель называется закрытой, а соответствующая задача – сбалансированной транспортной задачей.

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

Рассмотрим пример несбалансированной транспортной задачи.

Задача 2

В пунктах А и В расположены кирпичные заводы, а в С и Д карьеры, снабжающие их песком. потребность заводов в песке меньше, чем производительность карьеров. Известно, сколько песка нужно каждому из заводов и сколько добывается в каждом карьере. Также известна стоимость перевозки 1 тонны песка из каждого карьера к заводам (числа на стрелочках). Нужно так спланировать снабжение заводов песком, чтобы затраты на перевозку были наименьшими. Данные задачи на схеме.

Постоим математическую модель задачи.

Введем переменные:

x11 – количество тонн песка перевозимого с карьера С на завод А;

x12 – с карьера С на завод А;

x21 – количество тонн песка в А с карьера Д;

x22 – количество тонн песка с карьера Д на завод В.

На завод А должно быть доставлено 40 тонн с обоих карьеров, значит x11+x21=40,  на завод В должно быть доставлено 50 тонн, значит x12+x22=50. Из карьера С вывезено не более 70 тонн, т. е. x11+x12 ≤70, аналогично x21+x22 ≤30. Имеем систему ограничений:

   (3)

И целевая функция F, выражающая стоимость перевозок имеет вид

F=2x11+6x12+5x21+3x22→min.                                 (4)

Задача о составлении плана

Задача 3

Некоторому заводу требуется составить оптимальный план выпуска двух видов изделий, которые отрабатываются на четырех видах машин. Известные определенные возможности и производительность оборудования; цена изделий, обеспечивающая прибыль заводу составляет 4 тыс. руб. за изделие I вида, 6 тыс. руб. за изделие II вида. Составить план выпуска этих изделий так, чтобы от реализации их завод получил наибольшую прибыль. В таблице указано время, необходимое для обработки каждого из двух видов изделий на оборудовании всех четырех видов.


Изделия

Виды машин

1

2

3

4

I

1

0,5

1

0

II

1

1

0

1

Возможное время работы машин

18

12

12

9

Построим математическую модель.

В задаче необходимо определить план выпуска изделий, обозначим за x – количество изделий I вида, за y – количество изделий II вида. Тогда посчитаем сколько времени затратит 1-ая машина на обработку всех производственных изделий. Она тратит 1 единицу времени на 1 изделие типа I, значит на x штук изделий потратит 1x ед. времени, на обработку y изделий типа II затратится 1y ед. времени. Всего резерв времени работы 1-й машины 18 единиц времени. Значит, x+y ≤18. Аналогичные рассуждения со 2-й машиной, 3-й и 4-й дадут систему ограничений:

   (5)

Общая прибыль будет выражена в целевой функции:

F=4x+6y→max                                                  (6).

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

Задача составления смеси

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

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

Рассмотрим пример.

Задача 4

Для откорма цыплят на птицефабрике в их рацион необходимо включать не менее 33 единиц вещества А, 23 единицы питательного вещества В, 12 единиц С. Для откорма используются 3 вида корма. Данные о содержании питательных веществ в каждом виде корма заданы таблицей. Также известны: стоимость кормов. Необходимо составить наиболее дешевый рацион.

Корма – продукты

Вещества

Стоимость

1 ед. корма

А

В

С

I

4

3

1

20

II

3

2

1

20

III

2

1

2

10

Для понимания задачи можете представить себе, что вещества А, В, С – это жиры, белки, углеводы, а продукты I, II, III – то, чем кормят цыплят, например, пшено, комбикорм, витаминные добавки. Тогда, первая строка таблицы показывает содержание в 1 ед. пшена: 4 единиц белка, 3 ед. жиров, 1 ед. углеводов. Вторая строка содержание белков, жиров, углеводов в 1 ед. II продукта и т. д.

Если постановка задачи ясна, приступим к построению математической модели.

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

Обозначим за x1 – количество кормов типа I в рационе, за x2 – количество кормов типа II, и соответственно x3 – количество корма III в рационе. Тогда, вещества А при употреблении такого рациона, цыплята получат 4x1 – при съедении продуктов типа I, 3x2 – при потреблении II продукта, 2x3 – при потреблении III. Всего вещества А необходимо употребить по условию задачи не менее 33 единиц, следовательно 4x1+3x2+2x3 ≥ 33.

Аналогично рассуждая с веществом В, имеем:

3x1+2x2+1x3 ≥ 23                       и                            x1+x2+2x3 ≥ 12 для С.

Таким образом, получим систему ограничений:

   (7)

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

F=20x1+20x2+10x3 → min,                                               (8)

т. к. 20, 20, 10 – стоимость 1 ед. продуктов I, II, III типов соответственно, а в рационе их содержится x1, x2, x3 единиц

Система ограничений (7), вместе с целевой функцией (8) и составляют математическую модель исходной задачи. Решить ее, значит найти такие (x1, x2, x3), удовлетворяющие системе ограничений и обращающие значение функции F в минимальное.

Графический способ решения задач ЛП

Если в задаче ЛП неизвестных всего два, как к примеру в задаче 3, то ее можно решить графически.

Система ограничений такой задачи состоит из неравенств от двух переменных:

и целевая функция имеет вид F=C1x+C2y, которую необходимо максимизировать.

Определение. Любое решение системы ограничений называется допустимым решением ЗЛП.

Определение. Допустимое решение, в котором целевая функция достигает максимального или минимального значения, называется оптимальным решением.

В силу этих определений задача ЛП может быть сформулирована следующим образом:

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

Заметим, что переменные x, y в ЗЛП принимают, как правило, неотрицательные задачи (x≥0, y≥0), поэтому область расположены в I четверти координатной плоскости.

Рассмотрим линейную функцию F=C1x+C2y и зафиксируем какое-нибудь ее значение F, пусть, к примеру F=0 или C1x+C2y=0, графиком этого уравнения будет прямая, проходящая через начало координат(0;0) (см. рис).

 

При изменении этого фиксированного значения F=d, прямая C1x+C2y=d будет смещаться параллельно и «зачертит» всю плоскость. Пусть D – многоугольник – область решения системы ограничений. При изменении d прямая C1x+C2y=d, при некотором значении d=d1 достигнет многоугольника D, назовем эту точку А – «точкой входа», и затем, пройдя многоугольник, при некотором значении d=d2 будем иметь с ним последнюю общую точку В, назовем В – «точкой выхода».

Очевидно, что своего наименьшего значения целевая функция F=C1x+C2y достигнет в точке «входа» А и наибольшего значения в точке «выхода» В.

Учитывая, что оптимальное значение на множестве допустимых, целевая функция принимает в точке «входа» или «выхода», т. е. в вершинах области решений, можно предложить следующий план решения ЗЛП:

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

Заметим, что вектор (С1, С2) перпендикулярный прямой, показывает направление роста целевой функции.

При графическом решении ЗЛП возможны два случая, которые требуют особого обсуждения.

Случай 1

При перемещении прямой C1x+C2y=d “вход” или “выход” (как на рисунке) произойдет по стороне многоугольника. Это случится, если в многоугольнике есть стороны, параллельные прямой с1х+с2у=d.

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

Случай 2

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

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

 

Рассмотрим подробно на примере решение задачи 3 о составлении плана графически.

Необходимо найти максимальное значение целевой функции F=4x+6ymax, при системе ограничений

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

x+y=18

x

12

9

y

6

9

0,5x+y=12

x

12

18

y

6

3

x=12 –  параллельна оси OY;

y=9 – параллельна оси OX;

x=0 – ось OY;

y=0 – ось OX;

x≥0 – полуплоскость правее оси OY;

y≥0 – полуплоскость выше оси OX;

y≤9 – полуплоскость ниже y=9;

x≤12 – полуплоскость левее x=12;

0,5x+y≤12 – полуплоскость ниже прямой 0,5x+y=12;

x+y≤18 – полуплоскость ниже

прямой x+y=18.

  1.  Пересечением всех этих полуплоскостей является. очевидно, пятиугольник ОАВСД, с вершинами в точках О(0;0), А(0;9), В(6;9), С(12;6), Д(12;0). Этот пятиугольник и образует область допустимых значений задачи.
  2.  Рассмотрим целевую функцию задачи F=4x+6ymax.

x

3

0

y

-2

0

Построим прямую, отвечающую значению функции F=0: 4x+6y=0. Будем двигать эту прямую параллельным образом. Из всего семейства прямых 4x+6y=const последней вершиной, через которую пройдет прямая, при выходе за границу многоугольника, будет вершина С(12;6). Именно в ней F=4x+6y достигнет своего максимального значения.

Значит, при x=12, y=6 функция F достигает своего максимального значения F=4∙12+6∙6=84, равного 84. Точки с координатами (12;6) удовлетворяет всем неравенствам системы ограничений, и в ней значение целевой функции оптимально F*=84 (оптимальное значение будем обозначать «*»).

Задача решена. Итак, необходимо выпустить 12 изделий I вида и 6 изделий II вида, при этом прибыль составит 84 ед.

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

Каноническая форма задач ЛП

В каждой задаче ЛП ищутся значения переменных при условии, чтобы:

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

Одним из универсальных методов ЛП является симплексный метод, который однако можно применять если задача ЛП имеет каноническую форму.

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

Примером такой задачи ЛП в канонической форме является задача 1 – сбалансированная транспортная задача с системой ограничений (1) и целевой функцией (2).

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

Утверждение. Любая общая задача ЛП может быть приведена к канонической форме.

Приведение любой общей задачи ЛП к канонической форме достигается путем введения новых (или их называют дополнительными) переменных. Вернемся к задаче 3. Система ограничений (3) этой задачи состоит из четырех неравенств. Введя дополнительные переменные y1≥0, y2≥0, y3≥0, y4≥0, можно перейти к системе ограничений:

                                         (9)

Эти дополнительные переменные yi имеют абсолютно ясный экономический смысл, а именно означают величину неиспользованного времени работы (простоя машины i-го вида).

Например, если бы машины первого вида работали все 18 ч., то x+y=18, следовательно y1=0. Но мы допускаем возможность неполного использования времени работы 1-й машины x+y<18. В этом случае y1 приобретает положительное значение и может рассматриваться как неиспользованный лимит времени. Например, зная решение этой задачи из результатов темы 4.2, x=12, y=6, мы можем из системы ограничений (9) сделать вывод, что y1=y2=y3=0, а y4=12-6=6. Т. е. машины 1-го , 2-го, 3-го вида используют свое рабочее время полностью. А вот 4-я машина загружена лишь наполовину, 6 часов, при заданном оптимальном плане, простаивает. Возможно после таких выводов руководителю предприятия захочется загрузить ее другой работой, сдать в аренду на это время и т. д.

Итак, введением дополнительных переменных мы можем любое ограничение типа неравенства привести к уравнению.

Рассмотрим задачу о смеси (задача 4). Система ограничений (7) имела вид:

Неравенства были обращены в сторону «больше», поэтому вводя дополнительные переменные y1, y2, y3≥0 их необходимо отнять от левой части, чтобы уравнять ее с правой. Получим систему ограничений в канонической форме:

Переменные yi также будут иметь экономический смысл. Если вы вспомните практическое содержание задачи, то переменная y1 будет означать количество излишнего вещества А в смеси, y2 – количество излишков вещества В в смеси, y3 – излишки С в смеси.

Задача нахождения максимального значения целевой функции может быть сведена к нахождению минимума для функции –F. Ввиду очевидности утверждения max F=-min (-F). Посмотрите на рисунок , если в какой-то точке x=x0 функция y=F(x) достигает своего максимума, то функция y=-F(x), симметричная ей относительно оси OX, в этой же точке x0 достигнет минимума, причем ymax=-ymin при x=x0.

Вывод: Для представления задачи ЛП в канонической форме необходимо:

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

Аналитическое введение в симплекс-метод

Симплекный метод имеет широчайшее применение в связи с развитием ЭВМ и является универсальным методом линейного программирования. его алгоритм состоит из ряда шагов, четко определенных действий, следуя которым вы приходите к решению задачи ЛП. В этой теме нас будет интересовать идея этого метода, которая при общем взгляде на алгоритм, или на «замурованную» программу в ЭВМ не столь ясна, как если бы рассмотреть ее на конкретном примере.

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

Например, пусть есть система

Здесь число уравнений равно 2, а неизвестных 3, уравнений меньше. Выразим x1 и x2 через x3:

Это общее решение системы, если переменной x3 придавать любые, произвольные числовые значения, то будем находить частные решения системы. Например, x3=1 x1=1 x2=6. Имеем (1, 6, 1) – частное решение. Пусть x3=2 x1=-3, x2=1, (-3, 1, 2) – другое частное решение. Таких частных решений бесконечно много.

Переменные x1 и x2 называются базисными, а переменная x3  не базисная, свободная.

Совокупность переменных x1 и x2 образуют базис: Б(x1,x2). Если x3=0 равно нулю, то полученное частное решение (5,11,0) называется базисным решением соответствующим базису Б(x1,x2).

Базисным называется решение, соответствующее нулевым значениям свободных переменных.

В качестве базисных можно было взять и другие переменные (x1, x3)  или (x2, x3).

Как переходить от одного базиса Б(x1,x2) к другому базису Б(x1, x3)?

Для этого надо переменную x3 перевести в базисные, а x2 – в небазисные. Т. е. в уравнениях надо x3 выразить через x2 , и подставить в 1-е:

Базисное решение, соответствующее базису Б(x1, x3) таково: (-19/5;0;11/5).

Если теперь от базиса Б(x1, x3) нам захочется перейти к базису Б(x2, x3), то

Базисное решение , соответствующее базису Б(x2, x3): (0;19/4;7/8).

Из трех найденных базисных решений, решение соответствующее  базису Б(x1, x3) – отрицательное x10, нас в ЗЛП интересуют только неотрицательные решения.

Если задача ЛП имеет решение. то оно достигается на множестве базисных неотрицательных решений системы ограничений канонической формы.

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

Пример 4.

Решить задачу ЛП.

Функцию F= x2-x1min необходимо минимизировать, при заданной системе ограничений:

-2x1+x2+x3 =2

x1+x2+x5 =5

x1-2x2+x4 =12

xi≥0, i=1,5

Эти ограничения могут рассматриваться как произошедшие из неравенств, а переменные x3, x5, x4 как дополнительные.

  1.  Запишем ограничения, выбрав базис из переменных Б{ x3, , x4, x5}:

Этому базису соответствует базисное неотрицательное решение

x1=0, x2=0, x3=2, x4=2, x5=5 или (0,0,2,2,5).

Теперь нужно выразить F через небазисные переменные, в нашем случае это уже сделано: F= x2-x1.

  1.  Проверим достигла ли функция F своего минимального значения. Для этого базисного решения, F=0-0=0 – значение функции равно 0. Но его можно уменьшить, если x1 будет возрастать, т. к. коэффициент в функции при x1 отрицателен. Однако, при увеличении x1 значения переменных x4, x5 уменьшается (смотрите 2-е и 3-е равенство системы ограничений). Переменная x1 не может быть увеличена больше, чем до 2, иначе x4 станет отрицательной (ввиду равенства 2), и не больше, чем до 5, иначе x5 – отрицателен. Итак, из анализа равенств следует, что переменную x1 можно увеличить до 2, при этом значение функции уменьшится.

Перейдем к новому базису Б2, введя переменную x1 в базис вместо x4.

  1.  Б2{x1, x3, x5}

Выразим эти базисные переменные через небазисные. Для этого сначала выразим x1 из 2-го уравнения, и подставим в остальные, в том числе и в функцию.

Имеем:

F=-2- x2+ x4

Базисное решение, соответствующее базису Б2{x1, x3, x5} имеет вид (2,0,6,0,3) и функция принимает значение F=-2 в этом базисе.

  1.  Значение функции можно и дальше уменьшать, увеличивая x2. Однако, глядя на систему, x2 можно увеличивать лишь до 1, т. к. иначе из последнего равенства x5=3–3x2+x4 следует, что при x21 x5 станет отрицателен. А у нас все переменные в ЗЛП предполагаются неотрицательны. Остальные уравнения системы не дают ограничений на x2. Поэтому  увеличим x2 до 1, введя его в базис вместо x5.

Б3{x1, x2, x3}

Выразим x2 через x5 и  подставим во все уравнения:

Базисное решение, соответствующее базису Б31, х2, х3} выписывается (4,1,9,0,0), и функция принимает значение F=-3. Заметим, что значение F уменьшилось, т. е. улучшилось по сравнению с предыдущим базисом.

  1.  Посмотрев на вид целевой функции , заметим, что улучшить, т. е. уменьшить значение F нельзя, только при x4=0, x5=0,  значение F=-3,  как только x4, x5 станут  положительными, значение F только увеличится, т. к. коэффициенты при x4, x5 положительны. Значит, функция F достигла своего оптимального значения F*=-3. Итак, наименьшее значение F, равное –3, достигается при x1*=4, x2*=1, x3*=9, x4*=0, x5*=0

Пример завершен.

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

EMBED CorelDraw.Graphic.7  


 

А также другие работы, которые могут Вас заинтересовать

70855. Измерение параметров гармонического напряжения с помощью осциллографа 361 KB
  Получение навыков измерения параметров гармонического напряжения с помощью осциллографа. Приобретение сведений о характеристиках и устройстве электронного осциллографа. Ознакомьтесь с принципом работы устройством и характеристиками универсального электронного осциллографа.
70859. Этика отношений преподавателя и студента 98.5 KB
  Этические кодексы поведения запрещает преподавателю узурпировать свою власть над студентом особенно в форме эксплуатации или насилия в различных видах: сексуальном расовом религиозном интеллектуальном принуждать студентов делать то что не является предметом изучения его дисциплины.
70860. Обучение студентов и школьников навыкам изучения правовых наук 104.5 KB
  Творческие работы как элемент мотивации студентов к изучению правовых наук. Обучение студентов и школьников работе с текстом книгой Учебный текст как модель представления научных знаний это обобщенное содержание учебного процесса. Студентов следует учить как работать с текстом.
70861. Основные требования к преподавателю общественных дисциплин 89 KB
  Педагоги используют различные способы мотивирования студентов к учебе. Первый использует собственный авторитет свою личность для того чтобы привлечь студентов а затем пытается перенести интерес студентов от себя к предмету.
70862. Дискуссия как эффективный метод проведения семинарского занятия по правоведческим наукам 120 KB
  Дискуссии и диалоги их преимущества и недостатки. Роль преподавателя в проведении дискуссии. Приемы и методы проведения дискуссии. Дискуссии и диалоги их преимущества и недостатки.
70863. Демократический идеал и методика преподавания общественно- правовых дисциплин 57 KB
  По содержанию гуманитарное образование можно определить как учебно-воспитательный процесс преподавания и усвоения широкого круга гуманитарных дисциплин исторических философских политологических социологических экономических культурологических филологических...