Учебно-методический комплекс по дисциплине экономико-математическое моделирование на транспорте

Скачать 0.72 Mb.

Название	Учебно-методический комплекс по дисциплине экономико-математическое моделирование на транспорте
страница	3/5
Дата публикации	20.11.2017
Размер	0.72 Mb.
Тип	Учебно-методический комплекс

100-bal.ru > Экономика > Учебно-методический комплекс

1 2 3 4 5

Задача 3

Тема. Применение симплекс-алгоритма для решения экономической оптимизационной задачи управления производством

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

Локомотиворемонтный завод имеет три цеха, оснащенных различным оборудованием. В цехах может быть отремонтировано х₁, х₂ и х₃ локомотивов ежемесячно. Всего же направлено в ремонт 10 локомотивов. При этом за ремонт одного локомотива рабочие первого цеха получают сдельно 1 млрд. руб., второго цеха – 2 млрд. руб., и третьего также – 2 млрд. руб. По условию договора предприятия с профсоюзом рабочим должно быть выплачено в виде заработной платы не менее 8 млрд. руб.

Станковый парк предприятия ограничен, поэтому в указанные сроки у предприятия имеется всего 18 тыс. станко-часов. На ремонт одного локомотива в первом цехе требуется 1000 станко-часов, второго – 2000 станко-часов, а в третьем цехе – 4000 станко-часов. За ремонт одного локомотива в первом цехе завод получит 4 млрд. руб. прибыли, во втором – 5 млрд. руб. прибыли, в третьем – 3 млрд. руб. прибыли. Требуется найти такой план ремонта локомотивов, при котором будет наибольшая прибыль.

Постановка задачи

Целевая функция

.

Ограничения:

.

Решение задачи симплекс-методом

1. Чтобы перейти от задачи на максимум к задаче на минимум, введем функцию

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

2. Перейдем от ограничений неравенств к ограничениям-равенствам. Для этого введем новые переменные х₄ и х₅ по следующим формулам:

;

.

3. Получим следующую основную задачу линейного программирования:

4. Найдем вид канонической задачи линейного программирования. Для этого выразим в первом уравнении х₁ через другие неизвестные и подставим это его выражение во второе и третье уравнения, а также в уравнение для функции g. Получим:

5. Шаг симплекс-алгоритма. Из полученного выражения для целевой функции g видно, что для ее уменьшения следует увеличивать неизвестное x₂. Неизвестное x₃ увеличивать нецелесообразно, потому что это приведет к увеличению функции g. Напомним, что все неизвестные x₁ неотрицательны.

Увеличение x₂ возможно до 10 согласно первому уравнению и до 8 согласно второму. При больших значениях x₂ станут отрицательными значения x₅ и x₁. Второе ограничение не препятствует увеличению x₂. Из этого следует, что прежде проявляется второе ограничение, разрешающим элементом является число –1.

Поэтому выразим x₂ из второго ограничения и подставам его выражение в первое в третье ограничения, а также в выражение для целевой функции. Получим:

6. В выражении для функции цели g оба неизвестных входят со знаком «+». Поэтому можно утверждать, что найден оптимальный план: x₅=x₃=0. Подставив эти значения в последнюю систему ограничений, получим и остальные неизвестные: x₁=2, x₂=8, x₄=10. Оптимальное значение функции g равно –48. Возвращаясь к интересующим нас переменным, можно утверждать, что не следует производить ремонт в третьем цехе, в первом следует ремонтировать 2, а во втором 8 локомотивов. При этом прибыль будет равна 48 млрд. руб.
Задание: найти оптимальное значение функции при системе ограничений.

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

1. Целевая функция

.

Ограничения:

.

2. Целевая функция

.

Ограничения:

.

3. Целевая функция

.

Ограничения:

.

4. Целевая функция

.

Ограничения:

.

5. Целевая функция

.

Ограничения:

.

6. Целевая функция

.

Ограничения:

.

7. Целевая функция

.

Ограничения:

.

8. Целевая функция

.

Ограничения:

.

9. Целевая функция

.

Ограничения:

.

10. Целевая функция

.

Ограничения:

.

11. Целевая функция

.

Ограничения:

.

12. Целевая функция

.

Ограничения:

.

13. Целевая функция

.

Ограничения:

.

14. Целевая функция

.

Ограничения:

.

15. Целевая функция

.

Ограничения:

.

16. Целевая функция

.

Ограничения:

.

17. Целевая функция

.

Ограничения:

.

18. Целевая функция

.

Ограничения:

.

19. Целевая функция

.

Ограничения:

.

20. Целевая функция.

Ограничения:

.

21. Целевая функция.

Ограничения:

.

22. Целевая функция

.

Ограничения:

.

23. Целевая функция

.

Ограничения:

.

24. Целевая функция

.

Ограничения:

.

25. Целевая функция

.

Ограничения:

.
Методические указания к решению задачи 3

Эту задачу следует решать с помощью симплекс-метода [1].

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

2. Переход к канонической задаче линейного программирования. На этом этапе следует выразить базисные неизвестные через свободные. Число базисных неизвестных равняется числу ограничений, все остальные неизвестные называется свободными. Целевую функцию также следует выразить через свободные неизвестные. На этом этапе следует добиваться, чтобы при нулевых значениях свободных неизвестных базисные были положительными. Все задачи 1-10 подобраны таким образом, что сделать это несложно. Общий алгоритм получения допустимого базисного решения описан в [1].

3. Нахождение оптимального решения с помощью симплекс-алгоритма.

3.1. Если дана задача на максимизацию целевой функции f, то она сводится к задаче на минимизацию функции –f.

3.2. Проверка оптимальности базисного решения. Если в целевую функцию свободные неизвестные входят с неотрицательными коэффициентами для минимальности функции следует принять эти неизвестные нулями, потому что они неотрицательны, и сделать функцию цели меньше, чем при таком варианте, невозможно.

3.3. Нахождение разрешающего элемента. Если же какой-либо из коэффициентов при свободном неизвестном в целевой функции отрицателен, то функцию можно пытаться уменьшить путем увеличения этого неизвестного. При этом его можно увеличивать до тех пор, пока в каком-либо из ограничений базисное неизвестное не станет равным нулю, т.е. перейдет в число свободных. Следует найти то ограничение, которое в меньшей степени позволяет увеличивать свободное неизвестное. Коэффициент при нем в этом ограничении называется разрешающим элементом.

3.4. Шаг симплекс-алгоритма. Следует выразить варьируемое – свободное неизвестное через другие свободные и базисное из ограничения с разрешающим элементом. Полученное уравнение будет новым ограничением, прежнее ограничение следует удалить. Остальные ограничения следует изменить следующим образом: вместо свободного переменного следует подставить его выражение через базисное из нового ограничения. Аналогично следует заменить это свободное неизвестное его выражением и в целевой функции. При этом если приравнять нулю новые свободные переменные, то значение целевой функции уменьшится.

3.5. Критерий остановки в симплекс-алгоритме. Шаги симплекс-алгоритма следует делать до тех пор, пока не будет ситуации описанной в п. 3.2, когда все коэффициенты при неизвестных в целевой функции не станут положительными.

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

1 2 3 4 5

Похожие:

	Рабочая программа по дисциплине ен. Р. 01. Экономико-математическое моделирование Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования		Математическое моделирование движения несимметричного авторотирующего тела Учебно-методический комплекс по «Психологии и педагогике» составлен в соответствии с требованиями Государственного образовательного...
	Рабочая программа для студентов 010800. 62 специальности «Механика... Мосягин В. Е. Теория вероятностей, математическая статистика, случайные процессы. Учебно-методический комплекс. Рабочая программа...		Учебно-методический комплекс учебной дисциплины «математическое моделирование» Программа составлена в соответствии с требованиями фгос впо по направлению подготовки 230700. 68 «Прикладная информатика»
	Рабочая программа составлена в соответствии с фгт к структуре основной... Методы компьютерного моделирования. Статистическое моделирование Учебно-методический комплекс рабочая программа для аспирантов специальности...		Учебно-методический комплекс для студентов, обучающихся по экономическим специальностям Учебно-методический комплекс. Для студентов, обучающихся по экономическим специальностям. – М.: Финансовая академия при Правительстве...
	Русская логика – индикатор интеллекта Учебно-методический комплекс. Для студентов, обучающихся по экономическим специальностям. – М.: Финансовая академия при Правительстве...		Математическое моделирование термически нагруженных конструкций котельных агрегатов Специальность: 05. 13. 18 – Математическое моделирование, численные методы и комплексы программ
	Учебно-методический комплекс рабочая программа для студентов очной формы обучения Шармин Д. В. История и методология математики. Учебно-методический комплекс. Рабочая программа для студентов очной формы обучения,...		Учебно-методический комплекс рабочая программа для студентов очной формы обучения Шармин Д. В. История развития математической науки. Учебно-методический комплекс. Рабочая программа для студентов очной формы обучения,...
	Тестовый метод контроля знаний учащихся на уроках технологии Учебно-методический комплекс. Для студентов, обучающихся по экономическим специальностям. – М.: Финансовая академия при Правительстве...		Фгбоу впо «сгэу» от 09. 11. 2012г. № Решение ученого совета Самарского... «Математическое моделирование», «Математические модели в финансовых операциях», «Методы оптимизации», «Экономико-математические методы...
	«Основы логики» Наука, изучающая законы и формы мышления, называется Учебно-методический комплекс. Для студентов, обучающихся по экономическим специальностям. – М.: Финансовая академия при Правительстве...		Учебно-методический комплекс по дисциплине Специальность/направление 190701. 65 Организация перевозок и управление на транспорте (железнодорожный транспорт) (ПП)
	Электронный учебно-методический комплекс специальность: 190701. 65... Грузоведение: учебно-методический комплекс /авт сост. Б. Г. Ашуркин. – Спб.: Ивэсэп, 2011. – 69 с		Учебно-методический комплекс специальность: 190701 Организация перевозок... С 83 Стратегия развития автотранспортных предприятий: учебно-методический комплекс / авт сост. В. А. Богомазов. – Спб.: Ивэсэп, 2011....

Школьные материалы