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

Стр 1 из 11Следующая ⇒

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

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

Б	Н
	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) Предприятие выпускает продукцию, используя те же ресурсы, что и первое предприятие. Первому предлагается предлагается продать все имеющиеся у него ресурсы по следующим ценам: ; и .

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

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

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

Найти вектор , максимизирующий суммарный прирост прибыли

(3.1.)

при условии сохранения двойственных оценок ресурсов и структуры производственной программы (по примеру):

(3.2.)

- оптимальный план исходной задачи

- коэффициенты при дополнительных переменных

Решение

Пусть – вектор дополнительных объемов ресурсов. Для решения будут использоваться найденные ранее двойственные оценки, следовательно, должно выполняться равенство:

(3.4.)

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

Для дальнейшего решения неравенства (3.3.) и (3.3.) следует переписать в виде систем:

(3.5.) (3.6.)

Получена задача линейного программирования: максимизировать функцию (3.1.) при условиях (3.5.), (3.6.) и (3.4.).

Т.к. задача имеет только две переменные, ее можно решить графически.

Решение

Введем параметр состояния – количество средств, выделяемых нескольким предприятиям, и определим функцию состояния – максимальную прибыль на первых k предприятиях, если они вместе получают руб.

Если из рублей k-е предприятие получит рублей, то каково бы ни было это значение, оставшиеся ( рублей следует распределить между предприятиями от первого до k-го так, чтобы была получена максимальная прибыль . Тогда прибыль k предприятий будет равна . Нужно выбрать такое значение между 0 и чтобы эта сумма была максимальной, и мы переходим к рекуррентному соотношению:

для k = 2, 3, 4, …, n. Если же k = 1, то .

Первым этапом решения задачи является составление таблицы 2. Значения складываются со значениями и на каждой северо-западной диагонали отмечается максимальное значение:

Таблица 2.Второе предприятие



			20*
			33*
			45*
			57*
			67*
			75*
			81*

Отмеченными значениями заполняется таблица 3 и указываются соответствующие значения :

Таблица 3.Второе предприятие

Следующий этап – табулирование функции , (таблица 4) и составление таблицы 5:

Таблица 4.Третье предприятие



20*	33*	45*	57*	67*	75*
					81*

Таблица 5.Третье предприятие

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

200 тыс. руб.

Таблица 6. Четвертое предприятие





							103*

На долю остальных предприятий остается 700 – 200 = 500 тыс. руб. Согласно таблице 5 третьему предприятию должно быть выделено:

0 тыс. руб.

Аналогично находим значение для второго предприятия:

тыс.руб.

На долю первого предприятия остается:

тыс. руб.

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

Максимальный прирост прибыли составит (согласно таблице 1):

тыс. руб.

10. Оптимизация плана распределения ресурсов между производственными подразделениями с помощью двойственных оценок при двухуровневой системе управления.

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

В – объем ресурсов:

А – нормы расходов на единицу продукции каждого вида:

С – удельная прибыль по каждому виду продукции:

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

Предприятие имеет три филиала, каждый из которых производит по два вида продукции, требующей одних и тех же видов ресурсов. Каждая фабрика располагает двумя видами ресурсов (матрицы , суммарные количества которых равны 242 ед. и 185 ед. соответственно.

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

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

Модель задачи:

Найтивекторы (распределение ресурсов между филиалами) и оптимальный план:

)

Максимизирующий целевые функции:

Соответственно, и суммарную прибыль L , при следующих ограничениях:

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

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

Составляем локальные задачи:

(4.1.) (4.2.) ` (4.3.)

Решение задач (4.1.) – (4.3.) с помощью Excel:

Таблица 4.1. Решение локальной задачи (1)

Изделия	Изд1	Изд2	Целевая функция/объем продаж
Цена за единицу
План выпуска

Двойственные оценки

Таблица 4.2.Решение локальной задачи (2)

Изделия	Изд1	Изд2	Целевая функция/объем продаж
Цена за единицу
План выпуска	13, 4		720, 4

Двойственные оценки:

Таблица 4.3.Решение локальный задачи (3)

Изделия	Изд1	Изд2	Целевая функция/объем продаж
Цена за единицу
План выпуска	5, 25		433, 5

Двойственные оценки

Получены следующие оптимальные планы по филиалам:

Максимальные прибыли по каждому филиалу:

Общая прибыль по предприятию:

Двойственные оценки по предприятиям:

Разница между двойственными оценками:

· Для первой пары филиалов составляет 9, 2 ед.;

· Для второй пары филиалов составляет 16, 7 ед.

Разница для второй пары максимально, следовательно, второй и третий филиалы выбираются для перераспределения.

Модель объединенной задачи (задача (2) + задача (3)):

(4.4.)

Решение задачи (4.4.) в Excel

Таблица 4.4. Решение объединенной задачи (4.4.) (2) +(3)

Изделия	Изд1	Изд2	Изд3	Изд4	Целевая функция
Цена за единицу
План выпуска	18, 6			11, 2	1344, 4

Двойственные оценки:

Получено решение:

Переменная , что означает, что первое изделие в третьем филиале выпускать не следует.

Двойственные оценки для объединенной задачи:

Распределение ресурсов принимает следующие значения:

Объем ресурсов в первом филиале остается неизменным.

Прибыль по всему предприятию увеличилась и составляет L = 1344, 5 + 550 = 1894, 5 д. ед.

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

(4.5.)

Решение задачи (4.5.) в Excel

Таблица 4.5. Решение объединенной задачи (4.5.) (1) +(2)

Изделия	Изд1	Изд2	Изд3	Изд4	Целевая функция
Цена за единицу
План выпуска			25, 04	18, 39	1666, 082

Двойственные оценки

Получено решение:

Переменные что означает, что в первом филиал выпускать продукцию второго вида не следует.

Двойственные оценки для объединенной задачи:

Разница между двойственными оценками между вторым и третьим предприятием составляет 4, 9.

Распределение ресурсов принимает следующий вид:

Объем ресурсов в третьем филиале остается неизменным.

Прибыль по всему предприятию увеличилась и составляет L = 1666, 08 + 436, 8 = 2103, 6д. ед..

По решению двух объединенных задач, общая прибыль по предприятию увеличилась на 399, 6 единиц. Продолжая выполнять последовательные шаги оптимизации, мы будем увеличивать суммарную прибыль шаг за шагом. Процесс продолжается до тех пор, пока двойственные оценки задачи не станут примерно одинаковыми.

11. Применение метода динамического программирования для оптимального управления запасами и производством.

В лекциях не было!!! Обещал не давать!

12. Модель экономически выгодных размеров заказываемых партий (модель ЭВРП). Формула Уилсона, характеристическое свойство оптимального размера партии.

В лекциях не было!!! Обещал не давать!

13. Задача формирования оптимального портфеля ценных бумаг. Математическая модель задачи, её решение и анализ.

В лекциях не было!!! Обещал не давать!

Решение

Последняя таблица:

Б	Н
	53, 33	-0, 33	0, 33	0, 00	0, 00	1, 00	0, 33	-1, 00
	33, 33	0, 67	0, 33	0, 00	1, 00	0, 00	0, 33	0, 00
	4, 58	1, 67	0, 08	1, 00	0, 00	0, 00	-0, 42	0, 25
	11175, 00	136, 00	62, 00	0, 00	0, 00	0, 00	55, 00	0, 00

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

И максимальная прибыль составляет ед.

Не выполняется условие целочисленности решения: элементы базисного плана нецелочисленны.

Метод Гомори. Нахождение решения задачи целочисленного программирования методом Гомори начинают с определения симплексным методом оптимального плана задачи без учета целочисленности переменных. После того как этот план найден, просматривают его компоненты. Если среди компонентjd нет дробных чисел, то найденный план является оптимальным планом задачи целочисленного программирования (1)-(3) Если же в оптимальном плане задачи переменная принимает дробное значение, то к системе уравнений (2) добавляют неравенство

(4)

и находят решение задачи (1) – (3), (4).

В неравенстве (4) и – преобразованные исходные величины и , значения которых взяты из последней симплекс–таблицы, а и – дробные части чисел (под дробной частью некоторого числа а понимается наименьшее неотрицательное число b такое, что разность между а и b есть целое). Если в оптимальном плане задачи (1) – (3) дробные значения принимают несколько переменных, то дополнительное неравенство (4) определяется наибольшей дробной частью.

Если в найденном плане задачи (1) – (3), (4) переменные принимают дробные значения, то снова добавляют одно дополнительное ограничение и процесс вычислений повторяют. Проводя конечное число итераций, либо получают оптимальный план задачи целочисленного программирования (1) – (3), либо устанавливают ее неразрешимость.

Метод «ветвей и границ».

Рассмотрим задачу с двумя переменными, вошедшими в базис, и решим ее методом «ветвей и границ» для поиска целочисленного решения.

(1)

(2)

(3)

Системы уравнений (1) и (2) определяют область допустимых значений ОАВС, где координаты вершины В определяют оптимальный план производства.

В = (4, 58; 33, 3)

Переменная в оптимальном плане не является целой, следовательно, относительно нее будет производится ветвление.

Процесс ветвления делит исходную задачу на две подзадачи а) и б). Одна из них отличается добавлением условия , во второй подзадаче добавляется условие . При этом из области ОАВС исключается подобласть .

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

Решение в Excel

(см. №1)

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

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

· ) – частный критерий;

· Если критерии на min, их следует привести к max умножением на -1;

· Критерии следует ранжировать по степени важности для предприятия;

· Назначаются уступки (величина допустимого отклонения .

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

Получено решение:

Переходим к максимизации функции при условиях (8.4) и дополнительном ограничении, учитывающем, что по критерию нельзя уступать более чем на . Так как , то дополнительное ограничение будет иметь вид: 6 (5.6.)

Графическое решение задач (5.2.), (5.4.), (5.5.) представлено на рисунке 6.

Получено решение:

Переходим к максимизации функции при условиях (5.4) и дополнительном ограничении, учитывающем, что по критерию нельзя уступать более чем на . Так как 7, 25, то дополнительное ограничение будет иметь вид: (5.7.)