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

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

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

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

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

 

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

 

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

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

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

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

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

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

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

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

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

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

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

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

(1.1)

и функция

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

 

 

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

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

Если функции g_i(x₁,…,x_n) и f_i(x₁,…,x_n) являются линейными, то общая задача называется линейной. Если хотя бы одна из указанных функций не линейна, то задача называется нелинейной.

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

(1.2)

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

Пример: Предприятие выпускает два вида продукции Изделие 1 и Изделие 2. На изготовление единицы Изделия 1 требуется затратить а₁₁ кг сырья первого типа, а₂₁ кг сырья второго типа, а₃₁ кг сырья третьего типа. На изготовление единицы Изделия 2 требуется затратить а₁₂ кг сырья первого типа, а₂₂ кг сырья второго типа, а₃₂ кг сырья третьего типа.

Производство обеспечено сырьем каждого типа в количестве b ₁кг, b ₂кг, b ₃кг соответственно.

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

Требуется:

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

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

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

 

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

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

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

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

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

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

 

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

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

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

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

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

 

 

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

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

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

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

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

По расходу ресурса 1:

По расходу ресурса 2:

По расходу ресурса 3:

 

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

,

 

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

 

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

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

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

x 1
x 2

 

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

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

x 1
x 2

 

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

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

 

x 1		66,4
x 2

 

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

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

 

Рис.1

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

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

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

 

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

 

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