Симплекс метод с искусственным базисом

Размещено на http://www.allbest.ru/

Симплекс метод с искусственным базисом

Объектом исследования настоящей работы является планирование производства изделий на определенный плановый период, предприятия «XXX» в г. Холмск. Предметом исследования является изготовление на определённый плановый период времени разнообразные виды изделий.

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

Для предметного представления результатов исследования решим задачу о планировании производства предприятия «XXX».

Производственному секторунамечено к изготовлению на определённый плановый период времени два вида изделий: C и Z. На производство единицы изделия Cпервого типа используется 1ч., оборудование второго типа используется 4 ч. На производство единицы изделия Z оборудование первого типа используется 2 ч., оборудование второго типа - 2 ч.

Фонд полезного времени первого типа оборудования составляет 120 ч. второго типа оборудования - 240 ч. Отпускная цена единицы изделия C составляет 4 руб., а изделия Z - 6 руб. Спланировать выпуск изделий C и Z при условии, что план должен быть выполнен в стоимостном выражении на сумму не менее 320 рублей, и оборудование первого типа должно быть загружено минимально. Решить задачу графическим и симплексным методом с искусственным базисом.

Построение математической модели задачи. Преобразуем данные задачи в таблицу:

Таблица 1- Данные задачи «Планирование производства»

Система, учитывающая все поставленные условия, имеет следующий вид:

Симплексный метод применяется при решении задач линейного программирования, заданных в канонической форме.

Задачу линейного программирования будем считать приведённой к каноническому виду, если:

- система ограничений содержит только равенства;

- правые части системы ограничений положительны.

Приведём задачу к канонической форме:

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

Сведём данные в 1-й блок таблицы Гаусса (в столбце стоят коэффициенты базисных переменных целевой функции):

Таблица 2- Сведенные данные задачи в таблице Гаусса

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

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

Для этого вычислим индексы:

Здесь возможны три:

-все оценки в индексной строке неположительны - значит полученный план будет оптимален;

- среди оценок есть хотя бы одна положительная, и в столбце над ней есть хотя бы один положительный коэффициент - план не являетсяоптимальным, но возможно его улучшение;

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

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

Ведущий столбец в случае задачи на минимум определяется по самой большой оценке в строке индексов и указывает на то, какая переменная будет вводиться в новый базис. В данном случае ведущий столбец и в новый базис вводится переменная . Ведущая строка определится по самой наименьшей величине и указывает, какая базисная переменная выводится из базиса. В данном случае ведущая строка и из базиса выводится переменная . Итак, определены ведущий столбец и ведущая строка

Переходим к новому базису и составляем для него новую симплекс-таблицу.

Таблица 3- Симплекс-таблица для нового базиса

В результате преобразований на месте ведущего столбца новой симплекс-таблицы получен единичный столбец.

Построим новый опорный план:

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

Вычисляем индексы:

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

Таблица 4- Новый опорный план

Опорный план:

Проверим полученный опорный план на оптимальность. Вычислим индексы:

Опорный план, составленный по последней симплекс-таблице, является оптимальным, т.к. оценки в строке индексов все отрицательны и равны 0.

Если в результате решения задачи с искусственным базисом:

- получено оптимальное решение, в котором все искусственные переменные равны нулю, то исходная задача также имеет оптимальное решение, которое получается из оптимального решения -задачи путём отбрасывания всех искусственных переменных;

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

- установлено, что -задача решений не имеет, то исходная задача также решений не имеет, так как есть неограниченность целевой функции.

Найдено решение, оптимальное с точки зрения минимизации целевой функции в имеющихся условиях:

( план производства изделия A, ед.)

( план производства изделия B , ед.)

при этом

(минимально возможная загрузка оборудования 1-го типа при данных условиях, ч)

Прибыль от реализации созданных изделий составит руб.

Вывод:

50 - план производства изделия C (ед.),

20 - план производства изделия Z (ед.);

90 - загрузка оборудования 1-го типа (ч);

320 - прибыль при выполненном плане (руб.).

Рассмотрим графическое решение задачи, а за одно осуществим проверку.

Найдём геометрически наименьшее значение линейной функции в области, заданной системой неравенств

или

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

Прямая 1 Прямая 2 Прямая 3

Запишем её уравнение нулевой линии уровня целевой функции и и построим по точкам (тонкая линия):

Таблица

Двигая эту прямую параллельно самой себе (по направлению), зафиксируем её крайнее положение . Это нижняя опорная прямая для области .

Минимальное значение в области определится пересечением прямых и :

минимальное значение целевой функции в области.

Выводы

симплексный планирование стоимостный

50 - план производства изделия С (ед.),

20 - план производства изделия Z (ед.);

90 - загрузка оборудования 1-го типа (ч).

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

Данная задача о планировании производства является примером работы предприятия «ХХХ» г.Холмска. Благодаря ей мы спланировали выпуск изделий при условии, что план должен быть выполнен в стоимостном выражении на определенную сумму.

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

Литература

1. Бурда А.Г. Бурда Г.П. Методы принятия управленческих решений в экономических системах АПК: учеб. пособие для вузов / А.Г. Бурда, Г.П. Бурда. - Краснодар: КубГАУ, 2013. - 532 с

2. Информатизация деловой сферы и профессиональная деятельность Затонская И.В., Затонская С.С. Сборники конференций НИЦ Социосфера. 2014. № 1. С. 026-032.

3. Информационные технологии в управлении имущественным состоянием аграрного предприятия Затонская И.В., Чуб Е.В. В сборнике: Cовременное состояние и приоритетные направления развития экономики Материалы Международной заочной научно-практической конференции. Новосибирский государственный аграрный университет. Россия, г. Новосибирск, 2014. С. 88-93.

4. Ковалева К.А. Системы информационной безопасности и их построение/Ковалева К.А., Попова Е.В. В сборнике: Современные технологии управления - 2014 Сборник материалов международной научной конференции. Киров, 2014. С. 1853-1862.

5. Ковалева К.А., Попова Е.В., Молошнев С.А. Анализ востребованности сервисов систем межведомственного электронного взаимодействия многофункционального центра // Анализ, моделирование и прогнозирование экономических процессов: материалы VI Международной научно-практической Интернет-конференции, 15 декабря 2014 г. - 15 февраля 2015 г. / под ред. Л.Ю. Богачковой, В.В. Давниса; Волгоград. гос. ун-т, Воронеж. гос. ун-т. - Волгоград: ООО «Консалт», 2014.

6. Комиссарова К.А. Основы алгоритмизации и программирования: методическое пособие Часть I Turbo Pascal Си++ (2-е издание, переработанное): метод. пособие/ Комиссарова К.А., Коркмазова С.С. -Краснодар, КубГАУ 2014.-54 с.

7. Комиссарова К.А.Основы алгоритмизации и программирования: методическое пособие Часть II Turbo Pascal Си++ (2-е издание, переработанное): метод. пособие/ Комиссарова К.А., Коркмазова С.С. -Краснодар, КубГАУ 2014.-58 с.

8. Моделирование деятельности страховых компаний методами нелинейной динамики: монография (Научное издание)./В. А. Перепелица, Е. В. Попова, К. А. Комиссарова. -Краснодар: КубГАУ, 2007. -201 с.

9. Моделирование организационно-экономического процесса управления инновационным развитием аграрного предприятия. Чуб Е.В., Затонская И.В.В сборнике: Междисциплинарные исследования в области математического моделирования и информатики Материалы 5-й научно-практической internet-конференции. Ответственный редактор Ю.С. Нагорнов . Ульяновск, 2015. С. 230-233.

10. Основы математического моделирования социально-экономических процессов : учеб. пособие / С. Н. Косников ; под ред. д-ра экон. наук, проф. А. Г. Бурда. - Краснодар : КубГАУ, 2013. - 93 с.

11. Перепелица В.А., Тамбиева Д. А., Комиссарова К. А. Визуализация R/S-и Я-траекторий эталонных временных рядов//Современные наукоемкие технологии. Приложение. № 3, 2005, с. 64-68.

12. Попова Е.В. Информационные системы в экономике: методическое пособие для экономических специальностей. Часть 1 Word Excel (2-е издание, переработанное): метод. пособие/Попова Е.В., Комиссарова К.А. -Краснодар, КубГАУ 2014.-51 с.

13. Попова Е.В. Информационные системы в экономике: методическое пособие для экономических специальностей. Часть II Access PowerPoint (2-е издание, переработанное): метод. пособие/Попова Е.В., Комиссарова К.А. -Краснодар, КубГАУ 2014.-46 с.

14. Сегментация туризма как отражение современного состояния туристического рынка Попова Е.В., Шевченко А.А., Курносова Н.С. Политематический сетевой электронный научный журнал Кубанского государственного аграрного университета. 2013. № 89. С. 1063-1075.

15. Теория принятия решений : учебное пособие, задачник / С. Н. Косников ; под ред. д-ра экон. наук, проф. А. Г. Бурда. - Краснодар : КубГАУ, 2013. - 54 с.

16. Финансовый потенциал аграрного предприятия как фактор конкурентоспособности.Затонская И. В.В сборнике: Современные тенденции в науке и образовании Сборник научных трудов по материалам Международной научно-практической конференции: в 5 частях. ООО "АР-Консалт". Москва, 2015. С. 154-155.

17. Франциско О.Ю., Бурда А.Г. Выбор режима налогообложения при развитии подсобных перерабатывающих производств аграрных предприятий//Труды Кубанского государственного аграрного университета. 2009. Т. 1. № 16. С. 72-77.

Размещено на Allbest.ru