Образовательная программа: Вычислительная техника и программное обеспечение 8D06104

IV. Идти к II. Пример решения задачи линейного программирования симплексным методом

жүктеу/скачать 221,11 Kb.

бет	9/9
Дата	23.10.2023
өлшемі	221,11 Kb.
	#120740
түрі	Образовательная программа

1 2 3 4 5 6 7 8 9

Байланысты:
Лекция 6. Математическая модель ЛП. Часть 1

Таблица 2. Исходные данные для решения задачи ЗЛП
Обзорные вопросы
Список использованных источников

IV. Идти к II.

Пример решения задачи линейного программирования симплексным методом.
Механический завод выпускает продукцию видов А, Б и В. Общий выпуск продукции не должен превышать 2000 ед. На производство продукции расходуются ресурсы двух видов. Объем первого вида ресурса составляет 15000 ед., второго – 20000 ед.
В таблице 2 представлены нормативы затрат ресурсов и прибыль от продажи единицы продукции.
Таблица 2. Исходные данные для решения задачи ЗЛП

Затраты ресурсов на 1 продукции, ед.							Прибыль от продажи 1 продукции, д.ед.
Ресурс 1			Ресурс 2
А	Б	В		А	Б	В		А	Б	В
5	4	1		3	2	1		80	40	50

Определить оптимальную производственную программу предприятия, которая приносила бы максимум прибыли.

Решение
Обозначение переменных:
х₁ – выпуск продукции А, ед.;
х₂– выпуск продукции Б, ед.;
х₃ – выпуск продукции В, ед.
Приведем к канонической форме модели: неравенства преобразуем в уравнения, добавив в левую часть дополнительные переменные х₄, х₅, х₆:
1) х₁+ х₂ + х₃ + х₄= 2000;
2) 5х₁ + 4х₂ + х₃ + х₅ = 15000;
3) 3х₁ + 2х₂ + х₃ + х₆= 20000,
где х₄ – недостижение выпуска продукции до заданной границы, ед.;
х₅– остаток 1 ресурса, ед.;
х₆ – остаток 2 ресурса, ед.
Полученный план перенесем в симплексную таблицу и проверим на оптимальность (таблица 3).
Таблица 3. Симплексная таблица

Базисные переменные	Свободные члены (b_i)	Основные переменные			Дополнительные переменные			Симплексные отношения (b_i/a_ij*)
Базисные переменные	Свободные члены (b_i)	х₁	х₂	х₃	х₄	х₅	х₆	Симплексные отношения (b_i/a_ij*)
х₄	2000	1	1	1	1	0	0	2000:1=2000
х₅	15000	5	4	1	0	1	0	15000:5=3000
х₆	20000	3	2	1	0	0	1	20000:3=6667
Z	0	-80*	-40*	-50	0	0	0
х₁	2000	1	1	1	1	0	0	начальная
х₅	5000	0	-1	-4	-5	1	0
х₆	14000	0	-1	-2	-3	0	1
Z	160000	0	40	30	80	0	0

Ответ
План оптимален, т.к. в строке целевой функции Z нет отрицательных коэффициентов.
Предприятию выгодно выпускать продукцию А в количестве 2000 ед. Продукцию Б и В выпускать не выгодно, т.к. х₂ = 0, х₃ = 0.
Выпуск продукции соответствует максимально возможному объему выпуска (х₄ = 0).
Остаток 1-го ресурса составляет 5000 ед. (х₅ = 5000 ед.).
Остаток 2-го ресурса составляет 14000 ед. (х₆ = 14000 ед.). При выполнении данного оптимального плана прибыль будет максимальной и составит 160000 д. ед.
Обзорные вопросы

Какой метод решения задач ЛП является одним из наиболее распространенных?
Что называется опорным решением в симплексном методе?
Сколько главных шагов содержит алгоритм симплексного метода?

Список использованных источников

1. Акулич И.Л. Математическое программирование в примерах и задачах. Лань, 2011. 352 с.

2. Карманов В. Г. Математическое программирование: Учеб. пособие. — 5-е изд., стереотип. — М.: ФИЗМАТЛИТ, 2004. — 264 с.
3. Блюмин С.Л., Шуйкова И.А. "Модели и методы принятия решения в условиях неопределенности. - Липецк:ЛЭГИ, 2001
4. Алтунин А.Е., Семухин М.В. Модели и алгоритмы принятия решений в нечетких условиях. – Тюмень: Изд-во ТюмГУ, 2000.
5. Перепелица В.А., Попова Е.В. Математические модели и методы оценки рисков экономических, социальных и аграрных процессов. – Ростов н/Д.: Изд-во Рост. ун-та, 2002.

жүктеу/скачать 221,11 Kb.

Достарыңызбен бөлісу:

1 2 3 4 5 6 7 8 9