Вход

методы оптимальных решений УРГЭУ

Рекомендуемая категория для самостоятельной подготовки:
Контрольная работа*
Код 245401
Дата создания 16 февраля 2016
Страниц 21
Мы сможем обработать ваш заказ (!) 29 марта в 12:00 [мск]
Файлы будут доступны для скачивания только после обработки заказа.
730руб.
КУПИТЬ

Описание

Вариант № 2, контрольная на отлично,расчеты,графики присутствуют. ...

Содержание

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

Введение

Рассмотрим целевую функцию задачи F = 6x1-2x2 → max.
Построим прямую, отвечающую значению функции F = 0: F = 6x1-2x2 = 0. Вектор-градиент, составленный из коэффициентов целевой функции, указывает направление максимизации F(X). Начало вектора – точка (0; 0), конец – точка (6; -2). Будем двигать эту прямую параллельным образом. Поскольку нас интересует максимальное решение, поэтому двигаем прямую до последнего касания обозначенной области. На графике эта прямая обозначена пунктирной линией.

Фрагмент работы для ознакомления

2. Определение новой базисной переменной.В индексной строке F(x) выбираем максимальный по модулю элемент. В качестве ведущего выберем столбец, соответствующий переменной x4, так как это наибольший коэффициент по модулю.3. Определение новой свободной переменной.Вычислим значения Di по строкам как частное от деления: bi / ai4и из них выберем наименьшее:Следовательно, 3-ая строка является ведущей.Разрешающий элемент равен (20) и находится на пересечении ведущего столбца и ведущей строки.БазисВx1x2x3x4x5x6x7minx5304510210015x67051520501014x7150401015200017.5F(X1)0-6-7.5-10-1500004. Пересчет симплекс-таблицы.Представим расчет каждого элемента в виде таблицы:Bx1x2x3x4x5x6x7150 / 20 = 7.540 / 20 = 210 / 20 = 0.515 / 20 = 0.7520 / 20 = 10 / 20 = 00 / 20 = 01 / 20 = 0.05После преобразований получаем новую таблицу:БазисВx1x2x3x4x5x6x7x515048.5010-0.1x632.5-512.516.25001-0.25x47.520.50.751000.05F(X1)112.52401.250000.751. Проверка критерия оптимальности.Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи.Окончательный вариант симплекс-таблицы:БазисВx1x2x3x4x5x6x7x515048.5010-0.1x632.5-512.516.25001-0.25x47.520.50.751000.05F(X2)112.52401.250000.75Оптимальный план можно записать так:x4 = 7.5F(X) = 15 • 7.5 = 112.5Построим двойственную задачу по следующим правилам.1. Количество переменных в двойственной задаче равно количеству неравенств в исходной.2. Матрица коэффициентов двойственной задачи является транспонированной к матрице коэффициентов исходной.3. Система ограничений двойственной задачи записывается в виде неравенств противоположного смысла неравенствам системы ограничений прямой задачи.Столбец свободных членов исходной задачи является строкой коэффициентов для целевой функции двойственной. Целевая функция в одной задаче максимизируется, в другой минимизируется.Расширенная матрица A.4510230515205704010152015067.510150Транспонированная матрица AT.45406515107.51020151025201530701500Условиям неотрицательности переменных исходной задачи соответствуют неравенства-ограничения двойственной, направленные в другую сторону. И наоборот, неравенствам-ограничениям в исходной соответствуют условия неотрицательности в двойственной.Неравенства, соединенные стрелочками (↔), называются сопряженными.Решение двойственной задачи дает оптимальную систему оценок ресурсов.Выясним экономический смысл двойственной задачи. Заметим, что каждое слагаемое в левой части ограничений должно измеряться в тех же единицах, что и правая.Целевая функция в двойственной задаче определяет стоимость запасов всех ресурсов.Левая часть ограничений определяет стоимость ресурсов в теневых (альтернативных) ценах, затраченных на xj.4y1+5y2+40y3≥65y1+15y2+10y3≥7.510y1+20y2+15y3≥102y1+5y2+20y3≥1530y1+70y2+150y3 → miny1 ≥ 0y2 ≥ 0y3 ≥ 0Исходная задача IДвойственная задача IIx1 ≥ 0↔4y1+5y2+40y3≥6x2 ≥ 0↔5y1+15y2+10y3≥7.5x3 ≥ 0↔10y1+20y2+15y3≥10x4 ≥ 0↔2y1+5y2+20y3≥156x1+7.5x2+10x3+15x4 → max↔30y1+70y2+150y3 → min4x1+5x2+10x3+2x4≤30↔y1 ≥ 05x1+15x2+20x3+5x4≤70↔y2 ≥ 040x1+10x2+15x3+20x4≤150↔y3 ≥ 0Переменные yj называются допустимым решением двойственной задачи. Переменные yj называются оптимальными, если они допустимые и на них целевая функция достигает минимальное значения.Используя последнюю итерацию прямой задачи найдем, оптимальный план двойственной задачи.Из первой теоремы двойственности следует, что Y = C*A-1.Составим матрицу A из компонентов векторов, входящих в оптимальный базис.A(a5, a6, a4) =1020150020Определив обратную матрицу D = А-1 через алгебраические дополнения, получим:D = A-1 =10-0,101-0,25000,05Как видно из последнего плана симплексной таблицы, обратная матрица A-1 расположена в столбцах дополнительных переменных .Тогда Y = C*A-1 = (0, 0, 15) x10-0,101-0,25000,05= (0;0;0,75)Оптимальный план двойственной задачи равен:y1 = 0y2 = 0y3 = 0.75Z(Y) = 30*0+70*0+150*0.75 = 112.5Критерий оптимальности полученного решения. Если существуют такие допустимые решения X и Y прямой и двойственной задач, для которых выполняется равенство целевых функций F(x) = Z(y), то эти решения X и Y являются оптимальными решениями прямой и двойственной задач соответственно.Задача 3Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов1234Запасы151197100263189033524160Потребности907011080Проверим необходимое и достаточное условие разрешимости задачи.∑a = 100 + 90 + 160 = 350∑b = 90 + 70 + 110 + 80 = 350Условие баланса соблюдается. Запасы равны потребностям. Следовательно, модель транспортной задачи является закрытой.Занесем исходные данные в распределительную таблицу.1234Запасы151197100263189033524160Потребности907011080Этап I. Поиск первого опорного плана.1. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую, и в клетку, которая ей соответствует, помещают меньшее из чисел ai, или bj.Затем, из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя.Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены.1234Запасы1511[70]97[30]1002631[90]89033[90]52[20]4[50]160Потребности907011080В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи.2. Подсчитаем число занятых клеток таблицы, их 6, а должно быть m + n - 1 = 6. Следовательно, опорный план является невырожденным.Значение целевой функции для этого опорного плана равно:F(x) = 11*70 + 7*30 + 1*90 + 3*90 + 2*20 + 4*50 = 1580Этап II. Улучшение опорного плана.Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.

Список литературы

.Бережная Е.В. Математические методы моделирования экономических систем: Учеб. пособие для вузов/ Е.В. Бережная, В.И. Бережной. – М.: Финансы и статистика, 2003. – 364с.: табл.
2.Лихтенштейн В.Е. Экономико-математическое моделирование: Учеб. пособие/ В.Е. Лихтенштейн, В.И. Павлов; Ин-т экономики, управления и права. Фак. управления. – М.: ПРИОР, 2001. – 448с.: ил, табл.
Очень похожие работы
Пожалуйста, внимательно изучайте содержание и фрагменты работы. Деньги за приобретённые готовые работы по причине несоответствия данной работы вашим требованиям или её уникальности не возвращаются.
* Категория работы носит оценочный характер в соответствии с качественными и количественными параметрами предоставляемого материала. Данный материал ни целиком, ни любая из его частей не является готовым научным трудом, выпускной квалификационной работой, научным докладом или иной работой, предусмотренной государственной системой научной аттестации или необходимой для прохождения промежуточной или итоговой аттестации. Данный материал представляет собой субъективный результат обработки, структурирования и форматирования собранной его автором информации и предназначен, прежде всего, для использования в качестве источника для самостоятельной подготовки работы указанной тематики.
bmt: 0.01014
© Рефератбанк, 2002 - 2024