Вопросы для подготовки к экзамену

по дисциплине “Системный анализ и принятие решений”

для студентов 3 курса, д/о, 2011/2012уч. год

1. Задача линейного программирования, формулировка, математическая модель, алгоритм решения симплексным методом и в Excel. Постоптимизационный анализ решения задачи.

Исходные данные:

• Количество видов изделия n;

• Количество видов ресурсов m;

• Нормы потребления ресурсов на каждый вид изделия:

• Объем ресурсов каждого вида:

• Удельная прибыль при возможном выпуске четырех видов изделий с использованием трех видов продукции: вектор С:

Формулировка задачи:

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

Фабрика располагает тремя видами ресурсов, количество которых определяется вектором В. Известны также нормы расходов ресурсов (матрица А) и прибыль от реализации одного изделия (матрица С).

Требуется составить такой план выпуска изделий, при котором предприятие уложится в имеющиеся ресурсы, а суммарная прибыль будет максимальной.

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

Основные элементы модели оптимизационной задачи:

• Критерий оптимальности (целевая функция);

• Система ограничений;

• Неотрицательность переменных.

Примем следующие обозначения:

• i - номер отдельного вида ресурса: i = (1, 2, … , m);

• j – номер вида изделия: j = (1, 2, … , n);

• – норма ресурсов на изготовление j-го изделия с использованием i-го ресурса;

• – объем i-го ресурса;

• – объем прибыли при производстве j-го изделия;

• - количество планируемых единиц j-го изделия;

• ( - искомый план производства.

Найти производственную программу максимизирующую целевую функцию прибыли:

(1.1.)

при ограничениях по ресурсам:

(1.2.)

и при условии неотрицательности переменных:

(1.3.)

Решение

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

• Задача должна быть классической, т.е. на минимум (максимум);

• Система ограничений должна быть в виде равенств;

• В каждом уравнении должна быть базисная переменная.

=

Алгоритм (на примере):

1. Для решения систему ограничений (1.1.), состоящую из неравенств, следует преобразовать в равенства при помощи дополнительных неотрицательных неизвестных , т.е. заменить ее системой алгебраических уравнений. В целевую функцию также добавляются дополнительные переменные с коэффициентами 0:

(1.3.)

(1.4.)

где дополнительные переменные имеют смысл остатков соответствующих ресурсов. Для них также существует условие неотрицательности:

(1.5.)

Дополнительные переменные с коэффициентом +1  являются базисными.

2. Заполняется начальная симплексная таблица

Таблица 1.1. Исходная симплексная таблица

	Б	Н
0		168,00	3,00	2,00	0,00	3,00	1,00	0,00	0,00	84,00	0,67
0		60,00	0,00	1,00	4,00	2,00	0,00	1,00	0,00	60,00	0,33
0		112,00	1,00	3,00	5,00	0,00	0,00	0,00	1,00	37,33	---
		0,00	-18,00	-19,00	-8,00	-5,00	0,00	0,00	0,00	---	-6,33

– коэффициент целевой функции при базисных переменных;

Б – базисные переменные;

Н – значение базисных переменных;

Двойственные оценки рассчитываются по формуле

3. Выбирается разрешающий столбец по максимальной по величине двойственной оценке (второй столбец)

4. Выбирается разрешающая строка с помощью коэффициента – отношения элементов столбца Н и соответствующих элементов ключевого столбца.

5. Производится перерасчет таблицы по методу Жордано-Гаусса: вычисляется столбец β делением ключевого разрешающего на ключевой элемент, затем из каждой строки вычитается разрешающая строка, умноженная на соответствующий коэффициент β. Сама разрешающая строка делится на ключевой элемент.

6. Заполняется новая симплексная таблица (п.2)

Признак окончания расчетов – значения всех двойственных оценок больше или равны 0 (в задаче на максимум).

Критерий оптимальности в задаче на максимизацию прибыли – отсутствие отрицательных двойственных оценок.

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

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

Решение задачи с помощью программы Excel (на примере)

Предприятие выпускает четыре вида изделий ( ) . Для их изготовления используется три вида ресурсов ( ). Известны нормы расходов ресурсов на единицу продукции каждого вида, цена за единицу продукции и запасы ресурсов.

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

.

2. С помощью функции «Поиск решения» производится решение задачи симплекс-методом. Для этого в окне поиска указать: целевую ячейку (целевая функция), условие максимизации целевой функции, изменяемые ячейки (план выпуска).

3. Ввести ограничения, указанные в условии задачи: суммарные расходы ресурсов не должны превышать заданного объема. Также следует указать условие неотрицательности переменных.

4. Выполнить!

Получен оптимальный план производства

Постиптимизационный анализ:

Из отчетов по пределам и устойчивости можно сделать следующие выводы:

• Какие ресурсы использованы полностью, а для каких имеется резерв;

• При каких изменениях цен оптимальный план выпуска будет оставаться неизменным;

• При каких изменениях объемов ресурсов структура оптимального плана будет неизменной;

• Теневые цены показывают, на сколько изменится прибыль при увеличении объема ресурса.