Всё для Учёбы — студенческий файлообменник
1 монета
doc

Студенческий документ № 009287 из РГТЭУ (РИ)

ФЕДЕРАЛЬНОЕ АГЕНСТВО ПО ОБРАЗОВАНИЮ

РОСТОВСКИЙ ИНСТИТУТ (ФИЛИАЛ)

государственного образовательного учреждения высшего

профессионального образования

"РОССИЙСКИЙ ГОСУДАРСТВЕННЫЙ ТОРГОВО-ЭКОНОМИЧЕСКИЙ УНИВЕРСИТЕТ"

Кафедра высшей математики

Методические указания и варианты

контрольной работы №1

по математике

для студентов 2 курса заочного отделения экономических

специальностей

Ростов-на-Дону

2009 УДК 336:519

ББК 65.26

Печатается по решению кафедры высшей математики РИФ РГТЭУ, протокол №1 от 30 августа 2009

Методические указания и варианты контрольной работы № 1 для студентов заочного отделения.- Ростов-на-Дону: ИПО ПИ ЮФУ, 2009 - 34 стр.

I. Общие методические указания

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

Курс изучается по программе 'Прикладная математика", утвержденной в 2007 г.

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

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

II. Литература

1. Красс М.С., Чупрынов Б.П.. Математика в экономике. Математические методы и модели. М. "Финансы и статистика", 2007

2. Федосеев В.В., Гармаш А.Н. и др. Экономико-математические методы и прикладные модели. М.: ЮНИТИ, 2002.

3. Фомин Г.П. Математические методы и модели в коммерческой деятельности : Учебник. М.Финансы и статистика, 2005

4. Кундышева Е.С. Математическое моделирование в экономике. Учебное пособие, М.: Издательско-торговая корпорация "Дашков и К", 2004.

5. Стрикалов А.И., Печенежская И.А. Экономико-математические методы и модели. Пособие к решению задач. Ростов-на-Дону, Феникс, 2008.

ЗАДАЧА № 1

Для задачи линейного программирования на плоскости построить область допустимых решений и найти экстремальные (max и min) значения линейной функции в этой области, если условие её записано в виде:

Ограничения - неравенства

и условия:

Данные к задаче выбирают из таблицы №1 по первым буквам фамилии, имени и отчества.

Таблица №1

Первая буква Фамилия Имя Отчество a11 a12 a21 a22 a31 a32 a41 a42 b1 b2 b3 c0 c1 c2 А 1 2 3 4 5 2 3 4 10 11 12 5 6 7 Б 4 1 2 3 4 5 2 3 13 14 15 8 9 10 В 3 4 1 2 3 4 5 2 16 17 18 11 12 13 Г 2 3 4 1 2 3 4 5 19 20 21 13 5 6 Д 5 2 3 4 1 2 3 4 21 10 11 7 8 9 Е 4 5 2 3 4 1 2 3 12 13 14 10 11 12 Ж 3 4 5 2 3 4 1 2 15 16 17 4 6 5 З 2 3 4 5 1 3 5 1 18 19 20 8 7 9 И 2 1 3 4 5 1 3 5 21 12 11 11 10 12 К 5 2 1 3 4 5 1 3 10 1 14 4 11 5 Л 1 3 2 1 3 4 5 5 15 16 17 6 7 8 М 1 3 5 2 1 3 4 5 11 10 12 9 10 11 Н 5 1 3 5 2 1 3 4 12 10 11 12 4 5 О 4 5 1 3 5 2 1 3 12 16 17 6 7 9 П 3 4 5 2 3 4 2 1 13 15 14 10 12 4 Р 1 3 4 5 2 3 4 2 11 12 10 6 8 7 С 3 1 2 4 5 2 3 4 11 13 14 8 10 9 Т 4 3 1 2 4 5 2 3 17 16 15 11 12 10 Первая буква Фамилия Имя Отчество a11 a12 a21 a22 a31 a32 a41 a42 b1 b2 b3 c0 c1 c2 У 3 4 3 1 2 4 5 2 14 15 16 6 9 7 Ф 2 3 4 3 1 2 4 5 18 10 11 7 9 8 Х 5 2 3 4 3 1 2 4 19 11 10 5 7 6 Ц 4 5 1 2 3 3 1 2 19 21 10 8 5 6 Ч 2 4 5 1 3 5 3 1 18 19 11 4 10 5 Ш Э 1 2 4 5 1 2 3 3 10 11 17 5 6 7 Ю Я 4 2 1 5 1 3 5 3 13 10 16 6 7 4

ЗАДАЧА № 2

Составить математическую модель задачи; т.е. записать целевую функцию:

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

и условиям:

и Задачу решить симплексным методом данные к задачи выбрать из таблицы №2.

Таблица №2

Первая буква Фамилия Имя Отчество a11 a12 a13 a21 a22 a23 a31 a32 a33 b1 b2 b3 c1 c2 c3 А 1 2 3 4 5 1 2 3 4 30 40 50 2 3 4 Б 4 1 2 3 4 5 1 2 3 60 70 80 5 6 7 В 3 4 1 2 3 4 5 1 2 90 20 10 8 9 10 Г 2 3 4 1 2 3 4 5 1 10 30 40 11 12 13 Д 1 2 3 4 1 2 3 4 5 50 60 70 14 15 16 Е 5 1 2 3 4 1 2 3 4 80 90 20 16 2 3 Ж 4 5 2 3 4 5 1 2 3 20 30 40 4 5 6 З 3 4 5 2 3 4 5 1 2 50 70 60 7 8 9 И 2 3 4 5 2 3 4 5 1 80 70 90 10 11 12 К 2 1 3 4 5 2 3 4 5 40 50 60 13 14 15 Первая буква Фамилия Имя Отчество a11 a12 a13 a21 a22 a23 a31 a32 a33 b1 b2 b3 c1 c2 c3 Л 5 2 1 3 4 5 2 3 4 70 80 90 16 3 2 М 4 5 2 1 3 4 5 2 3 30 40 50 4 6 5 Н 3 4 5 2 1 3 4 5 1 60 80 70 3 4 5 О 1 3 4 5 2 1 3 4 5 90 80 70 6 7 8 П 5 1 3 4 5 2 1 3 4 35 45 55 9 10 11 Р 4 5 1 2 3 4 2 1 3 65 75 85 12 13 14 С 3 4 5 1 2 3 4 2 1 95 100 105 15 16 14 Т 1 3 4 5 3 4 2 5 2 100 90 80 4 3 2 У 3 1 4 5 2 3 4 5 2 70 35 45 7 6 5 Ф 2 3 1 4 5 2 3 4 5 55 65 75 10 9 8 Х 3 2 3 1 4 5 1 2 3 85 95 100 10 4 5 Ц 4 4 2 3 1 4 5 1 2 45 60 70 4 2 5 Ч 2 3 4 2 3 1 4 5 1 65 40 30 5 8 9 Ш Э 1 2 3 3 2 3 1 4 5 65 50 60 6 8 7 Ю Я 5 1 2 3 4 2 3 1 4 100 65 80 5 7 8

ЗАДАЧА № 3

Используя вариант предыдущего контрольного задания №2 необходимо:

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

- установить сопряженные пары переменных прямой и двойственной задач;

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

ЗАДАЧА№ 4

Поставщики товара - оптовые коммерческие предприятия А1, Am имеют запасы товаров соответственно в количестве а1, а2,..., am ед и розничные торговые предприятия В1,. В2,....Вn. - подали заявки на закупку товаров в объемах соответственно: b1, b2, b3,.., bn. Тарифы перевозок единицы груза с каждого из пунктов поставки в соответствующие пункты потребления заданы в виде матрицы

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

Таблица №3

Первая буква Фамилия Имя a1 a2 a3 a4 b1 b2 b3 b4 А 10 20 30 41 10 29 50 71 Б 11 21 31 40 12 28 50 72 В 10 22 32 42 10 22 31 71 Г 13 20 33 43 13 23 50 70 Д 14 24 30 44 14 32 45 60 Е 15 25 35 45 12 28 52 61 Ж 16 26 36 46 15 35 40 62 З 17 27 34 47 10 33 41 63 И 18 28 38 48 20 34 48 64 К 10 29 39 49 19 35 42 65 Л 20 31 41 51 10 22 40 66 М 21 30 40 50 19 25 41 67 Н 22 32 40 50 18 20 42 68 О 23 33 43 53 17 23 43 69 П 24 34 44 54 16 21 44 70 Р 25 35 45 50 15 27 45 71 С 26 30 46 56 14 20 46 72 Т 27 37 40 57 13 29 47 73 У 28 38 48 50 12 20 48 74 Ф 30 41 51 51 50 20 40 81 Х 31 40 52 62 50 21 39 71 Ц 32 42 50 63 48 20 38 72 Ч 33 43 53 60 47 23 40 73 Ш 34 44 54 64 46 24 33 80 Э 35 45 55 60 45 26 31 75 Ю Я 36 46 50 65 44 25 32 74 Продолжение таблицы №3

Первая буква Отчество с11 с12 с12 с14 с21 с22 с23 с24 с31 с32 с33 с34 с41 с42 с43 с44 А 3 9 7 2 10 5 11 12 1 8 14 4 1 6 8 2 Б 9 2 9 5 3 10 4 11 8 2 7 12 5 8 1 6 В 4 7 3 9 8 2 10 3 6 14 3 5 9 1 12 4 Г 1 3 6 4 9 3 8 10 2 12 9 4 1 5 12 7 Д 4 5 2 12 5 9 3 6 10 1 8 11 5 4 14 3 Е 8 1 10 6 11 4 9 2 12 10 5 8 3 7 4 9 Ж 5 3 7 12 2 14 3 4 9 4 10 6 7 2 8 1 З 3 8 11 1 14 5 6 2 8 9 4 10 7 4 5 3 И 9 10 3 8 6 11 5 9 2 14 7 1 10 3 2 4 К 2 8 11 3 12 8 1 14 5 2 6 3 4 10 7 9 Л 8 1 7 16 10 2 12 4 14 7 3 5 11 6 9 4 М 1 7 1 6 11 10 3 12 8 15 5 4 8 5 2 7 Н 6 3 7 1 5 12 10 4 16 8 2 9 5 11 10 3 О 7 8 1 14 1 4 9 10 11 3 12 4 2 6 3 5 П 5 2 12 9 15 8 3 12 10 1 4 2 6 3 7 4 Р 4 11 6 15 7 3 14 2 4 2 9 3 3 1 5 8 С 2 3 14 6 8 16 5 1 1 8 2 3 4 9 4 7 Т 3 12 1 11 14 4 2 5 1 2 3 10 6 8 7 4 У 2 4 3 1 10 12 7 16 3 1 4 9 10 8 6 5 Ф 1 8 14 3 7 5 3 4 9 5 10 11 2 12 6 2 Продолжение таблицы №3

Первая буква Отчество с11 с12 с12 с14 с21 с22 с23 с24 с31 с32 с33 с34 с41 с42 с43 с44 Х 8 1 4 7 3 10 2 9 4 12 5 2 11 6 1 3 Ц 2 9 1 8 12 3 10 2 3 4 2 5 6 11 14 7 Ч 3 7 9 1 8 5 3 10 1 2 4 6 5 7 2 4 Ш 7 4 2 9 1 8 11 3 2 1 6 4 3 5 12 10 Э 4 8 11 5 9 1 8 2 3 6 1 3 4 1 5 2 Ю Я 6 2 8 7 4 9 1 8 6 3 10 12 3 4 2 5

ПРАВИЛА ОФОРМЛЕНИЯ РАБОТЫ

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

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

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

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

Допущенную к защите контрольную работу вместе с рецензией на нее студент должен представить на собеседование.

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

IV. МЕТОДИЧЕСКИЕ УКАЗАНИЯ К РЕШЕНИЮ ЗАДАЧ

1. Графический метод решения задач линейного программирования

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

при условиях-ограничениях

где aij, bi, cj -заданные постоянные величины и k?m.

Стандартной (или симметричной задачей линейного программирования называется задача, которая состоит в определении максимального (минимального) значения целевой функции при выполнении условий 1 и 3 , где k=m и l=n.

Канонической (или основной) задачей линейного программирования называется задача, которая состоит в определении максимального (минимального) значения целевой функции при выполнении условий 2 и 4, где k=0 и l=n.

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

План |при котором целевая функция задачи принимает максимальное (минимальное значение, называется оптимальным.

В случае, когда требуется найти минимум функции =с1х1+с2х2+...cnхn, можно перейти к нахождению максимума функции F(X)=F(X)=-c1x1-c2x2-...-cnxn. так как min F(X)= -max F(X).

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

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

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

Так как векторы Аj являются m-мерными, то из определения опорного плана следует, что число его положительных компонент не может превышать m.

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

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

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

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

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

Множество планов основной задачи линейного программирования является выпуклым (если оно не пусто).Непустое множество планов называется многогранником решений, а всякая угловая точка многогранника решений - вершиной.

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

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

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

F(X) = clx1+c2x2

при условиях

Каждое из неравенств системы ограничений задачи геометрически определяет полуплоскость допустимых значений переменных соответственно с граничными прямыми

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

Решение задачи линейного программирования графическим методом включает следующие этапы.

1. На плоскости Х1ОХ2 строят прямые, уравнения которые получаются в результате замены в ограничениях знаков неравенств на знаки точных равенств.

2. Находят полуплоскости, определяемые каждым из ограничений задачи.

3. Строят многоугольник решений.

4. Строят вектор , направление которого указывает на возрастание целевой функции.

5.Строят начальную прямую с1х1+с2х2=0 и передвигают ее в направлении вектора до крайней угловой точки многоугольника решений. В результате находят точку, в которой целевая функция принимает максимальное значение, либо множество точек с одинаковым максимальным значением целевой функции, если начальная прямая сливается с одной из сторон многоугольника решений, либо устанавливают неограниченность сверху функции на множестве планов .

6. Определяют координаты точки максимума функции и вычисляют значение целевой функции в этой точке

Минимальное значение линейной функции цели находится путем передвижения начальной прямой с1х1+с2х2=0 в направлении, противоположном вектору .

Пример

Найти максимум и минимум линейной функции:

при условиях:

Решение:

Построим на плоскости Х1ОХ2 многоугольник решений рис 1. Для этого в неравенствах системы ограничений и условиях неотрицательности переменных знаки неравенств заменим на знаки точных равенств

Построив полученные прямые, найдем соответствующие полуплоскости и их пересечение

Построив полученные прямые, найдем соответствующие полуплоскости и их пересечение

Многоугольником решений задачи является пятиугольник АВСДЕ, координаты точек которого удовлетворяют условию неотрицательности и неравенствам системы ограничений задачи. Для нахождения точек экстремума построим начальную прямую =0=2х1+3х2 и вектор (2,3). Передвигая прямую =0 параллельно самой себе в направлении вектора .

Рис. 1. Построение многоугольника решений

Найдем точку С, в которой начальная прямая принимает положение опорной прямой. Следовательно, в точке С целевая функция принимает максимальное значение, так как точка С получена в результате пересечения прямых 1 и 2 , то ее координаты удовлетворяют уравнениям этих прямых:

Решив систему уравнений, получим: х1=3,4; х2=4,2; =2·3,4+3·4,2=6,8+12,6=19,4.

Для нахождения минимального значения целевой функции, задачи перемещаем начальную прямую в направлении, противоположном вектору . Начальная прямая займет положение опорной прямой в вершине Е. Целевая функция принимает минимальное значение в угловой точке Е, где х1=1, x2=0, a =1·2+ 3·0=2.

Найдем координаты угловых точек В, Д и А. Для этого решим следующие системы уравнений.

В результате получим координаты точек В(0;2,5), Д(2,0) и А(0,1).

Вычислим значения целевой функции во всех угловых точках многоугольника решений АВСДЕ:

F(0,1) =2·0+3·1=3

В(0;2.5) =2·0 + 3·2,5 = 7,5

С(3,4;4.2) =2·3,4 + 3·4,2 = 19,4(mах)

Д(2.0) =2·2 + 3·0 = 4.

Е(1.0) =2·1+3·0=2 (min)

КОНТРОЛЬНЫЕ ВОПРОСЫ

1. Сформулируйте общую задачу линейного программирования.

2 Дайте определение невырожденного и вырожденного опорного плана, оптимального плана.

3. Какое множество называется выпуклым?

4. Какая точка выпуклого множества называется угловой?

5. Дайте геометрическую интерпретацию задачи линейного программирования.

6. В какой точке многогранника решений целевая функция задачи линейного программирования достигает оптимального значения?

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

8. Назовите особые случаи при решении задачи линейного программирования графическим методом.

2. Симплексный метод решения задачи линейного программирования

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

Коммерческое предприятие реализует несколько n-товарных групп, располагая m ограниченными материально-денежными ресурсами bi(). Известны расходы ресурсов каждого i-вида на реализацию продажи единицы товарооборота товаров по каждой группе, представленной в виде матрицы A=(ai,j),bi?0, m{|3|, |4|} Рассчитываем значения 0 по строкам, как частное от отделения и выбираем наименьшее:

Симплексная таблица 3

План Базисные переменные Ресурсы

план Значения коэффициентов переменных

при х1 х2 х3 х4 xs х6 I план x4

x5 x6 1100 120 8000 0,1 0,05 3 0,2

0,02 1 0,4 0,02 2 1

0 0 0 1 0 0 0

1 5500 6000 8000 Индексная строка 0 -3 -5 -4 0 0 0 II план х2

x5 x6 5500 10

2500 0,5 0,04 2,5 1

0 0 2 -0,02 0 5

-0,1 -5 0 1 0 0

0 1 11000

250 1000 Индексная строка 27500 -0,5 0 6 25 0 0 III план х2

х1 х6 5 375 250

1875 0 1 0 1 0

0 2,25

-0,5 1,25 6,25 -2,5

1,25 -12,5 25 -62,5 0

0 1 Индексная строка 27 625 0 0 5,75 23,75 12,5 0

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

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

5. Формируем следующую симплексную таблицу. Вместо переменной х4 в план II войдет переменная х2. Строка, соответствующая переменной х2 в плане II, получена в результате деления всех элементов строки х4 плана I на разрешающий элемент РЭ=0,2. На месте разрешающего элемента в плане II получаем 1. В остальных клетках столбца х2 плана II записываем нули.

Таким образом в новом плане II заполнены строки х2 и столбец х2. Все остальные элементы нового плана II, включая элементы индексной строки определяется по правилу прямоугольника. Для этого выбираем из старого плана 4 числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ=0,2. Во второй вершине по диагонали находится старое значение элемента например, значение целевой функции F(K,)=0=C3, которое указывает на место расположение нового НЭ в новом плане II. Третий элемент А=1100 и четвертый элемент В=-5 завершают построение прямоугольника в недостающих двух вершинах и расположены по другой диагонали. Значение нового элемента в плане II находится из выражения:

Элементы строки определяются аналогично:

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

Выполняя последовательно все этапы алгоритма, формируем план II.

6. На третьей итерации таблицы 3 получаем план III, который является оптимальным, так как все коэффициенты в индексной строке ?0.

Оптимальный план можно записать так:

=(250,5375,0,0,0,1875),=27625 тыс. руб.

Следовательно, необходимо продавать товаров первой группы А 250 ед., а второй группы В - 5375 ед. При этом торговое предприятие получает максимальную прибыль в размере 27625 тыс. руб. Товары группы С не реализуются.

В оптимальном плане среди базисных переменных находится дополнительная переменная х6. Это указывает, что ресурсы третьего вида (площадь складских помещений) недоиспользована на 1875 м2. так как переменная х6 была введена в третье ограничение задачи, характеризующее собой использование складских помещений.

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

КОНТРОЛЬНЫЕ ВОПРОСЫ

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

2. Каков признак оптимальности в симплексном методе?

3. Как строится первый опорный план?

4. Как определяется ведущий столбец и ведущая строка симплексной таблицы?

5. Как осуществляется пересчет элементов симплексной таблицы?

6. Каковы особые случаи при реализации симплексного метода?

3. ДВОЙСТВЕННАЯ ЗАДАЧА.

Двойственная задача формулируется следующим образом.

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

Запишем математическую модель двойственной задачи.

Определить = (у1, у2,..., уm), который удовлетворяет ограничениям

yi?0

и доставляет минимальное значение целевой функции

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

Для симметричной пары задач двойственная задача по отношению к исходной составляется согласно следующим правилам.

1.Число переменных в двойственной задаче равно числу ограничений в прямой задаче.

2.Матрица коэффициентов системы ограничений двойственной задачи получается из матрицы коэффициентов системы ограничений прямой задачи путем транспонирования.

3. Система ограничений двойственной задачи записывается в виде неравенств противоположного смысла неравенствам системы ограничений прямой задачи.

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

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

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

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

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

Установим сопряженные пары переменных прямой и двойственной задач. Запишем переменные задач в двух строчках. В первой располагаем переменные xj по порядку номеров: сначала основные, затем - дополнительные, а во второй строке запишем переменные двойственной задачи: сначала дополнительные, затем - основные.

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

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

Определить =(y1, y2, y3), который удовлетворяет условиям - ограничениям:

и обеспечивает минимальное значение целевой функции =1100у1+120у2+8000у3 >min

Таким образом оптимальный план двойственной задачи имеет вид:

=(23,75; 12,5; 0; 0; 0; 5,75) =27625 руб

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

КОНТРОЛЬНЫЕ ВОПРОСЫ

1. Как сформулировать экономическую постановку двойственной задачи к задаче планирования торгового процесса?

2. Как записывается математическая модель прямой и двойственной задач?

3. Каков план построения двойственной задачи?

4. Как определяется сопряженные пары переменных прямой и шейной задач?

4. ТРАНСПОРТНАЯ ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Транспортная задача заключается в определении оптимального плана перевозок некоторого однородного груза из m пунктов отправления А1, А2, ... , Аm в n пунктов потребления B1, B2,..., Bn.

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

Введем обозначения:

аi - запасы груза в i-ом пункте отправления ();

bi - величина заказа на этот груз в j-ом пункте назначения

сij - стоимость перевозки единицы груза из A i-гo пункта отправления в В j-ый пункт потребления (тариф перевозок);

xij - количество груза, доставленного из i пункта в j пункт, хij?0.

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

Все исходные данные транспортной задачи можно записать в виде транспортной таблицы 4.

где - суммарный запас груза у поставщиков;

- суммарная величина заявок потребителей

Математическая постановка транспортной задачи заключается в определении матрицы ; которая удовлетворяет следующим условиям:

Таблица 4

Пункты от-

правления Пункты назначения Запасы a1 В1 В2 ... B1 ... Bn A1 с11

x11 с12 x12 ... с1i

x1i ... с1n x1n a1 А2 с21

x21 с22

x22 ... с1i x1i ... с1n

x1n a2 ... ... ... ... ... ... ... ... Ai сi1

xi1 сi2 xi2 ... сij

xij ... сin

xin ai ... ... ... ... ... ... ... ... Аm сm1

xm1 сm2 xm2 ... сmj

xmj сmn xmn am Заявки b1 b1 b2 ... bj ... bn

И обеспечивает минимальное значение целевой функции

а) всякое неотрицательное решение системы линейных уравнений, определяемое матрицей ; называется допустимым планом транспортной задачи:

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

в) Допустимый план транспортной задачи, имеющий не более (m+n-1) отличных от нуля величин xij, называется опорным.

г) Если в опорном плане число отличных от нуля компонент равно в точности (m+n-1), то план является невырожденным, если меньше, то план называется вырожденным.

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

е) Для решения транспортной задачи необходимо и достаточно, чтобы суммарные запасы груза в пунктах отправления были равны сумме заявок пунктов назначения

ж) Модель транспортной задачи, удовлетворяющая этому условию, называется закрытой. Если же указанное условие не выполняется, то модель называется открытой.

В случае превышения запаса над заявками: вводится фиктивный (n+1) пункт назначения с потребностью и соответствующие тарифы считаются равными нулю:

При вводится фиктивный (m+1) пункт отправления с запасом груза , и тарифы принимаются равными нулю: .

Рассмотрим один из методов построение первого опорного плана - метод наименьших тарифов.

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

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

1. Среди тарифов находится наименьший.

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

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

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

Дальнейшее улучшение первого опорного плана и получение оптимального плана производим методом потенциалов.

и) План X=(xij) транспортной задачи будет являться оптимальным, если существует система m+n чисел ?i, ?j называемых потенциалами, удовлетворяющая условиям:

?i +?j ? сij для занятых клеток, где xij>0

?i + ?j ?cij для свободных клеток, где хij=0

при решении задачи на минимум, а при решении задачи на максимум:

?j - ?i =сij для занятых клеток, где xij>0

?j - ?i ?сij для свободных клеток, где хij=0

Потенциалы ?i и ?j являются переменными двойственной транспортной задачи и обозначают оценку единицы груза в пунктах отправления и назначения соответственно.

Введем обозначение оценки свободной клетки таблицы:

?ij=cij-( ?i +?j)

Если среди оценок ?ij нет отрицательной (задача поставлена на минимум), то опорный план является оптимальным и все свободные клетки потенциальны.

Алгоритм метода потенциалов включает следующие этапы.

1. Построение первого опорного плана.

2. Проверка вырожденности плана.

Потенциалы ?i и ?j могут быть рассчитаны только для невырожденного плана. Если число занятых клеток в опорном плане меньше, чем (m+n+1) . то вносим нуль в одну из свободных клеток таблицы так, чтобы общее число занятых клеток стало равным (m+n+1). Нуль вводят в клетку с наилучшим тарифом одного из одновременно вычеркиваемых рядов таблицы. При этом фиктивно занятая нулем клетка не должна образовывать замкнутого контура с другими клетками таблицы.

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

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

Определением потенциалы ?i и ?j. Для каждой занятой клетки таблицы записываем уравнение ?j - ?i =сij . Получим систему (m+n+1) уравнений с (m+n) переменными.

Так как число переменных больше числа уравнений (m+n>m+n+1) . то система не определена и имеет бесчисленное множество решений. Одному из неизвестных ?i ?j. придают произвольное значение, например, для простоты вычислений полагаем ?i=0. Тогда остальные потенциалы определяются из приведенных соотношений.

В транспортную таблицу добавляется дополнительная строка и столбец, куда заносятся потенциалы.

Определяем оценки свободных клеток ?ij.

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

5. Построение нового опорного плана

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

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

Вершинам цикла, начиная от вершины, находящейся в свободной клетке, присваиваем поочередно знаки "+" и "-".

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

ЗАМЕЧАНИЯ

1. Если в минусовых клетках построенного цикла находятся два (или несколько) одинаковых минимальных значения хij, то при перераспределении объемов груза освобождаются две (или несколько) клеток, и план становится вырожденным. Для продолжения решения необходимо в одну (или несколько) одновременно освобождающихся клеток направить нуль, причем предпочтение отдается клетке с наилучшим тарифом. Нулей вводится столько, чтобы во вновь полученном опорном плане число занятых клеток было равно (m+n-1).

2. Если в оптимальном плане транспортной задачи оценка для некоторой свободной клетки ?ij=0, то задача имеет множество оптимальных планов. Для клетки с нулевой оценкой можно построить цикл и перераспределить груз. В результате полученный план будет также оптимальным.

3. Значение функции цели на каждой интерации можно рассчитать следующим образом:

F(Xk)=?(Xk-1)-0• ?ij. задача поставлена на min,

F(Xk)=(Хk-1)+0• ?ij. задача поставлена на max, где при переходе к новому плану;

F(Xk) - значение функции цели на k интерации;

Хk-1- значение функции цели на предыдущей (k-1) - интерации.

Пример решения транспортной задачи

На три базы А1,А2,А3 поступил однородный груз в количествах, соответственно равных 6, 8, 10 (ед.) Этот груз требуется перевезти в четыре магазина В1,В2,В3,В4 соответственно в количествах 4, 6, 8, 8 (ед.). Стоимость доставки единицы груза с каждого из пункта отправления в соответствующие пункты назначения задана матрицей тарифов (в руб.).

i=1,2,3;j=1,2,3,4.

Составить план перевозок однородного груза с минимальными транспортными издержками.

Проверим необходимое и достаточное условие разрешимости задачи.

=6+8+10=24.

=4+6+8+6=26

Как видно, суммарная потребность груза в пунктах назначения превышает запасы груза на трех базах. Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем дополнительную (фиктивную) базу А4 с запасом груза, равным 26-24=2 (ед.) Тарифы перевозки единицы груза из базы А4 во все магазины полагаем равны нулю.

Занесем исходные данные в распределительную таблицу 5.

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

Среди тарифов из всей таблицы наилучшим является с11=1, поэтому в клетку A1B1 направляем максимально возможный груз. Он равен min{6,4}=4. Тогда x11=4 и из базы A1 не вывезен, груз 2 ед., а потребность магазина B1 удовлетворена полностью. Столбец таблицы В1 выходит из рассмотрения. Из оставшихся тарифов строки наименьший - с12=2. В клетку A1B2 направляем максимально возможный груз, равный min{2,6}=2. Тогда строка А1 выходит из рассмотрения, поскольку из базы A1 вывезен весь груз. Из оставшихся тарифов наилучший с22=3 и с34=2. В клетку А2В2 направляем груз, равный min{8,4}=4. При этом вычеркивается столбец В2 из рассмотрения. Из оставшихся тарифов наименьший с34=3. В клетку А3В1 направляем груз, равный min{10,8}=8. При этом потребность четвертого магазина удовлетворена, а из третьей базы не вывезено 2 ед. Этот нераспределенный груз направляем в клетку А3В3, х33=2. Потребность третьего магазина не удовлетворена на 2 ед. Направим от фиктивного поставщика - базы А4 2 ед. в клетку А4В3, т.е. х43=2.

Таблица 5

Bj Аi В1 B2 B3 B4 Потенциалы ? i b1=4 b2=6 b3=8 b4=8 А1 a1=6 1

4 - 2

2- 4 + 3 ?1=0 А2 a2=8 4

4 3 4+ 8

4- 5 ? 2=1 A3 a3=10 2 7 6

2 3 8 ?3=-l А4 a4=2 0 0 0

2 0 ? 4=-7 Потенциалы ?1 ?1=1 ?2=2 ?3=7 ?2=4

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

Подсчитаем число занятых клеток таблицы, их -7, а должно быть m+n-1=4+4-1=7. Следовательно, опорный план является невырожденным.-

3. Определяем значение целевой функции первого опорного плана

F(X1)=4·1+2·2+4·3+4·8+2·6+8·3+2·0=88 руб.

Подтвердим оптимальность опорного плана.

4. Найдем потенциалы ?i, ?i. по занятым клеткам таблицы, решая систему уравнений, полагая, что ?i +?i.=С и ?1=0

Занесем рассчитанные потенциалы в таблицу 5, подсчитаем оценки свободных клеток, полагая, что для них ?ij=cij-(?i+?j):

?13= 4-7=-3; ?14=3-4=-1; ?21=4-2=-2; ?24=5-5=0; ?31=2-0=2;

?32=7-1=6; ?42=6; ?44=3;

Первый опорный план является не оптимальным, так как ?13<0 и ?14<0, поэтому переходим к его улучшению. Выбираем максимальную по модулю оценку свободной клетки - ?13=|-3|=3.

4. Для клетки A1B3 построим цикл перераспределения груза. Для этого в перспективную клетку A1 B3 поставим знак +, а в остальных вершинах многоугольника чередующиеся знаки -, +, -:

Затем из чисел xij стоящих в минусовых клетках, выбираем наименьшее, т.е. min{2,4}=2. Прибавляем 2 г объемам грузов, стоящих в плюсовых клетках и вычитаем 2 из хij. стоящих в минусовых клетках. В результате получим новый опорный план II.

6. Определяем значение целевой функции:

F(X2)=F(X1)+0·?13=88+(-3)·2=88-6=82 (руб)

7. Число занятых клеток в II плане 7, следовательно, план не вырожденный.

8. Проверяем оптимальность плана методом потенциалов для этого находим потенциалы ?i ?j по занятым клеткам, полагая ?1=0.

Затем рассчитаем оценки свободных клеток

?12=-2-(-1)=3; ?14=3-1=2; ?21,4-5=-1; ?24=5-5=0

?31=2-3=-1; ?32= 7-1 =6; ?413; ?42=5; ?44=3.

План, полученный в таблице 6 . не оптимальный, так как ?21<0 и ?21<0.

Таблица 6

План II Bj Аi В1 B2 B3 B4 Потенциалы ? i b1=4 b2=6 b3=8 b4=8 А1 a1=6 1

4 ? - 2 4

+ 2 3 ?1=0 А2 a2=8 4

4 + 3

6 8 ? 2 5 ? 2=4 A3 a3=10 2

+ 7 6 3 8 ?3=l А4 a4=2 0 0 0

2 0 ? 4=-4 Потенциалы ?1 ?1=4 ?2=-1 ?3=4 ?2=1

9. Проводим улучшение плана II путем перераспределения грузов. В качестве перспективной клетки для загрузки выбираем А3 В1, в которую записываем +, затем строим цикл перераспределения:

Груз перераспределения равен:

Это единственная положительная оценка, поэтому строим цикл для клетки A4B1. ?=min (4,2)=2.

Перераспределив груз получаем новый план III.

Таблица 7

План III

Bj Аi В1 B2 B3 B4 Потенциалы ? i b1=4 b2=6 b3=8 b4=8 А1 a1=6 1

2 ? 2 4

+ 4 3 ?1=0 А2 a2=8 4

+ 3 6 8

- 2 5 ? 2=4 A3 a3=10 2

2 7 6 3 8 ?3=l А4 a4=2 0 0 0

2 0 ? 4=-4 Потенциалы ?1 ?1=4 ?2=-1 ?3=4 ?2=2 10.Число занятых клеток 7, а должно быть m+n-1=7, следовательно план III невырожденный.

11.Вычислим значение целевой функции:

F(X3)=F(X2)+?•А31 = 82 + 2(-1) = 82- 2 = 80.

12.Проверяем оптимальность плана III методом потенциалов.

Находим потенциалы по занятым клеткам:

Проверим оценку свободных клеток:

?12=2-(-1)=3; ?14=3-(2+0)=1; ?21=4-5=-1; ?24=5-(2+4)=-1;

?32=7-(1+1)=7; ?33=6-(1+4)=1; ?41=0-(-4+1)=3; ?42=0-(-4+4)=0;

?44=4-0-(-4+2)=2.

План не оптимальный. ?21=-1, ?24=-1.

13. Проводим улучшение плана III путем перераспределения груза. В качестве перспективной клетки для загрузки выбираем А2 В1, в которую записываем +, затем строим цикл перераспределения:

Определяем груз перераспределения ?=min(2;2)=2, после исследования операции перераспределения получаем план IV

Таблица 8

План IV

Bj Аi В1 B2 B3 B4 Потенциалы ? i b1=4 b2=6 b3=8 b4=8 А1 a1=6 1

0 2 4 6 3 ?1=0 А2 a2=8 4

2 3 6 8 5 ? 2=3 A3 a3=10 2

2 7 6 3

8 ? 3=l А4 а4 =2 0 0 0 0

2 ? 4=-4 Потенциалы ?1 ?1=1 ?2=0 ?3=4 ?2=2

14. План получается вырожденный поскольку в минусовых клетках цикла находятся два одинаковых минимальных объема груза 2. При перераспределении две клетки A1 B2 и А2 В3 оказались свободными, поэтому число занятых клеток 6 будет меньше, чем m+n-1=7. Для продолжения решения в одну из освободившихся клеток записываем нуль A1 B1 т.к. тариф С11 меньше С23.

15. Вычисляем значение целевой функции:

F(X4)=F(X3)+?·?21=80+2·(-1)=78

15. Проверяем оптимальность плана IV методом потенциалов. Находим потенциалы по занятым клеткам:

Проверим оценку свободных клеток:

?12=2-1=1;?14=3-2=1;?23=8-(3+4)=1;?24=5-(3+2)=0

?32=7-(0+1)=6;?33=6-(4+1)=1;?41=0-(-4+1)=3;?42=0-(-4+0)=4

?44=0-(-4+2)=2 Поскольку все оценки больше или равны нулю, то план оптимален

Анализ плана. Из первой базы необходимо весь груз направить в третий магазин, из второй базы направить в первый и второй магазин в количестве 2 ед. и 6 ед. , а груз с третьей базы следует вывозить в первый и второй магазин в количестве 2 и 8 ед. соответственно. При этом плане потребность третьего магазина В3 остается неудовлетворительной в размере 2 ед. Общая стоимость доставки груза потребителям будет минимальной и составлять 78 тыс. руб. Так как оценка свободной клетки ?24=0, то задача имеет множество оптимальных планов.

КОНТРОЛЬНЫЕ ВОПРОСЫ

1. Сформулируйте транспортную задачу линейного программирования и запишите ее математическую модель.

2. Каковы необходимые и достаточные условия разрешимости транспортной задачи?

3. Какая транспортная задача называется открытой, закрытой?

4. Kак строится первый опорный план транспортной задачи методом наименьших тарифов?

5. Какой план транспортной задачи является оптимальным?

6. Kак выбирается клетка транспортной таблицы, в которую необходимо направить груз при переходе к новому плану?

7. Как определяется объем передвигаемого по циклу груза?

8. Как осуществляется переход к новому опорному плану?

9. Каковы особые случаи при решении транспортной задачи методом потенциалов?

2

Показать полностью…
2 Мб, 13 февраля 2012 в 18:23 - Россия, Ростов-на-Дону, РГТЭУ (РИ), 2012 г., doc
Рекомендуемые документы в приложении