Студопедия КАТЕГОРИИ: АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция |
Задания для самостоятельного решения1. Построить сетевой график (длина работы - tij ) 2. Выделить критический путь и найти его длину. 3. Определить резервы времени каждого события . 4. Определить резервы времени (полные, частные первого вида, свободные и независимые) всех работ и коэффициенты напряженности работ, не лежащих на критическом пути. 5. Выполнить оптимизацию сетевого графика по времени.
Контрольное задание №3. Модели линейного программирования.
Методические указания Задача линейного программирования (ЗЛП) в произвольной форме имеет следующий вид: Выражение Неравенства и равенства в задаче (3.1) называются ограничениями. Каждое неравенство определяет полупространство, а равенство – плоскость в пространстве переменных (Х1,Х2,…,Хn). Решение задачи (3.1) называется оптимальным решением (или оптимальным планом) и обозначается как Х* = (Х*1, Х*2, …, Х*n). Оптимальные решения лежат на границе области D. Всякая задача на минимум может быть сведена к задаче на максимум и, наоборот, умножением целевой функции на –1. Оптимальный план задачи при этом не изменится, а значение целевой функции изменит знак. После решения надо снова изменить знак целевой функции. (более подробно теорию можно прочитать в методичках – см. прикрепленные файлы). Пример. Необходимо найти месячный оптимальный производственный план предприятия, выпускающего четыре вида продукции (П1, П2, П3, П4). Цены реализации каждого вида продукции известны, и нет ограничения на объемы реализации. В табл. 3.1 даны необходимые для задачи данные: нормативы затрат ресурсов на производство единицы продукции, прибыль от реализации единицы продукции и запасы каждого вида ресурса.
Таблица 3.1
Экономико-математическая модель задачи имеет вид: max Z = 20x1 + 25x2 + 40x3 + 50x4 ; 0,6x1 + x2 + 2x3 + 2,5x4 ≤ 20 ; 3x1 + 5x2 + 2x3 + 3x4 ≤ 50 ; 5x1 + 4x2 + 3x3 + 4x4 ≤ 45 ; x1 , x2 , x3 , x4 ≥ 0 , где переменные (x1, x2, x3, x4) обозначают объемы производства соответствующих видов продукции (тыс.т), Z – выручка от реализации продукции при заданных ценах (20, 25, 40, 50) в тыс.руб. и заданных ограничениях на используемые ресурсы труда, сырья и оборудования (20, 50, 45) в ед. Решение задачи осуществляется при помощи EXCEL с помощью функции «Поиск решения». Необходимо: 1. Определить план выпуска продукции, при котором прибыль от ее реализации будет максимальной. 2. Получить решение двойственной задачи. Пояснить экономический смысл полученных объективно обусловленных (теневых) оценок ресурсов. 3. Найти интервалы устойчивости двойственных оценок по отношению к изменению запаса ресурсов каждого вида. Порядок выполнения задания: 1. Создать формус данными задачи (3.1) (рис. 3.1).
Рис 3.1. Таблица EXCEL решения задачи с помощью функции «Поиск решения» 2. Осуществитьабсолютную адресацию к блоку (диапазону) переменных (Х1, Х2, Х3, Х4), которому надо дать уникальное имя (например «Переменные») (рис. 3.2.). Чтобы не повторять имена, надо щелкнуть по кнопке рядом с полем для ввода имени блока. После этого увидите список имен. Можно щелчком по имени в этом списке переместиться к соответствующему блоку, на каком бы листе книги он не находился.
Рис. 3.2. Ввод наименования диапазона В ячейки, выделенные цветом, надо ввести формулы для вычисления значений прибыли и используемых ресурсов, умножая и складывая диапазон «Переменные» с коэффициентами, находящимися в соответствующих строках. Для этой цели используется функция СУМПРОИЗВ.
3. Вычислить значения прибыли. Выделим ячейку G79 (рис. 3.3), в которую нужно занести расчетное значение прибыли. Нажмем вставку функции (кнопка fx) и далее выберем функцию СУММПРОИЗВ среди математических функций пакета. В качестве первого аргумента выделим указателем диапазон переменных (Х1, Х2, Х3, Х4). Имя блока («Переменные») будет вставлено автоматически. Щелкнем по полю для ввода второго массива и выделим блок ячеек, содержащий значения прибыли. В этом случае в качестве второго аргумента будут вставлены адреса соответствующих ячеек (рис. 3.3). Закончим ввод формулы нажатием на кнопку ОК.
Рис. 1.2 Ввод формулы в ячейку G79 для расчета прибыли. Рис. 3.3. Вычисление значения прибыли Для контроля правильность формулы в диапазон переменных (х1,х2,х3,х4) надо ввести произвольные значения например х1=1, х2=2, тогда в ячейке прибыли должно получиться значение 70.
4. Вычислить значения ресурсов. Чтобы записать формулы для вычисления расчетных значений расхода ресурсов надо скопировать формулу для расчета прибыли в ячейки, предназначенные для расчета ресурсов. Выделим ячейку со значением прибыли и переместим указатель в ее правый нижний угол. Он примет вид перекрестия. (См. рис. 3.4.) Удерживая в нажатом положении левую клавишу мышки, протащим указатель по заполняемым ячейкам. Адреса ячеек со значениями прибыли (строка 79) автоматически будут заменены на адреса ячеек со значениями коэффициентов расхода ресурсов.
Рис. 3.4. Вычисление значений расхода ресурсов
Теперь для любых назначенных нами значений переменных (х1, х2, х3, х4) (в нашем случае х1=1, х2=2) в соответствующих ячейках можно видеть значения прибыли и объемы затраченных ресурсов.
5. Решить задачу оптимизации. В пункте меню Сервис выберите команду «Поиск решения». В поле Установить целевую ячейку команды «Поиск решения» выделите ячейку со значением целевой функции модели (рис. 3.5.)Чтобы максимизировать (минимизировать) значение целевой ячейки, установите соответствующее положение переключателя (см. рис. 3.5.) В поле Изменение ячейки введите имена или адреса переменных модели, выделяя блок этих ячеек («Переменные»). Имя «Переменные» блока будет вставлено автоматически.
Рис. 3.5. Использование команды Поиск решения.
Щелкните по полю Ограничения, после чего введите ограничения, накладываемые на решение задачи. Для этого нажмите кнопку Добавить. В поле Ссылка на ячейку выберите ячейку или диапазон ячеек на значения которых накладываются ограничения. (рис. 3.6). В примере левые части ограничений это – блок ячеек $G$80:$G$82, а правые части ограничений соответственно $I$80:$I$82.
Рис. 3.6. Ввод ограничений при нажатии кнопки Добавить
Для ограничений одного вида при вводе левых и правых частей можно ввести сразу весь диапазон, выделяя соответствующие ячейки. Выберите требуемый вид ограничения (<=, =, >=, цел., двоич.) из раскрывающегося списка, который находится между ссылкой и ограничением. (Если выбрано "цел." или "двоич.", в поле Ограничение появятся значения типа "целого" или "двоичного" типа. Последнее означает, что результат может быть только нулем или единицей). В поле для величины ограничения можно вводить и число, но тогда не так удобно анализировать модель на экране. Чтобы ввести ограничение и приступить к набору нового, нажмите кнопку Добавить, а чтобы вернуться в диалоговое окно Поиск решения, нажмите кнопку OK. В окне Параметры поиска решения (рис. 3.7) для решения линейных задач надо установить флажки Линейная модель и Неотрицательные значения. Остальные величины, которые определяют точность и сходимость решения, как правило, нет необходимости изменять.
Рис. 3.7. Ввод параметров поиска решения
Нажмем кнопку OK и вернемся в окно команды Поиск решения. Затем нажмем кнопку Выполнить, и, если все сделано правильно, то в таблице данных получим результаты решения задачи. (рис. 3.8.), где можно задать тип отчета.
Рис. 1.6. Результаты поиска решения.
Рис. 3.8. Результаты решения задачи и выбор типа отчета Оптимальный план задачи (х1*= 0, х2*= 6, х3*= 7, х4*= 0) единиц. Максимальная прибыль равна 430 ед. Ресурсы использованы следующим образом: труд полностью– 20 ед., сырье не полностью – 44 ед., оборудование – полностью – 45 ед. Анализ устойчивости решения Рассмотрим отчет по устойчивости (cм. таб. 3.2). Этот отчет содержит сведения о чувствительности решения к малым изменениям в формуле для целевой функции и в формулах ограничений. Поясним смысл столбцов табл. 3.2. Таблица 3.2.
Нормированная стоимость показывает изменение целевой функции при увеличении соответствующей переменной на единицу. Например, если ввести x4 = 1, то x2 и x3 станут меньше, а величина целевой функции изменится на -0,5. Допустимое увеличение и уменьшение определяют интервал изменений коэффициентов целевой функции, внутри которого сохраняются значения переменных оптимального плана. В разделе отчета «Ограничения» теневые цены это двойственные оценки ресурсов, а Допустимое увеличение и уменьшение показывают допустимые диапазоны изменения правых частей ограничений, в пределах которых в оптимальный план входят те же переменные, хотя возможно и с другими значениями. Любое увеличение ресурса сырья, поскольку этот ресурс недефицитный, (величина 1Е+30 выполняет роль бесконечности), не влияет на оптимальный план, однако уменьшение этого ресурса более чем на 6 единиц приведет к изменению структуры решения. При увеличении ресурса труда в оптимальном плане будет возрастать переменная Х3 и убывать Х2, но если прирост превысит 10 ед., то останется только переменная Х3. А при уменьшении ресурса труда более чем на 4,29 в оптимальный план войдет переменная Х1. |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
Последнее изменение этой страницы: 2018-04-12; просмотров: 248. stydopedya.ru не претендует на авторское право материалов, которые вылажены, но предоставляет бесплатный доступ к ним. В случае нарушения авторского права или персональных данных напишите сюда... |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
(3.1)
называется целевой функцией (или критерием) задачи, величины (Х1,Х2,…,Хn) – переменные задачи. Система неравенств в задаче (3.1) определяет область допустимых значений (планов) задачи D, которая имеет форму выпуклого многогранника.
