Файл: Решение одноиндексных оптимизационных задач Цель работы научиться решать одноиндексные оптимизационные задачи производства.docx
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 30.11.2023
Просмотров: 703
Скачиваний: 3
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
В задаче требуется найти оптимальный план раскроя ДСП, обеспечивающийвыход планового числа заготовок при минимальных суммарных отходах от раскроя всехплит. Инымисловами,взадаченеобходимоопределить,сколькоДСПследуетраскроитьпо тому или иному варианту раскроя, чтобы нарезать требуемое число заготовок и приэтом отходы были быминимальными.Математическаямодельзадачи,заключающаясявминимизациицелевойфункцииF=0,5x1+0,6x2+0,4x3+0,2x4+0,3x5 (2.8)приограничениях,представленныхввидесистемылинейныхнеравенств: (2.9)при x j ≥0 (j =1,2,3,4,5)или то же в общемвидеF=c1x1+ c2x2+…+ cnxn.=min (2.10) (2.11)при x j ≥0 ( j =1,2,..., n)ипри bi ≥0 (i =1,2,...,m).Этиисходныенеравенстванадопреобразоватьвравенстваснеотрицательными неизвестными. Для этого надо ввести дополнительные неотрицательные неизвестныех6,x7,х8иx9(авобщемслучаеxn+1,хп+2,…,хп+т)внеравенства-ограничениятак,чтобы
они превратились вуравнения.В данной задаче неравенства имеют противоположный смысл по сравнениюс неравенствами, рассмотренными ранее, т. е. левые части должныбыть не менее правых частей, поэтому дополнительные неотрицательные неизвестныедолжны вводиться со знаком плюс в правые части неравенств, либо со знаком минус(с коэффициентами -1) в левые части этихнеравенств-ограничений.Итак, вышеуказанные системы неравенств, преобразуются вследующие эквивалентные системы линейныхуравнений: (2.12)F=0,5x1+0,6x2+0,4x3+0,2x4+0,3x5-0x6-0x7-0x8-0x9=minприxj≥0 (2.13)или,вобщемвиде, (2.14)F=c1x1+…+ cnxn.+0xn+1+…+0xn+m=min. (2.15)В матрицах систем уравнений такого вида не содержится единичной подматрицы, вкоторойдиагональныеэлементыбылибыравныединице,аостальные -нулю.Вних содержатся подматрицы,
соответствующие дополнительным неизвестным,с диагональными элементами, равными -1. Поэтому, если принятьдополнительные неизвестные в качестве базисных, то они окажутся отрицательными (х1 = х2 = х3 = х4 = x5 =0, х6= -500, х7 = -1000, х8 = -200, x9 = -400), т. е. не будут удовлетворятьусловиям неотрицательности всех переменных. Следовательно, здесь мы не имеемявной неотрицательной исходнойпрограммы.Для решения задачи необходима единичная подматрица (сположительными элементами). Чтобы получить ее, надо ввести еще одну группу неизвестных,число которыхравночислуисходныхнеравенств(илиуравнений),по одному такому неизвестному на каждое неравенство (или уравнение). Этиновые неизвестные в отличие от дополнительных - уравновешивающих —называют
искусственными. В данной задаче обозначим их через y1, у2, у3, y4и введем их в левыечасти уравнений со знакомплюс.Симплексные уравнения исходных условий в окончательном виде,допускающем перенесение коэффициентов при неизвестных непосредственно впервоначальную симплекcную таблицу,будут1: (2.16)В этих уравнениях имеется единичная подматрица и все неизвестныесчитаются неотрицательными. Дальнейшее решение задачи может быть выполнено двумяспособами.Первый способ заключается в отыскании какой-то программы (опорногоплана) основной задачи (2.8), (2.9) посредством решения вспомогательной задачи,которая заключается в нахождении минимума целевойфункции:F’=y1+ y2+ y3+y4=min (2.17)или, в расширенномвиде,F’=0x1+0x2+0x3+0x4+0x5+0x6+0x7+0x8+0x9+1y1+1y2+1y3+1y4=minЕсли получится минимум этой целевой функции, равный нулю (F' = 0), то врешении этойвспомогательнойзадачи(3.24;3.25)получится искомая программаисходнойзадачи(3.16;3.17).Второй способ решения этой задачи. Он в значительной мере отличается от первого хотя бы тем, что здесь не требуется решать вспомогательную задачу для отыскания опорного плана (какого-то решения) исходной задачи. Этот способ позволяет нам приступить к непосредственному решению исходной задачи, поскольку в симплексных уравнениях, представленных в окончательной форме, имеется единичная подматрица (2.16).
Целевая функция была представлена выражением(2.8):F=0,5x1+0,6x2+0,4xз+0,2x4+0,3x5=minИскусственные переменные у1, y2, y3 и y4входят в первоначальную программу,с которой начинается процесс решения задачи, как базисные сположительными значениями, но по ходу решения они постепенно исключаются из базисныхпеременных. Оптимальной программа станет не раньше, чем все эти искусственныепеременные перейдут из базисных в свободные. Чтобы это обеспечить, искусственныенеизвестные вводятся в уравнение целевой функции с коэффициентами (ценами), равнымиМ.Под Мпонимается величина больше любого другого сколько угоднобольшего напередзаданногочисла.Такимобразом,мыблокируемискусственныенеизвестные,т.е. введением коэффициентов Ммы избавляемся от влияния искусственных переменныхна истинную оптимальную программу. Действительно, как только хотя бы однаиз искусственных переменных в программе положительна, значение целевойфункции расширенной задачи (с искусственными переменными), соответствующимподбором положительного числа М, может быть сделано больше любого значения целевойфункции (2.8) исходной задачи при любых значениях основных переменныхх1, x2, x3, x4,х
они превратились вуравнения.В данной задаче неравенства имеют противоположный смысл по сравнениюс неравенствами, рассмотренными ранее, т. е. левые части должныбыть не менее правых частей, поэтому дополнительные неотрицательные неизвестныедолжны вводиться со знаком плюс в правые части неравенств, либо со знаком минус(с коэффициентами -1) в левые части этихнеравенств-ограничений.Итак, вышеуказанные системы неравенств, преобразуются вследующие эквивалентные системы линейныхуравнений: (2.12)F=0,5x1+0,6x2+0,4x3+0,2x4+0,3x5-0x6-0x7-0x8-0x9=minприxj≥0 (2.13)или,вобщемвиде, (2.14)F=c1x1+…+ cnxn.+0xn+1+…+0xn+m=min. (2.15)В матрицах систем уравнений такого вида не содержится единичной подматрицы, вкоторойдиагональныеэлементыбылибыравныединице,аостальные -нулю.Вних содержатся подматрицы,
соответствующие дополнительным неизвестным,с диагональными элементами, равными -1. Поэтому, если принятьдополнительные неизвестные в качестве базисных, то они окажутся отрицательными (х1 = х2 = х3 = х4 = x5 =0, х6= -500, х7 = -1000, х8 = -200, x9 = -400), т. е. не будут удовлетворятьусловиям неотрицательности всех переменных. Следовательно, здесь мы не имеемявной неотрицательной исходнойпрограммы.Для решения задачи необходима единичная подматрица (сположительными элементами). Чтобы получить ее, надо ввести еще одну группу неизвестных,число которыхравночислуисходныхнеравенств(илиуравнений),по одному такому неизвестному на каждое неравенство (или уравнение). Этиновые неизвестные в отличие от дополнительных - уравновешивающих —называют
искусственными. В данной задаче обозначим их через y1, у2, у3, y4и введем их в левыечасти уравнений со знакомплюс.Симплексные уравнения исходных условий в окончательном виде,допускающем перенесение коэффициентов при неизвестных непосредственно впервоначальную симплекcную таблицу,будут1: (2.16)В этих уравнениях имеется единичная подматрица и все неизвестныесчитаются неотрицательными. Дальнейшее решение задачи может быть выполнено двумяспособами.Первый способ заключается в отыскании какой-то программы (опорногоплана) основной задачи (2.8), (2.9) посредством решения вспомогательной задачи,которая заключается в нахождении минимума целевойфункции:F’=y1+ y2+ y3+y4=min (2.17)или, в расширенномвиде,F’=0x1+0x2+0x3+0x4+0x5+0x6+0x7+0x8+0x9+1y1+1y2+1y3+1y4=minЕсли получится минимум этой целевой функции, равный нулю (F' = 0), то врешении этойвспомогательнойзадачи(3.24;3.25)получится искомая программаисходнойзадачи(3.16;3.17).Второй способ решения этой задачи. Он в значительной мере отличается от первого хотя бы тем, что здесь не требуется решать вспомогательную задачу для отыскания опорного плана (какого-то решения) исходной задачи. Этот способ позволяет нам приступить к непосредственному решению исходной задачи, поскольку в симплексных уравнениях, представленных в окончательной форме, имеется единичная подматрица (2.16).
Целевая функция была представлена выражением(2.8):F=0,5x1+0,6x2+0,4xз+0,2x4+0,3x5=minИскусственные переменные у1, y2, y3 и y4входят в первоначальную программу,с которой начинается процесс решения задачи, как базисные сположительными значениями, но по ходу решения они постепенно исключаются из базисныхпеременных. Оптимальной программа станет не раньше, чем все эти искусственныепеременные перейдут из базисных в свободные. Чтобы это обеспечить, искусственныенеизвестные вводятся в уравнение целевой функции с коэффициентами (ценами), равнымиМ.Под Мпонимается величина больше любого другого сколько угоднобольшего напередзаданногочисла.Такимобразом,мыблокируемискусственныенеизвестные,т.е. введением коэффициентов Ммы избавляемся от влияния искусственных переменныхна истинную оптимальную программу. Действительно, как только хотя бы однаиз искусственных переменных в программе положительна, значение целевойфункции расширенной задачи (с искусственными переменными), соответствующимподбором положительного числа М, может быть сделано больше любого значения целевойфункции (2.8) исходной задачи при любых значениях основных переменныхх1, x2, x3, x4,х