Тема 9. Математическое программирование.
1. Уметь построить область допустимых планов, которая задается системой линейных уравнений и неравенств. 2. Уметь построить вектор-градиент целевой функции и линию нулевого уровня. 3. Знать различные формы записи задачи линейного программирования (ЗЛП). 4. Уметь переходить от одной формы ЗЛП к другой. 5. Знать алгоритм симплекс-метода. 6. Знать критерий оптимальности решения ЗЛП на максимум. 7. Уметь для ЗЛП, заданной в симметричной форме, построить двойственную ей задачу. 8. Уметь построить начальный опорный план транспортной задачи (ТЗ) методом северо-западного угла и методом минимального элемента. 9. Знать критерий оптимальности решения ТЗ. 10. Уметь перейти к нехудшему опорному решению ТЗ. Задачи для самостоятельного выполнения ЗЛП решить графически: 1. 2. 3. 4. 5. ЗЛП решить симплекс-методом: 1. Для приведённых ЗЛП написать двойственную: 1. 2. 3. 4. 5.
Составить первоначальный план ТЗ методом северо-западного угла и(или) методом минимального элемента по следующим данным: 1 Таблица 9.1
2 Таблица 9.2
3 Таблица 9.3
4 Таблица 9.4
5 Таблица 9.5
Образцы решения ЗЛП: Задание 1 Решить задачу линейного программирования графическим методом
Решение 1. Построим область допустимых решений. Для этого запишем уравнения сторон многоугольника допустимых решений, положив в ограничениях вместо неравенств равенства Строим прямые, определяемые уравнениями (I) – (Y) и определяем полуплоскости, удовлетворяющие исходным неравенством. Пересечение этих полуплоскостей образует пятиугольник АВСDE.
2. Строим вектор 3. Проводим линию нулевого уровня 4. Перемещаем линию нулевого уровня в направлении вектора 5. Найдем координаты точек Е и С. Е – точка пересечения прямых (IY) и (Y).
Е(2; 2), С – точка пересечения прямых (III) и (II).
С ( Ответ: Задание 2 Для изготовления 4-х видов продукции используют три вида сырья. Количество сырья вида
Требуется: 1) составить экономико-математическую модель задачи, пользуясь которой, можно найти план выпуска продукции, при котором общая прибыль 2) симплексным методом найти оптимальный план выпуска продукции и максимальную величину прибыли; 3) составить задачу, двойственную к исходной, и пояснить ее экономическую суть. Используя теорию двойственности, установить соответствие между переменными прямой и двойственной задач, найти двойственные оценки; 4) с помощью двойственных оценок исследовать: а) степень полезности отдельных видов ресурсов в условиях производства; б) величину финансовых потерь в расчете на единицу продукции в случае, если предприятие вынуждено будет производить невыгодные ему виды продукции. При необходимости такого производства обосновать цены на готовую продукцию.
Решение 1) Составим экономико-математическую модель задачи. Обозначим через Х1, Х2, Х3, Х4 количество весовых единиц четырех видов продукции, которые планируется изготовить. Тогда прибыль, полученная от реализации выпущенной продукции, будет равна:
Переменные
По смыслу задачи
Таким образом, условия (9. 1) – (9.3) определяют экономико-математическую модель поставленной задачи. 2) Решим задачу линейного программирования (9.1)–(9.3) симплексным методом. Для этого перейдем к канонической форме записи задачи линейного программирования, введя дополнительные (балансовые) переменные
Составим начальную симплексную таблицу по данным математической модели (9. 1′)–(9. 3′). Таблица 9.6
Этой симплексной таблице соответствует опорный план
Следовательно, из базиса выводим переменную Х7, а соответствующий столбец называем разрешающим. На пересечении разрешающего столбца и разрешающей строки находится разрешающий (ключевой) элемент 4. С помощью разрешающего элемента выполняем симплексные преобразования, которые приводят к таблице 9.7.
Таблица 9.7
Полученный опорный план
Таким образом, в качестве разрешающей строки необходимо взять строку, соответствующую переменной Х5. Это означает, что базисную переменную Х5 необходимо заменить свободной переменной Х4. Проводя симплексные преобразования, мы придем к таблице 9.8. Таблица 9.8
В полученной симплексной таблице в индексной строке нет отрицательных элементов, поэтому опорный план Вывод. Максимальная возможная прибыль предприятия (в имеющихся условиях) будет 125 денежных единиц, если оно произведёт 5 единиц измерения продукции 2-го вида и 10 единиц измерения продукции 4-го вида, а продукцию 1-го и 3-го видов вообще выпускать не будет. При таком плане производства ресурсы 1-го и 3-го видов будут израсходованы полностью ( 3) Составим математическую модель двойственной задачи. Запишем матрицу математической модели исходной задачи.
Тогда, чтобы получить матрицу математической модели двойственной задачи, необходимо матрицу А транспонировать (т.е. поменять местами соответствующие строки и столбцы).
Обозначив через
Перейдем к канонической форме записи математической модели двойственной задачи введя дополнительные (балансовые) переменные
Из 1-й теоремы двойственности следует, что если решена одна из пары взаимодвойственных задач симплексным методом, то по последней симплексной таблице можем получить и компоненты оптимального плана двойственной задачи (они находятся в индексной строке). При этом необходимо использовать соответствие между переменными пары взаимодвойственных задач:
Для нашей задачи имеем оптимальный план двойственной задачи:
4) Оценки для 1-го и 3-го видов ресурсов положительные. Это указывает, что эти виды ресурсов наиболее дефицитные (и используются полностью). Увеличение объема ресурса 1-го вида на одну единицу измерения позволило бы получить увеличение максимальной прибыли предприятия на 0,88 денежных единиц; а для ресурса 3-го вида соответственно на 1,81 денежную единицу. Равенство нулю оценки для ресурса 2-го вида ( Дополнительные двойственные переменные являются мерой убыточности продукции, которую согласно оптимальному плану нецелесообразно выпускать. Так как Так как Задание 3. Имеется три поставщика и пять потребителей некоторой продукции. Количество груза
Составить экономико-математическую модель задачи и найти методом потенциалов оптимальный план перевозки груза, при котором общие транспортные затраты будут наименьшими. Решение Строим математическую модель задачи. Через Хij обозначим объем продукции, доставленной от поставщика Ai (i=l,2,3) потребителю Bj (
310+360+230=140+190+180+170+220 = 900.
Значит, задача закрытого типа и имеет решение. Математическая модель задачи принимает вид:
Строим начальную распределительную таблицу 9. 9: Таблица 9.9
Построенному опорному решению отвечают затраты: Z1 = 90∙2+220∙1+100∙8+90∙6+170∙10+140∙1+90∙2 = 3760.
Проверим полученный опорный план на оптимальность. Для этого i-й строке и j-му столбцу ставим в соответствие числа Ui и Vj (потенциалы). Для каждой базисной переменной Хij потенциалы должны удовлетворять условию Ui +Vj = Сij. Получаем систему:
U1+V3 = 2, Так как система состоит из 7 уравнений, а неизвестных U1+V5 = l, 8, то, чтобы найти численное решение этой системы, U2+V2 = 8, одно из неизвестных зададим произвольно, тогда U2+V3 = 6, остальные переменные найдутся из системы однозначно. U2+V4 = 10, U3+V1 = 1, U3+V2 = 2. Пусть U2 = 0, тогда V2 = 8, V3 = 6, V4 = 10, U1 = − 4, U3 = −6, V1 = 7, V5 = 5. Теперь для небазисных переменных (свободных клеток) найдем оценки
В силу критерия оптимальности опорного плана (все оценки Sij неотрицательны) делаем вывод, что построенный план не оптимален, т.к. среди оценок есть отрицательные. В базис введем переменную Х21 (отвечающую наибольшей по модулю отрицательной оценке) и строим замкнутый контур с вершинами в загруженных клетках. Присваиваем клеткам в вершинах контура поочередно по часовой стрелке знаки " + " и " – ", начиная с (2,1), которой присваиваем знак " + ". Выбираем наименьшее значение из клеток со знаком " – " (min (140,100) = 100) и перераспределим продукцию вдоль контура: прибавляя 100 к значениям в клетках со знаком "+" и вычитая из значений в клетках со знаком " – ". В результате приходим к таблице 9.10.
Таблица 9. 10
Полученному решению отвечают затраты: Z2 = 90∙2+220∙1+100∙3+90∙6+170∙10+40∙1+190∙2=3360. Проверяем полученный план на оптимальность и получаем, что S34 = –3 < 0. Значит, решение неоптимальное и строим в таблице 12 новый цикл пересчета для клетки (3,4). Так как min(170,40)=40=Х31,то перераспределяем продукцию вдоль контура, прибавляя 40 к значениям в клетках со знаком " + " и вычитая из значений в клетках со знаком " – ". В результате получаем таблицу 9. 11.
Таблица 9. 11
Полученному решению отвечают затраты: Z3 = 90∙2+220∙l+140∙3+90∙6+130∙10+190∙2+40∙5=3240. Аналогично предыдущему проверяем полученный план на оптимальность. Получаем, что S14 = – 2 < 0. Теперь для улучшения плана загрузим клетку (1,4). В итоге приходим к таблице 9.12.
Таблица 9.12
Z4 = 90∙4+220∙l+140∙3+180∙6+40∙10+190∙2+40∙5=3060. Среди оценок свободных клеток имеем S25 = –2<0, следовательно, полученный план перевозок не является оптимальным, и для его улучшения необходимо загрузить клетку (2,5). В итоге вычислений приходим к таблице 9.13.
Таблица 9.13
Z5 = 130∙4+180∙l+140∙3+180∙6+40∙5+190∙2+40∙5=2980. Полученный план оказывается оптимальным, так как все оценки незагруженных клеток неотрицательны. По этому плану перевозок 1–й поставщик отправляет 130 ед. продукции потребителю В4 и 180 ед. – B5; 2–й поставщик – 140 ед. потребителю В1, 180 ед. потребителю B3 и 40 ед. потребителю В5; 3–й поставщик – 190 ед. потребителю B2 и 40 ед. потребителю В4. Вопросы для подготовки к экзамену
Воспользуйтесь поиском по сайту: ![]() ©2015 - 2025 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...
|