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

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

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

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

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

 

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

· 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. Исходная симплексная таблица

	Б	Н
		168, 00	3, 00	2, 00	0, 00	3, 00	1, 00	0, 00	0, 00	84, 00	0, 67
		60, 00	0, 00	1, 00	4, 00	2, 00	0, 00	1, 00	0, 00	60, 00	0, 33
		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. Выполнить!

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

 

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

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

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

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

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

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

 

 

2. Двойственность в линейном программировании. Симметричная пара двойствен­ных задач, правила составления, их экономическое содержание.

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

 

 

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

(См. №1) Предприятие выпускает продукцию, используя те же ресурсы, что и первое предприятие. Первому предлагается предлагается продать все имеющиеся у него ресурсы по следующим ценам: ; и .

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

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

 

⇐ Предыдущая12345678910Следующая ⇒

Поделиться:

Популярное:

1. I. Иммунология. Определение, задачи, методы. История развитии иммунологии.
2. I. Цели и задачи библиотеки на 2015 год
3. II. 36. Основные задачи семеноводства.
4. II. ЦЕЛИ, ЗАДАЧИ И ВИДЫ ДЕЯТЕЛЬНОСТИ ОРГАНИЗАЦИИ.
5. V1: Предмет, цели и задачи товароведения
6. VII. Задачи научного руководителя дипломной работы
7. Алгоритм Симплекс-метода для решения задачи линейного программирования об оптимальном использовании ресурсов.
8. Аттестация государственных служащих: понятие, цели, задачи, функции, принципы.
9. Блок-схема алгоритма решения задачи
10. Бубновый Валет» . Представители, задачи, организации.
11. Введение и постановка задачи
12. Виды взаимосвязей, изучаемы в с. Задачи корреляционного анализа.