Реферат: Математическое програмирование

🛑 👉🏻👉🏻👉🏻 ИНФОРМАЦИЯ ДОСТУПНА ЗДЕСЬ ЖМИТЕ 👈🏻👈🏻👈🏻

Для производства двух видов изделий А и В используется три типа технологического оборудования. Для производства единицы изделия А оборудование первого типа используется 2 часа, оборудование второго типа – 1 час, оборудование третьего типа – 3 часа. Для производства единицы изделия В оборудование первого типа используется 2 часа, оборудование второго типа – 2 часа, оборудование третьего типа – 1 час.
На изготовление всех изделий предприятие может использовать оборудование первого типа не более чем 48 часа, оборудование второго типа – 38 часов, оборудование третьего типа – 54 часов.
Прибыль от реализации единицы готового изделия А составляет 2 денежные единицы, а изделия В – 3 денежные единицы.
Составить план производства изделий А и В, обеспечивающий максимальную прибыль от их реализации. Решить задачу симплекс-методом путем преобразования симплекс-таблиц. Дать геометрическое истолкование задачи, используя для этого ее формулировку с ограничениями – неравенствами.
Данная задача является задачей линейного программирования. Под планом производства понимается: сколько изделий А и сколько изделий В надо выпустить, чтобы прибыль была максимальна.
Запишем математическую модель задачи:
Для этого построим на плоскости области, описываемые ограничениями-неравенствами, и прямую , которая называется целевой функцией.
Три записанных выше неравенства ограничивают на плоскости многоугольник, ограниченный слева и снизу координатными осями (т.к. искомое количество изделий положительно).
График целевой функции передвигается в направлении, обозначенном стрелкой (в направлении своего градиента), до тех пор, пока не достигнет граничной точки многоугольника – в нашем случае это точка – (10 ; 14). В этой точке целевая функция будет достигать максимума.
Решим эту задачу симплекс-методом. Для этого перейдем от ограничений-неравенств к ограничениям-равенствам, введя дополнительные переменные .
В графе Базис записываются вектора переменных, принимаемые за базисные. На первом этапе это – А 3
, А 4
, А 5
. Базисными будут переменные, каждая из которых входит только в одно уравнение системы, и нет такого уравнения, в которое не входила бы хотя бы одна из базисных переменных.
В следующий столбец записываются коэффициенты целевой функции, соответствующие каждой переменной. Столбец В – столбец свободных членов. Далее идут столбцы коэффициентов А i
при i –й переменной.
Под столбцом свободных членов записывается начальная оценка
Остальные оценки записываются под столбцами соответствующих векторов .
Преобразуем симплекс-таблицу следующим образом:
Шаг 1: Проверяется критерий оптимальности, суть которого состоит в том, что все оценки должны быть неотрицательны. В нашем случае этот критерий не выполнен, поэтому переходим ко второму шагу.
Шаг 2: Для отрицательных оценок вычисляются величины:
Из этих элементов выбирается тот, для которого вычисленное произведение минимально, в нашем случае -57 минимально, поэтому в качестве разрешающего элемента выбирается второй элемент второго столбца – 2 (выделен в таблице).
Шаг 3: Вторая строка таблицы делится на 2
От элементов строки 1 отнимает соответствующие элементы строки 2, умноженные на 2.
От элементов строки 3 отнимает соответствующие элементы строки 2.
От элементов строки 4 отнимает соответствующие элементы строки 2, умноженные на -3.
Таким образом, новыми базисными переменными становятся А 3
, А 5
, А 2
.
Возвращаемся к шагу 1 и повторяем весь процесс.
Проверяется критерий оптимальности. Отрицательная оценка только одна – в столбце А 1
.
Разрешающим элементом будет первый элемент первого столбца – 1.
Новыми базисными переменными становятся A 5
, A 2
, A 1

От элементов строки 2 отнимает соответствующие элементы строки 1, умноженные на 0,5.
От элементов строки 3 отнимает соответствующие элементы строки 1, умноженные на 2,5.
От элементов строки 4 отнимает соответствующие элементы строки 1, умноженные на -0,5.
Отрицательных оценок нет, то есть критерий оптимальности выполнен.
Таким образом, получается искомое значение целевой функции
F(10; 14; 0; 0; 10) = 62, т.е. возвращаясь к системе неравенств, получаем:
Ответы, полученные различными методами, совпадают.
Ответ: х опт
= ( 10 , 14) Значение функции : F = 62
Имеются три пункта отправления А 1
,А 2
,А 3
однородного груза и пять пунктов В 1
, В 2
, В 3
, В 4
, В 5
его назначения. На пунктах А 1
,А 2
,А 3
находится груз в количествах 50, 30, 70 тонн. В пункты В 1
, В 2
, В 3
, В 4
, В 5
требуется доставить соответственно 20, 30, 50, 30, 20 тонн груза. Расстояния в сотнях километрах между пунктами отправления и назначения приведены в матрице D:
Найти такой план перевозок, при котором общие затраты на перевозку грузов будут минимальными.
Указания: 1) считать стоимость перевозок пропорциональной количеству груза и расстоянию, на которое этот груз перевозится, т.е. для решения задачи достаточно минимизировать общий объем плана, выраженный в тонно-километрах;
2) для решения задачи использовать методы северо-западного угла и потенциалов.
Составим математическую модель задачи:
Обозначим - количество груза, перевезенного из пункта отправления i в пункт назначения j.
Получим следующие ограничения (т.к. весь груз должен быть вывезен, и все потребности удовлетворены полностью):
При этом должна быть минимизирована целевая функция
Построим опорный план методом северо-западного угла:
Принцип заполнения таблицы состоит в том, что, начиная с крайней левой верхней ячейки (принцип северо-западного угла), количество грузов вписывается в таблицу так, чтобы потребности полностью удовлетворялись или груз полностью вывозился.
Построим систему потенциалов. U i
- потенциалы, соответствующие поставщикам, V i
- потенциалы, соответствующие потребителям.
Полагаем U 1
=0, а далее U i
+ V i
= d ij
для занятых клеток таблицы.
Проверим критерий оптимальности : для свободных клеток.
Из тех условий, где критерий не выполняется, выбираем то условие, где разница максимальна. Это – ячейка (1 , 4). Перебросим в ячейку (1 , 4) 20 единиц груза из ячейки (1 , 1).
Чтобы компенсировать недостаток в третьей строке, перебросим те же 20 единиц груза из ячейки (3 , 4) в ячейку (3 , 1).
Получили новую таблицу, для которой повторяем расчет потенциалов:
Полагаем U 1
=0, а далее U i
+ V i
= d ij
для занятых клеток таблицы.
Проверим критерий оптимальности : для свободных клеток.
Из тех условий, где критерий не выполняется, выбираем то условие, где разница максимальна. Это – ячейка (2 , 5). Перебросим в ячейку (2 ,5) 20 единиц груза из ячейки (1 , 2).
Получили новую таблицу, для которой повторяем расчет потенциалов:
Полагаем U 1
=0, а далее U i
+ V i
= d ij
для занятых клеток таблицы.
Проверим критерий оптимальности : для свободных клеток.
Из тех условий, где критерий не выполняется, выбираем то условие, где разница максимальна. Это – ячейка (2 , 2). Перебросим в ячейку (2 ,2) 10 единиц груза из ячейки (1 , 2).
Получили новую таблицу, для которой повторяем расчет потенциалов:
Полагаем U 1
=0, а далее U i
+ V i
= d ij
для занятых клеток таблицы.
Проверим критерий оптимальности : для свободных клеток.
Критерий выполнен, значит, полученное решение оптимально.
Найдем минимальную стоимость перевозок.
Дана задача выпуклого программирования. Требуется:
1) найти решение графическим методом
2) написать функцию Лагранжа данной задачи и найти ее седловую точку, используя решение задачи, полученное графически.
Графическое решение задачи следующее:
Система неравенств определяет область, ограниченную двумя прямыми и координатными осями. График целевой функции представляет собой окружность переменного радиуса с центром в точке (5, 10). Значение целевой функции графически представляет собой квадрат радиуса этой окружности. Минимальным радиусом, удовлетворяющим системе ограничений, будет такой радиус, который обеспечивает касание окружности с границей области так, как это показано на рисунке.
Искомая точка определяется как решение системы уравнений
Получили точку (3 , 8), значение целевой функции в этой точке равно
Запишем задачу в традиционном виде:
Функция называется функцией Лагранжа, а переменные - коэффициентами Лагранжа.
Точка называется седловой точкой функции Лагранжа, если для любых выполняются неравенства:
Если функции f, gдифференцируемы, то условия определяющие седловую точку (условия Куна-Таккера):
Подставим в эти выражения значения:
Условия выполнены, седловая точка .
Для двух предприятий выделено 900 единиц денежных средств. Как распределить все средства в течение 4 лет, чтобы доход был наибольшим, если известно, что доход от х единиц, вложенных в первое предприятие равен , а доход от у единиц, вложенных во второе предприятие равен . Остаток средств к концу года составляет - для первого предприятия, - для второго предприятия. Решить задачу методом динамического программирования.
Процесс распределения средств разобьем на 4 этапа – по соответствующим годам.
Обозначим - средства, которые распределяются на k–ом шаге как сумма средств по предприятиям.
Суммарный доход от обоих предприятий на k–ом шаге:
Остаток средств от обоих предприятий на k–ом шаге:
Обозначим - максимальный доход, полученный от распределения средств между двумя предприятиями с k-го шага до конца рассматриваемого периода.
Рекуррентные соотношения Беллмана для этих функций
Проведем оптимизацию, начиная с четвертого шага:
, т.к. линейная возрастающая функция достигает максимума в конце рассматриваемого промежутка, т.е. при .
т.к. линейная возрастающая функция достигает максимума в конце рассматриваемого промежутка, т.е. при .
т.к. линейная возрастающая функция достигает максимума в конце рассматриваемого промежутка, т.е. при .
т.к. линейная возрастающая функция достигает максимума в конце рассматриваемого промежутка, т.е. при .
Определим количественное распределение средств по годам:
Представим распределение средств в виде таблицы:
При таком распределении средств за 4 года будет получен доход, равный

Название: Математическое програмирование
Раздел: Рефераты по математике
Тип: реферат
Добавлен 09:57:56 04 июля 2011 Похожие работы
Просмотров: 184
Комментариев: 15
Оценило: 2 человек
Средний балл: 5
Оценка: неизвестно   Скачать

Срочная помощь учащимся в написании различных работ. Бесплатные корректировки! Круглосуточная поддержка! Узнай стоимость твоей работы на сайте 64362.ru
Привет студентам) если возникают трудности с любой работой (от реферата и контрольных до диплома), можете обратиться на FAST-REFERAT.RU , я там обычно заказываю, все качественно и в срок) в любом случае попробуйте, за спрос денег не берут)
Да, но только в случае крайней необходимости.

Реферат: Математическое програмирование
2 Класс Сочинение Придумать
Реферат: Кто разрабатывает бизнес-план?
Оборот Оружия Реферат
Правила Упаковки Товаров Реферат
Дипломная работа: Создание клиентских частей SQL БД под ОС Windows'95 и WindowsNT. Скачать бесплатно и без регистрации
Реферат: Magicians Nephew Essay Research Paper The play
Курсовая работа по теме Исследование рынка мягкой мебели г. Краснодара на примере ООО 'Центр Мебели'
Методы определения тс импортных товаров
Рота Уже Залегла Перед Броском Сочинение 9.3
Ахматова Собрание Сочинений Скачать
Презентация Речи Дипломной Работы
Результаты Контрольные Работы Обществознание 2022
Физические основы СКВИД - микроскопии
Курсовая работа по теме Создание приложения VBA в Access 'Начисления заработной платы по должностям'
Реферат по теме Повесть
Реферат Дар Мавзуи
Реферат: Паремии Корочанского района
Учебное пособие: Учебно-методическое пособие для студентов биологических и экологических специальностей Балашов
Ответственность Должностных Лиц Реферат
История Болезни На Тему Папилломатоз Гортани
Контрольная работа: Економіка праці й соціально-трудові відносини
Реферат: Бизнес-план ночного клуба
Курсовая работа: Оценка финансового состояния организации