По выполнению практических работ по

МДК.01.01 ЭКСПЛУАТАЦИЯ ИНФОРМАЦИОННОЙ СИСТЕМЫ

Раздел 1. АНАЛИЗ ИНФОРМАЦИОННЫХ СИСТЕМ

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

Информационные системы (по отраслям)»

Санкт-Петербург

ПРАКТИЧЕСКАЯ РАБОТА №1

МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ. РЕШЕНИЕ ОПТИМИЗАЦИОННЫХ ЗАДАЧ

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

Содержание работы:

· Изучить методы решения оптимизационных задач

· Решить задачи методами линейного программирования

· Написать отчет о проделанной работе

· Ответить на контрольные вопросы

Основные понятия теории оптимизации. Геометрическая интерпретация задач оптимизации.

Задачами оптимизации называют задачи отыскания точек минимума и максимума функций, заданных на множествах.

Общая задача теории оптимизации может быть сформулирована следующим образом:

Дана система неравенств и уравнений с переменными

по выполнению практических работ по - student2.ru (1.1)

и функция по выполнению практических работ по - student2.ru

В области решений системы (1.1) требуется найти такое решение, при котором функция z принимает наибольшее (наименьшее) значение, т.е.

по выполнению практических работ по - student2.ru

Функция z называется целевой функцией, а условия (1.1) ограничениями. Если ограничения (1.1) отсутствуют, то такая задача называется задачей безусловной оптимизации.

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

Если функции gi(x1,…,xn) и fi(x1,…,xn) являются линейными, то общая задача называется линейной. Если хотя бы одна из указанных функций не линейна, то задача называется нелинейной.

В качестве примера рассмотрим линейную задачу

по выполнению практических работ по - student2.ru

по выполнению практических работ по - student2.ru (1.2)

Область решений системы (1.2) представляет собой гипермногогранник (полиэдр) в n–мерном пространстве, а уравнение по выполнению практических работ по - student2.ru задает в этом пространстве гиперплоскость. Если n=2 то решение системы (1.2) есть плоский многогранник, а целевая функция описывает прямую на плоскости. В случае n=3, решение системы (1.2) образует многогранник в пространстве. При этом α=f(x1, x2, x3) задает плоскость в этом пространстве

Пример: Предприятие выпускает два вида продукции Изделие 1 и Изделие 2. На изготовление единицы Изделия 1 требуется затратить а11 кг сырья первого типа, а21 кг сырья второго типа, а31 кг сырья третьего типа. На изготовление единицы Изделия 2 требуется затратить а12 кг сырья первого типа, а22 кг сырья второго типа, а32 кг сырья третьего типа.

Производство обеспечено сырьем каждого типа в количестве b1кг, b2кг, b3кг соответственно.

Рыночная цена единицы Изделия 1 составляет c1тыс. руб., а единицы Изделия 2 c2тыс.руб.

Требуется:

1) построить экономико -математическую модель задачи;

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

3) составить план производства изделий, обеспечивающий максимальную выручку от их реализации при помощи табличного симплекс – метода решения задачи линейного программирования, используя надстройку «Поиск решения» в среде MS Excel

по выполнению практических работ по - student2.ru

Решение задачи

1) Математическая модель задачи

Переменные задачи:

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

x1– количество изделий вида 1;

x2- количество изделий вида 2.

Целевая функция.

Критерием эффективности служит параметр прибыли, который должен cтремиться к максимуму. Для расчета величины прибыли от реализации изделий, необходимо знать:

· Выпускаемое количество изделий каждого вида, т.е. x1 и x2;

· Прибыль от реализации согласно условию, соответственно 55 и 35 тыс.руб.

Таким образом, прибыль от реализации выпускаемых изделий вида 1 составит 55х1 тыс.руб., а от реализации изделий вида 2 составит 35х2 тыс.руб. Поэтому целевая функция прибыли от продажи каждого вида изделий примет вид

по выполнению практических работ по - student2.ru

Ограничения:

Возможное оптимальное количество изделий каждого вида ограничивается следующими условиями:

- Заданными ресурсами 1,2,3, которые используются на выпуск каждого вида изделия, не могут превышать общего запаса ресурсов;

- Количество каждого вида изделия не может быть отрицательным.

Запишем эти ограничения в математической форме:

По расходу ресурса 1: по выполнению практических работ по - student2.ru

По расходу ресурса 2: по выполнению практических работ по - student2.ru

По расходу ресурса 3: по выполнению практических работ по - student2.ru

Неотрицательность количества выпускаемых изделий:

по выполнению практических работ по - student2.ru ,

по выполнению практических работ по - student2.ru

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

по выполнению практических работ по - student2.ru

по выполнению практических работ по - student2.ru

по выполнению практических работ по - student2.ru

по выполнению практических работ по - student2.ru

по выполнению практических работ по - student2.ru

по выполнению практических работ по - student2.ru

Так как переменные задачи x1 и x2 входят в целевую линейную функцию и ограничения задачи линейны, то соответствующая задача оптимизации – задача линейного программирования.

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

1. по выполнению практических работ по - student2.ru . Построим разделяющую прямую на плоскости по выполнению практических работ по - student2.ru . Для этого найдем две точки, через которые она проходит:

x1
x2

Подставим точку (0;0) в неравенство по выполнению практических работ по - student2.ru и проверим условие. Если условие соблюдается, указать стрелками направление на полуплоскость к нулю. Если нет, в противоположную сторону.

2. по выполнению практических работ по - student2.ru . Построим разделяющую прямую на плоскости по выполнению практических работ по - student2.ru . Для этого найдем две точки, через которые она проходит:

x1
x2

Подставим точку (0;0) в неравенство по выполнению практических работ по - student2.ru и проверим условие. Если условие соблюдается, указать стрелками направление на полуплоскость к нулю. Если нет, в противоположную сторону.

3. по выполнению практических работ по - student2.ru . Построим разделяющую прямую на плоскости по выполнению практических работ по - student2.ru . Для этого найдем две точки, через которые она проходит:

x1 66,4
x2

Подставим точку (0;0) в неравенство по выполнению практических работ по - student2.ru и проверим условие. Если условие соблюдается, указать стрелками направление на полуплоскость к нулю. Если нет, в противоположную сторону

4. Найдем многоугольник, в котором пересекаются и накладываются друг на друга все построенные полуплоскости. Многоугольник допустимых решений заштриховывается (рис.1).

по выполнению практических работ по - student2.ru

Рис.1

5. Построим градиент и линию уровня функции цели: по выполнению практических работ по - student2.ru . Градиент всегда изображается с началом в точке (0;0). Любая линия уровня перпендикулярна градиенту. Удобно построить линию уровня z=0, а также проходящую через начало координат по выполнению практических работ по - student2.ru

6. Перемещаем мысленно или с помощью линейки линию уровня так, чтобы найти угловые точки многоугольника допустимых планов, координаты которых определяют максимальное значение функции цели. В данной задаче линия уровня перемещается в направлении за градиентом, поэтому её значения будут увеличиваться от линии к линии. Следовательно, в точке А будет наибольшее значение. Найдём координаты точки А, как точки пересечения разделяющих прямых. Аmax (58;42), Zmax(55;35) = 55*58+35*42 = 4660

Ответ: изделий вида 1 необходимо выпускать в количестве 58 единиц, а изделий вида 2 в количестве 42 единиц.

Задание для самостоятельного решения:Решить графическим методом задачу линейного программирования

по выполнению практических работ по - student2.ru

по выполнению практических работ по - student2.ru

№ вар a b c № вар a b c № вар a b c

Наши рекомендации