Вопросы к экзамену 5 Задания для контрольных работ 6 Методические указания для выполнения контрольных работ 7 Указания для оформления контрольных работ 21 Список литературы 24 Приложения 25 Введение Дисциплина «Методы оптимальных решений»
Скачать 312.15 Kb.
|
3 Методические указания для выполнения контрольных работЗадание 2. Симплекс-метод решения задачи линейного программирования Рассмотрим пример. 2.1 Постановка задачи Для производства двух видов изделий А и В предприятие использует три вида сырья. Нормы расхода сырья каждого вида на изготовление единицы продукции данного вида приведены в таблице. В ней же указаны прибыль от реализации одного изделия каждого вида и общее количество сырья данного вида, которое может быть использовано предприятием.
Учитывая, что изделия А и В могут производиться в любых соотношениях (сбыт обеспечен), требуется составить такой план их выпуска, при котором прибыль предприятия от реализации всех изделий является максимальной. Составить математическую модель задачи, решить задачу геометрически и симплекс-методом. 2.2. Математическая модель задачи Искомый выпуск изделий А обозначим через х1 изделий В - через х2. Поскольку имеются ограничения на выделенный предприятию фонд сырья каждого вида, переменные х1, х2 должны удовлетворять следующей системе неравенств:  12х1 + 4х2 ≤ 300,4х1 + 4х2 ≤ 120, (1) 3х1 + 12х2 ≤ 252. Общая прибыль произведенной предприятием продукции составляет F = 30х1 + 40х2. (2) По своему экономическому содержанию переменные х1 и х2 могут принимать только лишь неотрицательные значения: х1, х2 > 0. (3) Таким образом, приходим к следующей математической задаче: среди всех неотрицательных решений системы неравенств (1) требуется найти такое, при котором функция 2) принимает максимальное значение. 2.3 Геометрическое решение задачи Сначала определим многоугольник решений 1) 12х1 + 4х2 = 300 х2 = 75 - 3х1 2) 4х1 + 4х2 = 120 х2 = 30 - х1 3) 3х1 + 12х2 = 252  4)  5)   Многоугольник решений – OABCD  Построим линию уровня  
Построим вектор  .  Передвигаем линию уровня вдоль вектора С до тех пор, пока она не пройдет через последнюю ее общую точку с многоугольником решений. Эта точка – В. Точка пересечения второй и третьей линии:        В(12; 18) Найдем значение целевой функции в этой точке: F(12; 18) = 3012 + 4018 = 1080 Ответ: план выпуска: Х = (12; 18), F(Х) = 1080. 2.4 Решение задачи симплекс-методом Запишем эту задачу в форме основной задачи линейного программирования. Для этого перейдем от ограничений-неравенств к ограничениям-равенствам. Введем три дополнительные переменные, в результате чего ограничения запишутся в виде системы уравнений  12х1 + 4х2 + х3 = 300,4х1 + 4х2 + х4 = 120, 3х1 + 12х2 + х5 = 252. Эти дополнительные переменные по экономическому смыслу означают не используемое при данном плане производства количество сырья того или иного вида. Например, х3 - это неиспользуемое количество сырья I вида. Преобразованную систему уравнений запишем в векторной форме: x1P1 + x2P2 + x3P3 + x4P4 + x5P5 =P0, где  ;  ;  ;  ;  ;  .Поскольку среди векторов P1, P2, P3, P4, P5 имеются три единичных вектора, для данной задачи можно непосредственно записать опорный план. Таковым является план X = (0, 0, 300, 120, 252), определяемый системой трехмерных единичных векторов P3 , P4 , P5, которые образуют базис трехмерного векторного пространства. Составляем симплексную таблицу I итерации (табл. 1): Вычисления в 4-ой (m+1)-й строке:  ; ; ; ; ; ; ; ; ; Таблица 1.
Целевая функция равна нулю (ничего не производится, сырье не тратиться – план не оптимальный). То, что план не оптимальный, видно из четвертой строки: имеются отрицательные числа. Отрицательные числа не только свидетельствуют о возможности увеличения общей прибыли производимой продукции, но и показывают, на сколько увеличится эта сумма при введении в план единицы того или другого вида продукции. Так, число -30 означает, что при включении в план производства одного изделия А обеспечивается увеличение прибыли выпуска продукции на 30 руб. Если включить в план производства одно изделие В, то общая прибыль возрастет на 40 руб. Поэтому с экономической точки зрения наиболее целесообразным является включение в план производства изделий В. Определим, какой вектор включить в базис:  .Вектор Р2 включаем в базис. Определяем, какой вектор исключить из базиса:  для аi2 > 0. .Соответствует Р5. Этот вектор исключаем из базиса. Столбец вектора Р2 и 3-я строка являются направляющими. Составляем таблицу II итерации (табл. 2). Таблица 2.
Заполняем строку вектора Р2: элементы строки получаются из соответствующих элементов предыдущей таблицы 1 делением на разрешающий элемент (на 12).  .Заполняем столбцы для базисных векторов. На пересечении PiPi ставим единицы, остальные элементы – нули. Вычисляем следующие элементы в столбцах: r = 5 (исключенный вектор), k = 2 (включенный вектор)  , , , , , .Вычислим элементы в 4-й строке по рекуррентным формулам:   ,  , .Найденный план не является оптимальным, т.к. в столбце вектора Р1 – отрицательное число: -20 < 0. Х = (0, 21, 2416 36, 0). Значит, Р1 вводим в базис.   Р4 – исключаем из базиса. Составляем таблицу III итерации: Таблица 3.
Сначала заполняем элементы 2-й строки (для Р1). Получаем их из элементов 2-й строки таблицы 2 делением на разрешающий элемент: на 3 (Р1Р4). Заполняем остальные строчки: сначала столбцы для Р3, Р1, Р2 (единицы PiPi и нули) Остальные ячейки – по рекуррентным формулам: r = 4 (исключенный вектор), k = 1 (включенный вектор)  , , ,  , .Заполняем последнюю строчку.  , , .В четвертой строке таблицы нет отрицательных j. Значит, найденный опорный план является оптимальным: Х = (12, 18, 84, 0, 0). Следовательно, план выпуска продукции, являющийся оптимальным, включает изготовление: 12 изделий А, 18 изделий В. На изделие А: 1212 = 144 кг – I вида сырья, 124 = 48 кг – II вида сырья, 123 = 36 кг – III вида сырья. На изделие В: 184 = 72 кг – I вида сырья, 184 = 72 кг – II вида сырья, 1812 = 216 кг – III вила сырья. Использовано I вида сырья: 144+72 = 216 кг – осталось 300 – 216 = 84 кг, использовано II вида сырья: 48+72 = 120 кг – использовано полностью, использовано III вида сырья: 36+216 = 252 кг –использовано полностью. Прибыль от производимой продукции 1080 руб. Задание 3. Транспортная задача. Рассмотрим пример. 3.1 Постановка задачи. На двух базах Б1 и Б2 находится однородный груз в количестве соответственно: а1 и а2 условных единиц. Этот груз необходимо перевести на три предприятия П1, П2 и П3, потребности которых составляют соответственно b1, b2 и b3 условных единиц. Стоимость перевозки одной условной единицы груза с базы Бi на предприятие Пj составляет cij руб. Эти стоимости указаны в таблице. Необходимо спланировать перевозки так, чтобы их общая стоимость была наименьшей.  3.2 Математическая модель задачи Определим количество груза, отправленного с каждой базы:  (4)Определим количество груза, доставленное на каждое предприятие:  (5)Общая стоимость перевозок:   при (4) ,(5) и  .1. Определим тип модели.  , . ,задача сбалансированная, модель закрытая.3.3 Решение транспортной задачи 1. Найдем первоначальный опорный план методом северно-западного угла. Сделаем поставку в клетку (1, 1): x11 = min (a1, b1) = min (600, 840) = 600. Следовательно, удовлетворяем полностью потребности П1. Значение 600 вписываем в клетку (1, 1); первый столбец вычеркиваем. Пересчитываем запас груза на базе Б1, т.е. значение a1: a1 - b1 = 840 – 600 = 240.  Сделаем поставку в клетку (1, 2): x12 = min (a1, b2) = min (240, 360) = 240. Следовательно, удовлетворяем полностью поставщика Б1. Значение 240 вписываем в клетку (1, 2); первую строку вычеркиваем. Пересчитываем потребность П2, т.е. значение b2: b2 - a1 = 360 – 240 = 120.  Сделаем поставку в клетку (2, 2): x22 = min (a2, b2) = min (600, 120) = 120. Следовательно, удовлетворяем полностью потребность П2. Значение 120 вписываем в клетку (2, 2); второй столбец вычеркиваем. Пересчитываем запасы груза на Б2, т.е. значение a2: a2 – b2 = 600 – 120 = 480.  Сделаем поставку в клетку (2, 3): x23 = min (a2, b3) = min (480, 480) = 480. Удовлетворяем полностью потребность П3 и запасы на Б2. Значение 480 вписываем в клетку (2, 3).  План составлен, полностью удовлетворены и поставщики, и потребители.  Занятых клеток 4, и по условию N = 2+3-1 = 4. Значит, план опорный. Клетки, в которых помещаются грузы, называются занятыми, им соответствуют базисные переменные. Остальным клеткам (незанятым) соответствуют свободные переменные. 2. Вычислим стоимость перевозки.  .3. Проверим план па оптимальность. Найдем потенциалы ui и vi из условия  для  :(ui соответствует строка, vi - столбец),  для x11:  для x12:  для x22:  для x23:  Система содержит 4 уравнения и 5 неизвестных, следовательно, система имеет бесконечно много решений. Одну переменную можно выбрать произвольно (потенциал строки или столбца с наибольшим количеством занятых клеток). Пусть v2 = 0. u1 = 2 v1 = 3 – u1 = 3 – 2 = 1 u2 = 4 – v2 = 4 v3 = 3 – u2 = 3 – 4 = –1 Вычислим оценки свободных клеток: ij = ui + vj - cij 13 = u1 + v3 – c13 = 2+(-1)-4 = -3 21 = u2 + v1 – c21 = 4+1-2 = 3 4. Делаем выводы. План не оптимален, т.к. имеются положительные оценки ij. Наибольшую экономию можно получить по клетке, где наибольшее значение ij из положительных. Клетку (2, 1) необходимо загрузить. 5. Делаем переход к следующему лучшему (не худшему) плану. Строим означенный цикл:   Анализируем клетки со знаком «минус» и выбираем клетку с минимальным объемом перевозок. = min{xij} = min(x11, x22) = 120. Прибавляем данное число к вершинам с «+», вычитаем из вершин с «-». 600-120 240+120  120-120 0+120 480 360 120 0 Новый план:  .Внесем в таблицу полученные поставки:  6. Повторим проверку плана на оптимальность.  Пусть  , тогда  Оценки:  Данный план оптимальный. Вычислим стоимость перевозки: L(Xопт) = 3 480+2 360+4 0+2 120+4 0+3 480 = 3840. Ответ:  , L(Xопт) = 3840. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Похожие:
 | Методические указания по выполненю контрольных работ выполнение контрольных... Тематика контрольных работ и рефератов для студентов первого курса заочного отделения факультета мировой экономики и торговли | | Методические указания по темам курса, задачи контрольных работ (десять... Математика. Пособие к изучению дисциплины и варианты заданий для контрольных работ. – М.: Мгту га, 2008. 48 с |
| Методические указания и тематика контрольных работ для студентов... Культурология: Методические указания и тематика контрольных работ / Сост. Н. Д. Михайлова. Новосиб гос аграр ун-т. Новосибирск, 2007.... |  | Методические указания по выполнению контрольных работ Направление... В методических указаниях излагаются цель и задачи выполнения контрольных работ, дана тематика с примерным кругом вопросов по всем... |
| Методические указания к выполнению контрольных работ по дисциплине “ Методические указания к выполнению контрольных работ по дисциплине “Основы внешнеэкономической деятельности” для студентов экономических... | | II. Указания о порядке выполнения контрольных работ Необходимым этапом самостоятельной работы над программным материалом является выполнение контрольных работ по предложенным |
| Тесты для самостоятельной работы. Для студентов заочной формы работы... Методические указания к семинарским занятиям, практикум, контрольные работы и задания | | Программа по формированию навыков безопасного поведения на дорогах... По физике и химии: 3 тетради (1 тетрадь для выполнения классных и домашних работ, 1 тетрадь для выполнения контрольных работ, 1 тетрадь... |
| Методические указания к выполнению контрольных работ по дисциплине «Информатика» Задания и методические указания к выполнению контрольных работ по дисциплине «Информатика». Екатеринбург, фгаоу впо «Российский государственный... | | Методические указания по выполнению контрольных работ для экономических специальностей Методические указания по выполнению контрольных работ по дисциплине "Экономическая теория" для студентов экономических специальностей–... |
| Методические указания по изучению дисциплины и выполнению контрольных... Педагогика: Методические указания по изучению дисциплины и выполнению контрольных работ /Университет га. С. – Петербург, 2012 | | Методические указания по выполнению контрольных работ по дисциплине Методические указания по выполнению контрольных работ по дисциплине «Правовые основы российского государства» для студентов по специальности... |
| Методические указания по изучению курса и выполнению контрольных... География воздушного транспорта : Методические указания по изучению курса и выполнению контрольных работ/ Университет га. С. – Петербург,... | | Методические указания по изучению курса и выполнению контрольных работ Для студентов зф Автоматизированные системы бронирования и продажи авиационных услуг: Методические указания по изучению курса и выполнению контрольных... |
| Методические указания для написания контрольных работ Задания предназначаются... Электронный ресурс]: для написания контрольных работ / Н. Ю. Рычкова, И. В. Яковенко. – Электрон дан. – Красноярск: Сиб федер ун-т,... | | Методические указания для написания контрольных работ Задания предназначаются... Методические указания предназначены для написания контрольных работ студентами юи сфу 3-го и 4-го курсов заочной формы обучения |
