Читайте также:
|
Решим прямую задачу линейного программирования симплекс-методом.
Определим максимальное значение целевой функции F(X) = 50x1+60x2+110x3+120x4 при следующих условиях-ограничений.
x1+x2+2x3+x4≤20
3x1+6x2+5x3+4x4≤150
6x1+12x2+13x3+4x4≤100
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
В 1-м неравенстве смысла (≤) вводим базисную переменную x5. В 2-м неравенстве смысла (≤) вводим базисную переменную x6. В 3-м неравенстве смысла (≤) вводим базисную переменную x7.
1x1 + 1x2 + 2x3 + 1x4 + 1x5 + 0x6 + 0x7 = 20
3x1 + 6x2 + 5x3 + 4x4 + 0x5 + 1x6 + 0x7 = 150
6x1 + 12x2 + 13x3 + 4x4 + 0x5 + 0x6 + 1x7 = 100
Введем новую переменную x0 = 50x1+60x2+110x3+120x4.
Выразим базисные переменные <5, 6, 7> через небазисные.
x0 = 0+50x1+60x2+110x3+120x4
x5 = 20-x1-x2-2x3-x4
x6 = 150-3x1-6x2-5x3-4x4
x7 = 100-6x1-12x2-13x3-4x4
Переходим к основному алгоритму симплекс-метода.
Поскольку задача решается на максимум, то переменную для включения в текущий план выбирают по максимальному положительному числу в уравнении для x0.
1. Проверка критерия оптимальности.
В выражении для x0 присутствуют отрицательные элементы. Следовательно, текущий план неоптимален
2. Определение новой базисной переменной.
max(50,60,110,120,0,0,0) = 120
x0 = 0+50x1+60x2+110x3+120x4
x5 = 20-x1-x2-2x3-x4
x6 = 150-3x1-6x2-5x3-4x4
x7 = 100-6x1-12x2-13x3-4x4
В качестве новой переменной выбираем x4.
3. Определение новой свободной переменной.
Вычислим значения Di по всем уравнениям для этой переменной: bi / ai4
и из них выберем наименьшее:
Вместо переменной x5 в план войдет переменная x4.
4. Пересчет всех уравнений.
Выразим переменную x4 через x5
x4 = 20-x1-x2-2x3-x5
и подставим во все выражения.
x0 = 0+50x1+60x2+110x3+120(20-x1-x2-2x3-x5)
x6 = 150-3x1-6x2-5x3-4(20-x1-x2-2x3-x5)
x7 = 100-6x1-12x2-13x3-4(20-x1-x2-2x3-x5)
После приведения всех подобных, получаем новую систему, эквивалентную прежней:
x0 = 2400-70x1-60x2-130x3-120x5
x4 = 20-x1-x2-2x3-x5
x6 = 70+x1-2x2+3x3+4x5
x7 = 20-2x1-8x2-5x3+4x5
Полагая небазисные переменные x = (4, 6, 7) равными нулю, получим новый допустимый вектор и значение целевой функции:
x = (70, 60, 130, 0, 120, 0, 0), x0 = 2400
Выражение для x0 не содержит положительных элементов. Найден оптимальный план.
Окончательный вариант системы уравнений:
x0 = 2400-70x1-60x2-130x3-120x5
x4 = 20-x1-x2-2x3-x5
x6 = 70+x1-2x2+3x3+4x5
x7 = 20-2x1-8x2-5x3+4x5
Оптимальный план можно записать так:
x4 = 20
F(X) = 120 • 20 = 2400
Заключение
Развитие современного общества характеризуется повышением технического уровня, усложнением организационной структуры производства, управления войсками, углублением общественного разделения труда, предъявлением высоких требований к методам планирования хозяйственного и военного руководства. Научного подхода требует и решение тактических и стратегических задач, руководство военными операциями.
В настоящее время новейшие достижения математики и современной вычислительной техники находят все более широкое применение как в экономических исследованиях и планировании, так и в решении военных тактических задач. Этому способствует развитие таких разделов математики как математическое программирование, теория игр, теория массового обслуживания, а также бурное развитие быстродействующей электронно-вычислительной техники. Уже накоплен большой опыт постановки и решения экономических и тактических задач с помощью математических методов. Особенно успешно развиваются методы оптимального управления. Ярким примером применения современных математических методов является война Америки с Ираком и «Буря в пустыне». Там быстро развивается экономика и производство, где широко используются математические методы.
Данная курсовая работа посвящена вопросу о решении задачи линейного программирования методом последовательного улучшения плана, иначе симплекс – метод.
В первой задаче рассказывается о линейном программировании в частности, и о том, что такое общая постановка задачи линейного программирования, как составить математическую модель, а также рассказано о канонической форме задач линейного программирования.
Вторая задача планирования строится на математической модели и решается данная задача симплексным методом, а также методом Гаусса.
Литература
1. А.В. Волощенко, Ю.Н. Кузнецов, В.И. Кузубов, “Математическое программирование”. М., Высшая школа, 1980.
2. В.А. Ильин, Э. Г. Позняк “Основы математического анализа”. М., Наука, 1979.
3. В.И. Ермаков “Общий курс высшей математики для экономистов”, Москва, Инфра-М, 2000г.
4. И.В. Большакова “Линейное программирование”. Минск: БНТУ, 2004.
Дата добавления: 2015-09-10; просмотров: 74 | Поможем написать вашу работу | Нарушение авторских прав |
| <== предыдущая лекция | | | следующая лекция ==> |
| Графоаналитический метод решения задачи № 1 | | | Понятие об экологической безопасности |