Формирование исходных данных к практическим задачам

Условия задач одинаковы для всех студентов, однако числовые данные задач (№ варианта) зависят от № зачетной книжки (шифра) студента, выполняющего работу.

Для получения числовых данных для условий задач своего варианта (m и n) необходимо взять две последние цифры своей зачетной книжки (А – предпоследняя цифра, В – последняя цифра) и выбрать из таблицы 2 параметр m, а из таблицы 3 – параметр n. Эти два числа нужно подставить в условие задачи.

Таблица 2 (выбор параметра m)

А
m

Таблица 3 (выбор параметра n)

B
n

Например, если шифр студента ЭКР-2010-404, то А=0, В=4, тогда из таблиц находим, что m=4, n=5. Полученные m=4 и n=5 подставляются в условия задач контрольной работы этого студента.

Задача линейного программирования

Предприятие планирует выпуск двух видов продукции I и II, на производство которых расходуется три вида сырья А, В и С. Потребность a_ij i-го вида сырья для производства каждой единицы j-го вида продукции, запас b_i соответствующего вида сырья и прибыль c_j от реализации единицы j-го вида продукции заданы таблицей:

Виды сырья	Виды продукции	Запасы сырья
I	II
A	a11 = n	a12 = 2	b1 = mn +5n
B	a21 = 1	a22 = 1	b2 = m + n +3
C	a31 = 2	a32 = m + 1	b3 = mn + 4m + n + 4
прибыль	c1 = m +2	c2 = n + 2
план (ед.)	x1	x2

1. Для производства двух видов продукции I и II с планом x₁ и x₂ единиц составить математическую модель, т.е. целевую функцию прибыли F и соответствующую систему ограничений по запасам сырья, предполагая, что требуется изготовить в сумме не менее n единиц обоих видов продукции.

2. Найти оптимальный план X* = (x₁, x₂) производства продукции, обеспечивающий максимальную прибыль F_max. Определить остатки каждого вида сырья. Задачу решить симплекс-методом.

3. Построить по полученной системе ограничений многоугольник допустимых решений и найти оптимальный план производства геометрическим методом. Определить максимальную прибыль F_max.

4. Составить математическую модель двойственной задачи (систему ограничений по единичной прибыли и целевую функцию общих издержек на сырье Z); найти оптимальный набор цен на сырьё Y*=(y₁, y₂, y₃), обеспечивающий минимум общих затрат на сырье Z_min.

5. Провести анализ первоначальных и дополнительных переменных исходной и двойственной задач, сделать выводы.

6. Решить задачу оптимизации в MS Excel в режиме «поиск решения». Провести исследование полученного решения, используя отчеты по результатам, по устойчивости, по пределам; сделать выводы. Ответы, полученные в результате решений «вручную» и с помощью Excel, должны совпадать.

Решение типовой задачи с использованием Excel представлено в Приложении B.

Транспортная задача

На трех складах А₁, А₂ и А₃ хранится а₁=100, а₂=200, а₃=60+10n единиц одного и того же груза, соответственно. Этот груз требуется доставить трем потребителям В₁, В₂ и В₃, заказы которых b₁=190, b₂=120, b₃=10m единиц груза, соответственно. Стоимости перевозок c_ij единицы груза с i-го склада j-му потребителю указаны в соответствующих клетках транспортной таблицы:

Потребности Запасы	В1	В2	В3
b1=190	b2=120	b3=10m
А1	а1 = 100			m
А2	а2 = 200	n
А3	а3 = 60 + 10n		m + 1

1. Сравнивая суммарный запас и суммарную потребность

в грузе, установить, является ли модель транспортной задачи открытой или закрытой. Если модель открытая, то ее необходимо закрыть, добавив фиктивный склад А₄ с запасом а₄=b-а в случае а<b или фиктивного потребителя В₄ с потребностью b₄=a-b в случае а>b и положив соответствующие им тарифы перевозок нулевыми.

2. Составить первоначальный план перевозок методом северо-западного угла и методом наименьшей стоимости.

3. Методом потенциалов проверить первоначальный план перевозок на оптимальность в смысле суммарной стоимости перевозок, и если это не так, то составить оптимальный план

,

обеспечивающий минимальную стоимость перевозок . Найти эту стоимость.

4. Решить задачу в MS Excel в режиме «поиск решения». Ответы (значения стоимости перевозок), полученные в результате решений «вручную» и с помощью Excel, должны совпадать. Оптимальные планы перевозок могут не совпадать.

Решение типовой задачи с использованием Excel см. в Приложении С.

Приложение А

Пермский институт (филиал)

ФГБОУ ВПО «Российский государственный экономический университет им. Плеханова»

Кафедра информационных технологий и математики

Контрольная работа

по дисциплине:

«Методы оптимальных решений»

на тему:

«Численные методы поиска стационарных точек в оптимизационных задачах: градиентные методы»

Вариант 5(m=4, n=5)

Выполнила:

студентка группы Экз-31

Суханова Любовь Сергеевна

№ зач. кн. ….04

Проверил:

О.Ю. Вшивков

Пермь-2016

Приложение B

Применение MS Excel при решении задач оптимизации (поиск решения)

1. Составление плана выгодного производства

Постановка задачи

Предприятие производит 3 вида продукции А, В и С. Для их изготовления используются три вида ресурсов Р1, Р2, Р3, объемы которых ограничены. Известны потребности в ресурсах для выпуска единицы каждого j-го вида продукции («ресурсные коэффициенты» или «нормы расхода сырья на производство единицы продукции» r_ij). Ресурсные коэффициенты для каждого вида продукции приведены в табл.1.

Известна прибыль, получаемая от реализации единицы каждого j-го вида продукции (единичная прибыль c_j). Реализация единицы продукции А дает прибыль c₁=60 $, продукции В — c₂=70 $ и продукции С — c₃=120 $. Заданы также граничные значения объемов выпуска каждого вида продукции (верхняя и нижняя границы). Виды продукции В и С можно производить неограниченно в любом количестве (верхние границы их объемов равны плюс бесконечности).

Необходимо определить оптимальное количество выпуска каждого вида продукции x_j, при котором будет получена максимальная общая прибыль.

Таблица 1

Вид ресурса Рi	ресурсные коэффициенты rij	Запас ресурса (ограничения по ресурсам) bi
Продукция А	Продукция В	Продукция С
Р1
Р2
Р3
Единичная прибыль

Математическую модель задачи представим в виде набора уравнений:

Уравнение для целевой функции:F = Σ c_j x_j → max;

где: c_j - единичная прибыль, целевые коэффициенты; x_j – объемы производства, независимые переменные.

Для рассматриваемой задачи уравнение будет иметь вид:

(Итоговая общая прибыль)=(Общая прибыль по А)+(Общая прибыль по В)+(Общая прибыль по С) → max

Здесь: (Общая прибыль по А) = (единичная прибыль от А) * (объем производства А)

(Общая прибыль по В) = (единичная прибыль от В) * (объем производства В)

(Общая прибыль по С) = (единичная прибыль от С) * (объем производства С)

или, используя данные из таблицы 1, запишем это уравнение в виде:

F = 60·x₁ + 70·x₂ + 120·x₃ → max

Здесь: x₁, x₂, x₃ – объемы производства продукции А, В и С, соответственно.

Целевыми коэффициентами c_j в данном уравнении являются значения единичной прибыли (60, 70, 120).

Ограничения на ресурсы:

(Расход ресурса 1) = (объем производства А) * (норма расхода ресурса 1 на А) + (объем производства В) * (норма расхода ресурса 1 на В) + (объем производства С) * (норма расхода ресурса 1 на С)

или для каждого вида ресурса Р_i:

Р1 = 1 · x₁ + 1 · x₂ + 1 · x₃ ≤ 16

Р2 = 4 · x₁ + 6 · x₂ + 10 · x₃ ≤ 100

Р3 = 6 · x₁ + 5 · x₂ + 4 · x₃ ≤ 110

Ограничения на объемы производства по видам продукции:

1 ≤ x₁ ≤ 4

x₂ ≥ 2

x₃ ≥ 2

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

Порядок решения

1. Создайте электронную расчетную таблицу как на рис.1. Введите в нее исходные данные и формулы в соответствии с условиями задачи.

Расчетные формулы имеют вид:

для ячейки F5: =В5*$В$10+С5*$С$10+D5*$D$10. Скопируйте формулу в ячейки F6, F7.

Для независимых переменных x₁, x₂, x₃ (объемов производства каждого вида продукции) зарезервированы ячейки В10:D10. Решение должно определить оптимальные значения x₁*, x₂*, x₃*, которые будут содержаться в этих ячейках. Так как значения этих переменных пока неизвестны и будут подобраны в процессе решения задания, то ячейки B10:D10 останутся пока пустыми.

Для заполнения 16-й строки (Общая прибыль) в ячейку В16 следует ввести формулу =В8*В10 и скопировать ее для ячеек С16 и D16.

В ячейку Е16 (Итоговая общая прибыль) введите формулу =СУММ(В16:D16).

Необходимо отметить, что простые ограничения на независимые переменные, которые называются «Верхняя граница» и «Нижняя граница», в принципе, могут быть введены в таблицу (В13:D14) так же, как и ограничения на ресурсы. Однако Excel дает возможность вводить простые ограничения непосредственно в процессе решения с помощью диалогового окна Поиск решения. Поэтому пока воздержимся от ввода указанных ограничений в таблицу.

Рис. 1. Исходные данные

2. Активизируйте режим Поиск решения и введите параметры, как на рис. 2.

В качестве целевой ячейки укажите ячейку Е16 (Итоговая общая прибыль) и задайте максимальное значение суммарной прибыли.

В качестве изменяемых ячеек укажите ячейки B10:D10 (Объемы производства по видам продукции А, В, С).

Укажите ограничения на запас ресурсов $F$5:$F$7<=$E$5:$E$7 и простые ограничения на независимые переменные (Объемы производства продукции А, В, С) (рис. 2).

Рис. 2. Задание условий и ограничений для поиска решений

Установите параметры поиска решения как на рис.3. Задайте Линейную модель расчета, ОК.

Рис. 3. Задание параметров поиска решения

Запустите процесс вычислений кнопкой Выполнить. Решение будет как на рис. 4.

Рис. 4. Найденное решение максимизации прибыли при заданных ограничениях

Из полученного решения можно сделать выводы: оптимальный план производства предусматривает выпуск 4,0 ед. продукции А (соответствует верхней границе ограничений по объемам производства), 2,0 ед. продукции В (соответствует нижней границе ограничений по объемам производства) и 7,2 ед. продукции С. Полученная суммарная прибыль при этом составит 1244,0 $. Продукция В является неэффективной для производства. Ресурс Р2 является дефицитным, так как используется полностью. Имеется возможность снизить запас ресурса Р1 на 2,8 ед. или запас ресурса Р3 на 47,2 ед. без сокращения итоговой прибыли.

3. Сохраните созданный документ под именем «План производства».