Решение задач линейного программирования различными методами - Программирование, компьютеры и кибернетика контрольная работа

Главная

Программирование, компьютеры и кибернетика
Решение задач линейного программирования различными методами

Практические навыки моделирования задач линейного программирования и их решения графическим и симплекс-методом с использованием прикладной программы SIMC. Моделирование транспортных задач и их решение методом потенциалов с помощью программы TRAN2.


посмотреть текст работы


скачать работу можно здесь


полная информация о работе


весь список подобных работ


Нужна помощь с учёбой? Наши эксперты готовы помочь!
Нажимая на кнопку, вы соглашаетесь с
политикой обработки персональных данных

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Решение задач линейного программирования графическим методом
Цель задания : приобрести практические навыки решения задач линейного программирования графическим методом.
Найти максимум и минимум линейной формы графическим методом по исходным данным задачи ЛП (таблица 1).
Ограничения задачи линейного программирования
Построим область L допустимых решений. Заменим в каждом неравенстве задачи знак неравенства на знак равенства. Получим уравнения прямых:
x 1 +4 x 2 =8, 2 x 1 - x 2 =4, x 1 + x 2 -=1, x 1 =0, x 2 =0.
Область L определяется как общая часть полуплоскостей, соответствующих неравенствам ограничений (рисунок 1).
Рисунок 1. Графическое решение задачи ЛП
В данной задаче она составляет многоугольник ABCD . Для нахождения экстремума функции Z =-2 x 1 + 4 x 2 , строим разрешающую прямую, приравнивая линейную форму нулю: Z =0. Строим градиент целевой функции C(2;4).
Минимальное значение функция принимает в точке D(4,5;0,7) , а максимальное в точке B .
Анализ решения задачи линейного программирования
В результате решения задачи линейного программирования были получены минимум и максимум рассматриваемой функции, вследствие того, что область ограничений представляет собой замкнутый многоугольник, если бы фигура области ограничений была не замкнута, функция могла бы не иметь одного или обоих экстремумов в заданной области.
Решение задач ЛП симплексным методом с использованием симплекс-таблиц
Цель задания : закрепить теоретические сведения и приобрести практические навыки решения задач ЛП симплекс-методом.
Приведем задачу ЛП к каноническому виду:
x 3 , x 4 , x 5 -- дополнительные переменные.
Во втором уравнении дополнительная переменная введена с коэффициентом -1 и уравнение умножено на -1.
Постановка задачи в виде матрицы системы ограничений
Решение задачи ЛП с составленными симплекс-таблицами
Единичные векторы A 3 , A 4 , A 5 образуют базис трехмерного пространства ( m =3 ). Решать эту задачу алгоритмом симплекс-метода можно, поскольку переменные x 3 , x 4 , x 5 входят с коэффициентом +1 соответственно в первое, второе и третье ограничения. Таким образом, x 3 , x 4 , x 5 - базисные переменные, а остальные небазисные. Полагая небазисные переменные в ограничениях равными нулю, получим исходное допустимое базисное решение:
Заполняем исходную симплекс-таблицу (таблица 2)
Таблица 2. Нулевая симплекс-таблица
Так как среди разностей есть положительные, то X 0 не является оптимальным решением. Строим новое базисное решение.
Выводим из базиса вектор A 3 ,так как
Разрешающий элемент таблицы x 12 выделим кругом, а разрешающий столбец и строку стрелками.
Таблица 3. Первая симплекс-таблица
Так как среди разностей есть положительные, то оптимальное решение не получено. Строим новое базисное решение.
Выводим из базиса вектор A 4 ,так как
Так как все разности во второй таблице (таблица 4) неположительны: , т получено оптимальное решение:
Тогда max ( Z ) = - min (- Z ) = 225
Использование переменной x 1 нецелесообразно.
Моделирование и решение задач ЛП на ЭВМ
Цель задания : приобрести практические навыки моделирования задач ЛП и их решения симплекс-методом с использованием прикладной программы SIMC.
Предприятие может работать по 5-ти технологическим процессам, причем кол-во единиц выпускаемой продукции по разным ТП за ед. времени соответственно равны 300, 260, 320, 400, 450 шт. затраты производственных факторов в гривнах при работе по разным ТП в течение 1 ед. времени и располагаемые ресурсы этих факторов в табл.5.
Найти программу максимального выпуска продукции.
Математическая интерпретация задачи
Исходные массивы, записанные в виде, пригодном для решения задачи по программе SIMC
12.000 15.000 10.000 12.000 11.000 < 1300.000
0.200 0.100 0.200 0.250 0.300 < 30.000
3.000 4.000 5.000 4.000 2.000 < 400.000
6.000 5.000 4.000 6.000 4.000 < 800.000
300.000 260.000 320.000 400.000 450.000
Распечатка ЭВМ в результатом решения
ТЕКУЩАЯ СИМПЛЕКС-ТАБЛИЦА ЗАДАЧА НЕ ВЫРОЖДЕНА
6 0.000 1300.000 12.000 15.000 10.000 12.000 11.000
7 0.000 30.000 0.200 0.100 0.200 0.250 0.300
8 0.000 400.000 3.000 4.000 5.000 4.000 2.000
9 0.000 800.000 6.000 5.000 4.000 6.000 4.000
0.000 300.000 260.000 320.000 400.000 450.000
ОПТИМАЛЬНОЕ ЗНАЧЕНИЕ БАЗИС-ВЕКТОРА И РЕШЕНИЕ
ИТЕРАЦИЯ N=1 ПРОДОЛЖЕНИЕ РЕШЕНИЯ ТЕКУЩАЯ СИМПЛЕКС-ТАБЛИЦА ЗАДАЧА НЕ ВЫРОЖДЕНА
6 0.000 1300.000 12.000 15.000 10.000 12.000 11.000
7 0.000 30.000 0.200 0.100 0.200 0.250 0.300
8 0.000 400.000 3.000 4.000 5.000 4.000 2.000
9 0.000 800.000 6.000 5.000 4.000 6.000 4.000
0.000 -300.000 -260.000 -320.000 -400.000 -450.000
ИТЕРАЦИЯ N=2 ПРОДОЛЖЕНИЕ РЕШЕНИЯ ТЕКУЩАЯ СИМПЛЕКС-ТАБЛИЦА ЗАДАЧА НЕ ВЫРОЖДЕНА
6 0.000 200.000 4.667 11.333 2.667 2.833 -36.667
5 450.000 100.000 0.667 0.333 0.667 0.833 3.333
8 0.000 200.000 1.667 3.333 3.667 2.333 -6.667
9 0.000 400.000 3.333 3.667 1.333 2.667 -13.333
45000.000 -0.000 -110.000 -20.000 -25.000 1500.000
ИТЕРАЦИЯ N=3 ПРОДОЛЖЕНИЕ РЕШЕНИЯ ТЕКУЩАЯ СИМПЛЕКС-ТАБЛИЦА ЗАДАЧА НЕ ВЫРОЖДЕНА
2 260.000 17.647 0.412 0.235 0.250 0.088 -3.235
5 450.000 94.118 0.529 0.588 0.750 -0.029 4.412
8 0.000 141.176 0.294 2.882 1.500 -0.294 4.118
9 0.000 335.294 1.824 0.471 1.750 -0.324 -1.471
46941.176 45.294 5.882 2.500 9.706 1144.118
ОПТИМАЛЬНОЕ ЗНАЧЕНИЕ БАЗИС-ВЕКТОРА И РЕШЕНИЕ
ОПТИМУМ ЦЕЛЕВОЙ ФУНКЦИИ = 46941.1765
Оптимальный план. Экономическая интерпретация оптимального решения. В соответствии с полученным результатом выпуск продукции по 1,3 и 4 технологическим процессам нецелесообразен.
Моделирование транспортных задач и их решение методом потенциалов
Цель задания : приобрести практические навыки моделирования и решения транспортной задачи ЛП методом потенциалов.
Составить оптимальное распределение трех видов механизмов на четырех участках работ, обеспечивающих минимальную себестоимость выполнения всей работы. Количество единиц механизмов, потребности участков в механизмах и себестоимость выполнения единицы работы каждым механизмом на соответствующем участке приведены в таблице 6.
Таблица 6. 06 вариант транспортной задачи
Себестоимость выполнения единицы работы механизма ,гр.
Потребности b j участков в механизмах
Математическая формулировка транспортной задачи
Пусть x ij - количество единиц работы, выполненной механизмом вида a i , на участке работы b j .Требуется определить план распределения механизмов, минимизирующий себестоимость выполнения всей работы:
1) ; - все механизмы должны быть задействованы;
2); - все участки должны быть загружены;
3) ; - количество единиц работы не может быть отрицательным
Условие разрешимости задачи выполняется:
Исходный опорный план, составленный по методу северо-западного угла
Решение транспортной задачи методом потенциалов
Итак, видно что в число занятых клеток следует ввести клетку (2,1).
Получим новый улучшенный план - таблица 8.
Введём в число занятых клетку (1,4) . Получим новый улучшенный план - Таблица 9.
Так как, - то данный план является оптимальным и значение себестоимости по данному плану.
x 12 =1 5 ; x - 21 =5; x 22 =5; x - 31 = 2 0; x 33 =1 0 ; x -34 = 5 .
Z =1 5 *4+5* 6 + 5 * 8 + 20 * 4 +1 0 *4+5*2= 260 .
Данный оптимальный план показывает, как нужно распределить механизмы по участкам для получения минимальной себестоимости выполненной работы.
Цель задания : приобрести практические навыки решения транспортной задачи на ЭВМ с использованием прикладной программы TRAN2.
Составить оптимальное распределение трех видов механизмов на четырех участках работ, обеспечивающих минимальную себестоимость выполнения всей работы. Количество единиц механизмов, потребности участков в механизмах и себестоимость выполнения единицы работы каждым механизмом на соответствующем участке приведены в таблице 6.
Таблица 10. 06 вариант транспортной задачи
Себестоимость выполнения единицы работы механизма ,гр.
Потребности b j участков в механизмах
Исходные массивы для решения транспортной задачи по программе TRAN 2
Распечатка с ЭВМ с результатом решения
Оптимальный план транспортной задачи
x 12 =1 5 ; x - 21 =5; x 2 2 =5; x 31 = 2 0; x 33 =1 0 ; x -34 = 5 .
Z =1 5 *4+5* 6 +5* 8 + 2 0* 4 +1 0 *4+5*2= 260 .
Решение транспортной задачи на ЭВМ автоматизирует работу по вычислению решений транспортных задач и на тестируемом входном условие получается за 3 итерации, как и при ручном вычислении.
Решение многоэтапных задач методом динамического программиров а ния
Цель задания : приобрести практические навыки решения многоэтапных задач методом динамического программирования.
В таблице 11 приведены значения g i ( x ) возможного прироста продукции на четырех предприятиях в зависимости от выделенной на реконструкцию и модернизацию производства суммы x .
Распределить между предприятиями имеющиеся 100 тыс. гр., чтобы общий прирост f 4 (100) выпуска продукции был максимальным. Для упрощения вычислений значения x принимать кратными 20 тыс. гр.
Прирост выпуска продукции, тыс. гр.
Функциональное уравнение Беллмана для рассматриваемой задачи
f 1 ( x )= max [ g 1 ( x )]= g 1 ( x ) - для пер в ого предприятия;
Решение задачи оптимального распределения средств между предприятиями методом динамического программирования
Итак, из таблицы 16 видно, что наибольший прирост выпуска продукции, который могут дать четыре предприятия при распределении между ними 100 тыс. грн. составляет 69 тыс. грн. При этом четвертому предприятию нужно выделить 40 тыс. грн., а остальным 60 тыс. грн.
Оптимальное распределение оставшихся 60 тыс. грн. между 3 -мя предприятиями обеспечит прирост продукции на сумму 42 тыс. грн., при условии, что 3 -му предприятию не будут выделены средства. Остается 60 тыс. грн., которые надо распределить между 2 -мя предприятиями. Выделив всю оставшуюся сумму (60 тыс. грн.) второму, прибыль составит 42 тыс. грн. первому предприятию средств не остается.
Максимальный прирост выпуска продукции на четырех предприятиях при распределении между ними 100 тыс. грн. составляет 69 тыс. грн. и будет получен, если первому предприятию не выделять средств, второму -- 60 тыс. грн., третьему не выделять, а четвертому -- 40 тыс. грн.
X * =(0,0,60,40); f * = f 4 (100)= 69 тыс. гр.
Алгоритм решения задач линейного программирования симплекс-методом. Построение математической модели задачи линейного программирования. Решение задачи линейного программирования в Excel. Нахождение прибыли и оптимального плана выпуска продукции. курсовая работа [1,1 M], добавлен 21.03.2012
Разработка программы, решающей базовую задачу линейного программирования симплекс-методом с помощью симплекс-таблиц. Выбор языка программирования и среды разработки, программные модули и их взаимодействие между собой. Листинг разработанной программы. курсовая работа [415,8 K], добавлен 08.09.2013
Изучение и укрепление на практике всех моментов графического метода решения задач линейного программирования о производстве журналов "Автомеханик" и "Инструмент". Построение математической модели. Решение задачи с помощью электронной таблицы Excel. курсовая работа [663,9 K], добавлен 10.06.2014
Сущность линейного программирования. Математическая формулировка задачи ЛП и алгоритм ее решения с помощью симплекс-метода. Разработка программы для планирования производства с целью обеспечения максимальной прибыли: блок-схема, листинг, результаты. курсовая работа [88,9 K], добавлен 11.02.2011
Широкое применение вычислительной техники как в общей математике, так и в одном из её разделов – математических методах. Ознакомление с решением задач линейного программирования симплекс-методом и графически. Составлена программа на языке Delphi. курсовая работа [57,1 K], добавлен 04.05.2010
Решение задачи линейного программирования симплекс-методом: постановка задачи, построение экономико-математической модели. Решение транспортной задачи методом потенциалов: построение исходного опорного плана, определение его оптимального значения. контрольная работа [118,5 K], добавлен 11.04.2012
Графическое решение задач. Составление математической модели. Определение максимального значения целевой функции. Решение симплексным методом с искусственным базисом канонической задачи линейного программирования. Проверка оптимальности решения. контрольная работа [191,1 K], добавлен 05.04.2016
Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д. PPT, PPTX и PDF-файлы представлены только в архивах. Рекомендуем скачать работу .

© 2000 — 2021



Решение задач линейного программирования различными методами контрольная работа. Программирование, компьютеры и кибернетика.
Этика И Психология Речевого Поведения Реферат
Реферат Здоровый Образ Жизни Семьи
Дипломная работа по теме Паранормальные явления человеческой психики
Курсовая Работа На Тему Система Юридических Наук
Реферат: Правоотношения
Отчет по практике по теме Организационно-экономическая характеристика Гомельского райпо
Сочинение по теме Медальные сочинения
Банковский маркетинг
Контрольная Работа Простые Вещества
Реферат: Гелиоэнергетика состояние и перспективы. Скачать бесплатно и без регистрации
Итоговое Сочинение 2022 Подготовка По Направлениям
Эссе Рефлексия По Пройденному Материалу
Статья: Разработка и исследование процесса выделения нафталина и других летучих веществ из конденсата вакуум-содовой сероочистки
Контрольная работа по теме Приговор суда как акт правосудия
Реферат по теме Мифология майя
Дипломная работа по теме Игровые технологии в начальной школе
Дипломная Работа Метрополитен
Контрольная Работа Умк 5 Класс
Курсовая работа по теме Прядильный цех
Список Аргументов К Итоговому Сочинению
Изучение становления и развития первобытного общества - Государство и право курсовая работа
Географическая характеристика Бельгии - География и экономическая география презентация
Исследование конкурентной среды фирмы на примере ООО "Темп-Авто" - Маркетинг, реклама и торговля курсовая работа