Учебная работа № 6074. «Контрольная Задача линейного программирования. Транспортная задача
Учебная работа № 6074. «Контрольная Задача линейного программирования. Транспортная задача
Содержание:
«1. Задача линейного программирования
Предприятие планирует выпуск продукции I и II видов, на производство которых расходуется три вида сырья А, В и С. Потребность aij i-го вида сырья для производства каждой единицы j-го вида продукции, запас bi соответствующего вида сырья и прибыль cj от реализации единицы j-го вида продукции заданы таблицей:
Виды сырья Виды продукции Запасы сырья
I II
A a11 = 5 a12 = 2 b1 = 45
B a21 = 1 a22 = 1 b2 = 12
C a31 = 2 a32 = 5 b3 = 45
прибыль c1 = 6 c2 = 7
план (ед.) x1 x2
1. Для производства двух видов продукции I и II с планом x1 и x2 единиц составить математическую модель, т.е. целевую функцию прибыли F и соответствующую систему ограничений по запасам сырья, предполагая, что требуется изготовить в сумме не менее n единиц обоих видов продукции.
2. Найти оптимальный план X*=(x1,x2) производства продукции, обеспечивающий максимальную прибыль Fmax. Определить остатки каждого вида сырья. Задачу решить симплекс-методом.
3. Построить по полученной системе ограничений многоугольник допустимых решений и найти оптимальный план производства геометрическим методом. Определить максимальную прибыль Fmax.
4. Составить математическую модель двойственной задачи (систему ограничений по единичной прибыли и целевую функцию общих издержек на сырье Z); найти оптимальный набор цен на сырьё Y*=(y1, y2, y3), обеспечивающий минимум общих затрат на сырье Zmin.
5. Провести анализ первоначальных и дополнительных переменных исходной и двойственной задач, сделать выводы.
6. Решить задачу оптимизации в MS Excel в режиме «поиск решения». Провести исследование полученного решения, используя отчеты по результатам, по устойчивости, по пределам; сделать выводы. Ответы, полученные в результате решений «вручную» и с помощью Excel, должны совпадать.
2. Транспортная задача
На трех складах А1, А2 и А3 хранится а1=100, а2=200, а3=60+10n единиц одного и того же груза, соответственно. Этот груз требуется доставить трем потребителям В1, В2 и В3, заказы которых b1=190, b2=120, b3=10m единиц груза, соответственно. Стоимости перевозок cij единицы груза с i-го склада j-му потребителю указаны в соответствующих клетках транспортной таблицы:
Потребности
Запасы В1 В2 В3
b1=190 b2=120 b3=40
А1 а1 = 100 4 2 4
А2 а2 = 200 5 5 3
А3 а3 = 110 1 5 6
1. Сравнивая суммарный запас и суммарную потребность
в грузе, установить, является ли модель транспортной задачи открытой или закрытой. Если модель открытая, то ее необходимо сделать закрытой, добавив фиктивный склад А4 с запасом а4=b-а в случае аb и положив соответствующие им тарифы перевозок нулевыми.
2. Составить первоначальный план перевозок методом северо-западного угла и методом наименьшей стоимости.
3. Методом потенциалов проверить первоначальный план перевозок на оптимальность в смысле суммарной стоимости перевозок, и если это не так, то составить оптимальный план
,
обеспечивающий минимальную стоимость перевозок . Найти эту стоимость.
4. Решить задачу в MS Excel в режиме «поиск решения». Ответы (значения стоимости перевозок), полученные в результате решений «вручную» и с помощью Excel, должны совпадать. Оптимальные планы перевозок могут не совпадать.
»
Выдержка из похожей работы
просты, хорошо разработаны, допускают
полное исследование и достаточно
эффективны в целом ряде стандартных
ситуаций,
Линейное программирование – это
математический метод решения задачи
оптимального распределения имеющихся
ресурсов (денег, материалов, времени)
для достижения определённой цели
(наибольшего дохода или наименьших
издержек), Программированиев данном
термине имеет смыслпланирования,Линейноеозначает, что ищется
экстремум линейной целевой функции при
линейных ограничениях (линейных
уравнениях или линейных неравенствах),
Общие ситуации, в которых линейное
программирование применяется часто и
эффективно:
задачи о составлении смеси, цель
которых заключается в выборе наиболее
экономичной смеси ингредиентов (руды,
нефти, пищевых продуктов и др,) при учёте
ограничений на физический или химический
состав смеси и на наличие необходимых
материалов;
задачи производства, целью которых
является подбор наиболее выгодной
производственной программы выпуска
одного или нескольких видов продукции
при использовании некоторого числа
ограниченных источников сырья;
задачи распределения, цель которых
состоит в том, чтобы организовать
доставку материалов от некоторого числа
источников к некоторому числу потребителей
так, чтобы оказались минимальными либо
расходы по этой доставке, либо время
затрачиваемое на неё, либо некоторая
комбинация того и другого, В простейшем
виде это задача о перевозках (транспортная
задача),
Наиболее распространённым методом
решения задачи линейного программирования
является симплекс-метод, В простейшем
случае, когда число переменных равно
двум, удобен простой и наглядныйграфический метод,
1, Общая задача линейного программирования
Задача линейного программирования
состоит в составлении плана максимизирующего
или минимизирующего некую линейную
функцию при ограничениях в виде линейных
уравнений или линейных неравенств:
найти вектор
,
максимизирующий (минимизирующий) функцию
(1)
и удовлетворяющий условиям
(2)
Линейная функция
называетсяцелевой функциейзадачи, Условия
(2) называются ограничениями задачи,
Любое решение системы ограничений ЗЛП
называется допустимымпланом,
Допустимый план, максимизирующий или
минимизирующий целевую функцию называется
оптимальным,План, у которого отличным от нуля компонентам соответствует система линейно независимых векторов, называется опорным планом,
Теорема,Множество планов задачи
линейного программирования является
выпуклым множеством,
Теорема,Оптимальный план задачи
линейного программирования находится
в крайней точке выпуклого множества
планов, Если оптимальный план находится
в двух крайних точках выпуклого множества
планов, то он находится также и в любой
точке, являющейся выпуклой комбинацией
этих крайних точек
