27 август 2017 г. в 14:20 ч

Решението е директно и двоен проблем линейно програмиране използвайки Python

Въведение

Трябва да се отбележи, че методите за решаване на проблеми с линейно програмиране включват не към икономиката, а към математиката и компютърните технологии.В същото време икономистът трябва да осигури най-удобните условия за диалог с подходящия софтуер. От своя страна, такива условия могат да бъдат осигурени само от динамично развиващи се и интерактивни среди за разработка, които имат в своя арсенал набор от библиотеки, необходими за решаване на подобни проблеми. Една от които среди за разработка софтуеропределено е Python.

Формулиране на проблема

Публикациите разглеждат решения на проблеми с директна оптимизация с помощта на метода на линейно програмиране и предлагат разумен избор на решаващия инструмент scipy. оптимизиране.

Известно е обаче, че всеки проблем с линейно програмиране съответства на така наречения разграничен (двоен) проблем. При нея в сравнение с пряката задача редовете се превръщат в колони, неравенствата сменят знака, вместо максимум се търси минимум (или обратното, вместо минимум се търси максимум). Задачата, двойна към двойната, е самата оригинална задача.

Решаването на двойния проблем е много важно за анализа на използването на ресурси. В тази публикация ще бъде доказано, че оптималните стойности на целевите функции в оригиналните и двойните проблеми съвпадат (т.е. максимумът в първоначален проблемсъвпада с минимума в дуала).

Оптималните стойности на разходите за материали и труд ще бъдат оценени според техния принос към целевата функция. Резултатът ще бъде „обективно определени оценки“ на суровини и труд, които не съвпадат с пазарните цени.

Решение на пряката задача за оптималната производствена програма

Имайки в предвид високо нивоматематическо обучение на по-голямата част от потребителите на този ресурсНяма да представям балансови уравнения с горни и долни ограничения и въвеждане на допълнителни променливи за преход към равенства. Затова веднага ще дам обозначенията на променливите, използвани в решението:
N – брой видове произведени продукти;
m – брой видове използвани суровини;
b_ub - вектор на наличните ресурси с размерност m;
A_ub е матрица с размерност m×N, всеки елемент от която е потреблението на ресурс от тип i за производството на единица продукт от тип j;
c е векторът на печалбата от производството на единица от всеки вид продукт;
x – необходимите обеми произведени продукти от всеки вид ( оптимален планпроизводство) осигуряване на максимална печалба.

Целева функция
maxF(x)=c×x

Ограничения
A×x≤b

Числени стойности на променливите:
N=5; m=4; b_ub =; A_ub = [, , ,]; c = .

Задачи
1. Намерете x, за да осигурите максимална печалба
2. Намерете ресурсите, използвани при изпълнение на стъпка 1
3. Намерете оставащите ресурси (ако има такива), когато изпълнявате стъпка 1

За определяне на максимума (по подразбиране минимумът се определя от коефициентите целева функциятрябва да напишете c = [-25, -35,-25,-40,-30] с отрицателен знак и да игнорирате знака минус пред печалбата.

Обозначения, използвани за показване на резултатите:
х– масив от променливи стойности, които осигуряват минимума (максимума) на целевата функция;
отпуснатост– стойности на допълнителни променливи. Всяка променлива съответства на ограничение за неравенство. Стойност на променлива нула означава, че съответното ограничение е активно;
успех– Вярно, ако функциите могат да бъдат намерени оптимално решение;
състояние– състояние на решението:
0 – търсенето на оптималното решение приключи успешно;
1 – достигнато е ограничението за брой итерации;
2 – проблемът няма решения;
3 – целевата функция не е ограничена.
гнида– брой извършени итерации.

Изброяване на решението на задачата за директна оптимизация

#!/usr/bin/python # -*- кодиране: utf-8 -*- import scipy от scipy.optimize import linprog # зареждане на LP библиотека c = [-25, -35,-25,-40,-30] # списък с коефициенти на целевата функция b_ub = # списък с обеми на ресурси A_ub = [, # матрица на специфични стойности на ресурса ​​, , ] d=linprog(c, A_ub, b_ub) # търсене на решение за key,val в d.items(): print(key,val) # изход на решение if key=="x": q=#използвани ресурси print("A_ub*x",q) q1= scipy.array(b_ub)-scipy.array (q) #оставащи ресурси print(" b_ub-A_ub*x", q1)

Резултати от решаването на проблема
гнида 3
състояние 0

успех Вярно
x [ 0. 0. 18.18181818 22.72727273 150. ]
A_ub*x
b_ub-A_ub*x [0. 0. 0. 90.90909091]
забавно -5863.63636364
отпуснатост [0. 0. 0. 90.90909091]

заключения

1. Намерен е оптималният план за видовете продукти
2. Намерено действително използване на ресурси
3. Намерен е остатъкът от неизползвания четвърти тип ресурс [ 0. 0 0.0 0.0 90.909]
4. Няма нужда от изчисления съгласно стъпка 3, тъй като същият резултат се показва в променливата slack

Решение на двойствената задача върху оптималната производствена програма

Четвъртият вид ресурс в пряката задача не се използва напълно. Тогава стойността на този ресурс за предприятието се оказва по-ниска в сравнение с ресурсите, които ограничават производството, и предприятието е готово да плати повече висока ценаза придобиване на ресурси за увеличаване на печалбата.

Нека въведем ново предназначение за желаната променлива x като някаква „сенчеста“ цена, която определя стойността на даден ресурс по отношение на печалбата от продажбата на произведени продукти.

C – вектор на наличните ресурси;
b_ub е векторът на печалбата от производството на единица от всеки вид продукт;
A_ub_T – транспонирана матрица A_ub.

Целева функция
minF(x)=c×x

Ограничения
A_ub_T ×x≥ b_ub

Числени стойности и връзки за променливи:
c = ; A_ub_T транспониране (A_ub); b_ub = .

Задача:
Намерете x, показващ стойността за производителя на всеки тип ресурс.

Характеристики на решението с библиотеката scipy. оптимизиране
За да замените ограниченията отгоре с ограниченията отдолу, е необходимо да умножите двете части на ограничението по минус едно – A_ub_T ×x≥ b_ub... За целта запишете началните данни във формата: b_ub = [-25, -35,-25,-40,-30]; A_ub_T =- scipy.transpose(A_ub).

Изброяване на решението на проблема с двойната оптимизация

#!/usr/bin/python # -*- кодиране: utf-8 -*- import scipy от scipy.optimize import linprog A_ub = [, , , ] c= b_ub = [-25, -35,-25,- 40,-30] A_ub_T =-scipy.transpose(A_ub) d=linprog(c, A_ub_T, b_ub) за ключ,вал в d.items(): печат(ключ,вал)

Резултати от решаването на проблема
гнида 7
съобщение Оптимизацията е прекратена успешно.
забавно 5863.63636364
x [ 2.27272727 1.81818182 6.36363636 0. ]
отпуснатост [5.45454545 2.27272727 0. 0. 0. ]
състояние 0
успех Вярно

заключения

Следователно третият вид ресурс има най-голяма стойност за производителя този видресурсите трябва да бъдат закупени първо, след това първият и вторият тип. Четвъртият вид ресурс има нулева стойност за производителя и се купува последен.

Резултати от сравнение на преки и двойни задачи

1. Двойният проблем разширява възможностите за продуктово планиране, но с помощта на scipy. optimize се решава с два пъти повече директни итерации.
2. Променливата slack показва информация за активността на ограниченията под формата на неравенства, които могат да се използват например за анализ на баланси на суровини.
3. Директният проблем е проблем за максимизиране, а двойният проблем е проблем за минимизиране и обратно.
4. Коефициентите на целевата функция в директния проблем са ограничения в двойния проблем.
5. Ограниченията в директната задача стават коефициенти на целевата функция в двойствената.
6. Знаците на неравенствата в ограниченията са обърнати.
7. Транспонира се матрицата на системата от равенства.

Връзки

Ако има само един ограничаващ фактор (например, оскъдна машина), решение може да се намери с помощта на прости формули(вижте линка в началото на статията). Ако има няколко ограничаващи фактора, се използва методът на линейно програмиране.

Линейно програмиране- това е името дадена комбинацияинструменти, използвани в науката за управление. Този метод решава проблема с разпределянето на оскъдни ресурси между конкуриращи се дейности, за да се максимизират или минимизират някои числови стойности, като марж на вноската или разходи. В бизнеса може да се използва в области като планиране на производството максимално увеличениепечалби, избор на компоненти за минимизиране на разходите, избор на портфолио от инвестиции за максимизиране на рентабилността, оптимизиране на транспорта на стоки за намаляване на разстоянията, назначаване на персонал за максимизиране на ефективността на работата и планиране на работа за спестяване на време.

Изтеглете бележка във формат, снимки във формат

Линейното програмиране включва конструкцията математически моделразглеждания проблем. След което решението може да се намери графично (обсъдено по-долу), с използвайки Excel(ще се разглеждат отделно) или специализирани компютърни програми.

Може би изграждането на математически модел е най-много трудната частлинейно програмиране, което изисква транслирането на разглеждания проблем в система от променливи, уравнения и неравенства – процес, който в крайна сметка зависи от уменията, опита, способностите и интуицията на моделиращия.

Нека разгледаме пример за конструиране на математически модел на линейно програмиране

Николай Кузнецов управлява малък механичен завод. Следващия месец той планира да произведе два продукта (А и Б), за които специфичната маргинална печалба се оценява съответно на 2500 и 3500 рубли.

И двата продукта изискват машинна обработка, суровини и разходи за труд (Фигура 1). Производството на всяка единица продукт А отнема 3 часа. механична обработка, 16 единици суровини и 6 единици труд. Съответните изисквания за единица за продукт B са 10, 4 и 6. Никълъс прогнозира, че следващия месец той може да достави 330 часа машинна обработка, 400 единици суровини и 240 единици труд. Технологията на производствения процес е такава, че най-малко 12 единици продукт B трябва да бъдат произведени през даден месец.

Ориз. 1. Използване и осигуряване на ресурси

Николай иска да изгради модел за определяне на броя на единиците продукти A и B, които той трябва да произведе през следващия месец, за да максимизира маржа на своя принос.

Линейният модел може да бъде изграден на четири етапа.

Стъпка 1: Дефиниране на променливи

Има целева променлива (да я наречем Z), която трябва да бъде оптимизирана, тоест максимизирана или минимизирана (например печалба, приходи или разходи). Николай се стреми да максимизира маржа на вноската, следователно целевата променлива:

Z = общата пределна печалба (в рубли), получена през следващия месец в резултат на производството на продукти А и Б.

Има редица неизвестни неизвестни променливи (нека ги обозначим с x 1, x 2, x 3 и т.н.), чиито стойности трябва да бъдат определени, за да се получи оптималната стойност на целевата функция, която в нашия случай е обща пределна печалба. Този марж на приноса зависи от произведените количества продукти A и B. Стойностите на тези количества трябва да бъдат изчислени и следователно те представляват желаните променливи в модела. И така, нека обозначим:

x 1 = брой единици продукт А, произведени през следващия месец.

x 2 = брой единици продукт B, произведени през следващия месец.

Много е важно да се дефинират ясно всички променливи; Обърнете специално внимание на мерните единици и периода от време, за който се отнасят променливите.

Сцена. 2. Построяване на целевата функция

Целевата функция е линейно уравнение, което трябва да бъде максимизирано или минимизирано. Той съдържа целевата променлива, изразена с помощта на целевите променливи, т.е. Z, изразена чрез x 1, x 2 ... под формата на линейно уравнение.

В нашия пример всеки произведен продукт А носи 2500 рубли. пределна печалба, а при производството на x 1 единици от продукт A, пределната печалба ще бъде 2500 * x 1. По същия начин пределната печалба от производството на x 2 единици продукт B ще бъде 3500 * x 2. По този начин общата пределна печалба, получена през следващия месец чрез производството на x 1 единици продукт A и x 2 единици продукт B, т.е. целевата променлива Z, ще бъде:

Z = 2500 * x 1 + 3500 * x 2

Николай се стреми да максимизира този показател. По този начин целевата функция в нашия модел е:

Увеличете максимално Z = 2500 * x 1 + 3500 * x 2

Сцена. 3. Дефинирайте ограничения

Ограниченията са система линейни уравненияи/или неравенства, които ограничават стойностите на търсените променливи. Те математически отразяват наличието на ресурси, технологични фактори, пазарни условия и други изисквания. Ограниченията могат да бъдат три вида: „по-малко или равно“, „по-голямо или равно“, „строго равно“.

В нашия пример производството на продукти A и B изисква време за обработка, суровини и труд, а наличността на тези ресурси е ограничена. Производствените обеми на тези два продукта (т.е. стойностите на x 1 x 2) следователно ще бъдат ограничени от факта, че количеството ресурси, необходими в производствения процес, не може да надвишава наличните. Нека разгледаме ситуацията с времето за машинна обработка. Производството на всяка единица продукт А изисква три часа машинна обработка и ако се произведат x 1 единици, тогава ще бъдат изразходвани 3 * x 1 часа от този ресурс. Всяка единица от продукт B изисква 10 часа за производство и следователно, ако са произведени x 2 продукта, тогава ще са необходими 10 * x 2 часа. Така общото количество машинно време, необходимо за производството на x 1 единици от продукт A и x 2 единици от продукт B, е 3 * x 1 + 10 * x 2 . Това общо значениемашинното време не може да надвишава 330 часа. Математически това се записва по следния начин:

3 * x 1 + 10 * x 2 ≤ 330

Подобни съображения важат за суровините и труда, което ни позволява да запишем още две ограничения:

16 * x 1 + 4 * x 2 ≤ 400

6 * x 1 + 6 * x 2 ≤ 240

И накрая, трябва да се отбележи, че има условие, според което трябва да бъдат произведени най-малко 12 единици продукт B:

Етап 4. Писане на условия за неотрицателност

Търсените променливи не могат да бъдат отрицателни числа, което трябва да бъде написано под формата на неравенства x 1 ≥ 0 и x 2 ≥ 0. В нашия пример второто условие е излишно, тъй като по-горе беше определено, че x 2 не може да бъде по-малко от 12.

Пълен модел за линейно програмиране за производствена задачаНикола може да се запише като:

Увеличете: Z = 2500 * x 1 + 3500 * x 2

При условие, че: 3 * x 1 + 10 * x 2 ≤ 330

16 * x 1 + 4 * x 2 ≤ 400

6 * x 1 + 6 * x 2 ≤ 240

Нека разгледаме графичен метод за решаване на проблем с линейно програмиране.

Този метод е подходящ само за проблеми с две неизвестни променливи. Конструираният по-горе модел ще бъде използван за демонстриране на метода.

Осите на графиката представляват двете променливи, които представляват интерес (Фигура 2). Няма значение коя променлива по коя ос е нанесена. Важно е да изберете мащаб, който в крайна сметка ще ви позволи да създадете ясна диаграма. Тъй като и двете променливи трябва да са неотрицателни, се изчертава само 1-ви квадрант.

Ориз. 2. Линейно програмиране на графични оси

Помислете например за първото ограничение: 3 * x 1 + 10 * x 2 ≤ 330. Това неравенство описва областта под линията: 3 * x 1 + 10 * x 2 = 330. Тази права пресича оста x 1 при x 2 = 0, тоест уравнението изглежда така: 3 * x 1 + 10 * 0 = 330, а решението му: x 1 = 330 / 3 = 110

По подобен начин изчисляваме пресечните точки с осите x1 и x2 за всички ограничителни условия:

Диапазон от приемливи стойности	Граница на допустимите стойности	Пресечна точка с ос x 1	Пресечна точка с ос х 2
3 * x 1 + 10 * x 2 ≤ 330	3 * x 1 + 10 * x 2 = 330	х 1 = 110; х 2 = 0	x 1 = 0; х 2 = 33
16 * x 1 + 4 * x 2 ≤ 400	16 * x 1 + 4 * x 2 = 400	x 1 = 25; х 2 = 0	x 1 = 0; х 2 = 100
6 * x 1 + 6 * x 2 ≤ 240	6 * x 1 + 6 * x 2 = 240	х 1 = 40; х 2 = 0	x 1 = 0; х 2 = 40
x 2 ≥ 12	х 2 = 12	не пресича; върви успоредно на оста x 1	x 1 = 0; х 2 = 12

Графично първото ограничение е показано на фиг. 3.

Ориз. 3. Застрояване на района допустими решенияза първото ограничение

Всяка точка от избрания триъгълник или от неговите граници ще отговаря на това ограничение. Такива точки се наричат ​​валидни, а точки извън триъгълника се наричат ​​невалидни.

По подобен начин показваме останалите ограничения на графиката (фиг. 4). Стойностите на x 1 и x 2 върху или вътре в защрихованата област ABCDE ще задоволят всички ограничения на модела. Този регион се нарича регион на осъществимите решения.

Ориз. 4. Област на възможните решения за модела като цяло

Сега, в областта на възможните решения, е необходимо да се определят стойностите x 1 и x 2, които максимизират Z. За да направите това, в уравнението на целевата функция:

Z = 2500 * x 1 + 3500 * x 2

разделете (или умножете) коефициентите преди x 1 и x 2 с едно и също число, така че получените стойности да попадат в диапазона, отразен на графиката; в нашия случай този диапазон е от 0 до 120; така че шансовете могат да бъдат разделени на 100 (или 50):

Z = 25x 1 + 35x 2

след това присвоете на Z стойност, равна на произведението на коефициентите преди x 1 и x 2 (25 * 35 = 875):

875 = 25x 1 + 35x 2

и накрая, намерете точките на пресичане на правата с осите x 1 и x 2:

Нека начертаем това целево уравнение върху графика, подобна на ограниченията (фиг. 5):

Ориз. 5. Прилагане на целевата функция (черна пунктирана линия) към областта на възможните решения

Стойността Z е постоянна по цялата линия на целевата функция. За да намерите стойностите x 1 и x 2, които максимизират Z, трябва паралелно да преместите линията на целевата функция до точка в границите на областта на възможните решения, която се намира на максималното разстояние от оригиналната линия на целевата функция нагоре и надясно, т.е. до точка С (фиг. 6).

Ориз. 6. Линията на целевата функция е достигнала максимум в областта на възможните решения (в точка C)

Можем да заключим, че оптималното решение ще бъде разположено в една от крайните точки на зоната на решение. Коя ще зависи от наклона на целевата функция и от това какъв проблем решаваме: максимизиране или минимизиране. По този начин не е необходимо да се начертае целевата функция - всичко, което е необходимо, е да се определят стойностите на x 1 и x 2 във всяка крайна точка чрез четене от диаграма или чрез решаване на подходящата двойка уравнения. Намерените стойности на x 1 и x 2 след това се заместват в целевата функция, за да се изчисли съответната стойност на Z. Оптималното решение е това, което получава максималната стойност на Z при решаване на проблема за максимизиране и минималната при решаване проблемът с минимизирането.

Нека да определим например стойностите на x 1 и x 2 в точка C. Обърнете внимание, че точка C се намира в пресечната точка на линиите: 3x 1 + 10x 2 = 330 и 6x 1 + 6x 2 = 240. Решаването на тази система от уравнения дава: x 1 = 10, x 2 = 30. Резултатите от изчислението за всички върхове на областта на допустимите решения са дадени в таблицата:

Точка	Стойност х 1	Стойност х 2	Z = 2500x 1 + 3500x 2
А	22	12	97 000
IN	20	20	120 000
СЪС	10	30	130 000
д	0	33	115 500
д	0	12	42 000

По този начин Николай Кузнец трябва да планира за следващия месец производството на 10 продукта А и 30 продукта Б, което ще му позволи да получи пределна печалба от 130 хиляди рубли.

Накратко същността графичен методрешенията на проблемите с линейното програмиране могат да бъдат формулирани по следния начин:

1. Начертайте две оси на графиката, представящи двата параметъра на решението; начертайте само 1-ви квадрант.
2. Определете координатите на точките на пресичане на всички гранични условия с осите, като замествате последователно стойностите x 1 = 0 и x 2 = 0 в уравненията на граничните условия.
3. Нанесете ограничителните линии на модела върху графиката.
4. Определете региона на графиката (наречен регион на възможно решение), който отговаря на всички ограничения. Ако няма такъв регион, тогава моделът няма решение.
5. Определете стойностите на целевите променливи в крайните точки на зоната за вземане на решение и във всеки случай изчислете съответната стойност на целевата променлива Z.
6. За проблеми с максимизиране решението е точката, в която Z е максимално; за проблеми с минимизиране решението е точката, в която Z е минимум.

Проектни параметри. Този термин означава независими променливи параметри, които напълно и недвусмислено определят решавания проектен проблем. Проектните параметри са неизвестни величини, чиито стойности се изчисляват по време на процеса на оптимизация. Всички основни или производни величини, които служат за количествено описание на системата, могат да служат като параметри на дизайна. Така че това могат да бъдат неизвестни стойности на дължина, маса, време, температура. Броят на проектните параметри характеризира степента на сложност на даден проектен проблем. Обикновено броят на проектните параметри се означава с n, а самите проектни параметри с x със съответните индекси. Така n проектни параметри на този проблем ще бъдат означени с

X1, X2, X3,...Xp.

Трябва да се отбележи, че проектните параметри могат да бъдат посочени като вътрешни контролируеми параметри в някои източници.

Целева функция. Това е израз, чиято стойност инженерът се стреми да направи максимална или минимална. Целевата функция ви позволява да сравните количествено две алтернативни решения. От математическа гледна точка целевата функция описва някаква (n+1)-мерна повърхност. Стойността му се определя от проектните параметри

M = M (x1,x2,…,xn).

Примери за обективни функции, често срещани в инженерната практика, са цена, тегло, здравина, размери, ефективност. Ако има само един проектен параметър, тогава целевата функция може да бъде представена чрез крива в равнината (фиг. 1). Ако има два проектни параметъра, тогава целевата функция ще бъде изобразена като повърхност в триизмерно пространство (фиг. 2). С три или повече параметри на проектиране, повърхностите, определени от целевата функция, се наричат ​​хиперповърхности и не могат да бъдат изобразени с конвенционални средства. Топологичните свойства на повърхността на целевата функция играят голяма роля в процеса на оптимизация, тъй като изборът на най-ефективния алгоритъм зависи от тях.

Фигура 1. Едномерна целева функция.

Фигура 2. Двумерна целева функция.

Целевата функция в някои случаи може да приеме най-неочаквани форми. Например, тя не винаги може да бъде изразена в затворена математическа форма; в други случаи тя може да бъде частично линейна функция. Задаването на целева функция понякога може да изисква таблица с технически данни (например таблица за състоянието на водната пара) или може да изисква експеримент. В някои случаи параметрите на дизайна приемат само цели числа. Пример за това е броят на зъбите в зъбното колело или броят на болтовете във фланеца. Понякога проектните параметри имат само две значения – да или не. Качествените параметри, като удовлетворението, изпитвано от купувача, закупил продукта, надеждност, естетика, са трудни за отчитане в процеса на оптимизация, тъй като е почти невъзможно да се характеризират количествено. Въпреки това, в каквато и форма да е представена целевата функция, тя трябва да бъде недвусмислена функция на проектните параметри.

Редица оптимизационни проблеми изискват въвеждането на повече от една целева функция. Понякога един от тях може да е несъвместим с другия. Пример за това е проектирането на самолети, където е необходимо едновременно да се осигури максимална здравина, минимално тегло и минимални разходи. В такива случаи дизайнерът трябва да въведе система от приоритети и да присвои определен безразмерен фактор на всяка целева функция. В резултат на това се появява „компромисна функция“, която позволява използването на една съставна целева функция по време на процеса на оптимизация.

Търсене на минимум и максимум. Някои оптимизационни алгоритми са предназначени да намерят максимума, други - да намерят минимума. Въпреки това, независимо от вида на проблема с екстремума, който се решава, можете да използвате същия алгоритъм, тъй като проблемът с минимизирането може лесно да се превърне в проблем с търсене на максимум чрез обръщане на знака на целевата функция. Тази техника е илюстрирана на фиг. 3.

Фигура 3. Когато знакът на целевата функция се промени на противоположния в минимален проблем, това го превръща в максимален проблем.

Дизайн пространство. Това е името на областта, дефинирана от всички n параметри на дизайна. Пространството за проектиране не е толкова голямо, колкото може да изглежда, тъй като обикновено е ограничено от редица условия, свързани с физическото естество на проблема. Ограниченията може да са толкова силни, че проблемът да няма нито едно задоволително решение. Ограниченията се делят на две групи: ограничения - равенство и ограничения - неравенство.

Ограниченията за равенство са зависимости между проектните параметри, които трябва да се вземат предвид при намиране на решение. Те отразяват законите на природата, икономиката, правото, преобладаващите вкусове и достъпност необходими материали. Броят на ограниченията - равенства може да бъде всякакъв. Приличат на

C1 (X1, X2, X3, . . ., Xn) = 0,

C2 (X1, X2, X3, . . ., X n) = 0,

..……………………………..

Cj(X1, X2, X 3,..., Xn) = 0.

Ограниченията на неравенствата са специален тип ограничения, изразени чрез неравенства. В общия случай те могат да бъдат колкото искате и всички имат формата

z1 ?r1(X1, X2, X3, . . ., Xn) ?Z1

z2 ?r2(X1, X2, X3, . . ., Xn) ?Z2

………………………………………

zk ?rk(X1, X2, X3, . . ., Xn) ?Zk

Трябва да се отбележи, че много често поради ограничения оптимална стойностцелевата функция не се постига, когато нейната повърхност има нулев градиент. Често Най-доброто решениесъответства на една от границите на зоната за проектиране.

Преки и функционални ограничения. Преките ограничения имат формата

xнi? xi? xвi в i? ,

където xнi, xвi - минимум и максимум валидни стойности i-ти контролиран параметър; n е размерността на пространството на контролираните параметри. Например за много обекти параметрите на елементите не могат да бъдат отрицателни: xнi ? 0 ( геометрични размери, електрическо съпротивление, маса и т.н.).

Функционалните ограничения, като правило, представляват условия за изпълнение на изходни параметри, които не са включени в целевата функция. Функционалните ограничения могат да бъдат:

• 1) вид равенства
• w(X) = 0; (2.1)
• 2) вид неравенства

tz (X) › 0, (2.2)

където w(X) и q(X) са векторни функции.

Форма за преки и функционални ограничения валидна площТърсене:

ХД = (Х | w(Х) = 0, ц (Х)›0, xi › xнi ,

xi ‹ xвi за i ? ).

Ако ограниченията (2.1) и (2.2) съвпадат с условията на производителност, тогава допустимата зона се нарича още зона на производителност на XP.

Всяка от точките X, принадлежащи на CD, е възможно решение на задачата. Параметричният синтез често се поставя като проблем за определяне на някое от възможните решения. Много по-важно е обаче да се реши проблемът с оптимизацията - да се намери оптималното решение сред осъществимите.

Локален оптимум. Това е името на точката в дизайнерското пространство, в която има целевата функция най-висока стойноств сравнение със стойностите му във всички други точки в непосредствена близост. Фигура 4 показва едномерна целева функция, която има два локални оптимума. Често проектното пространство съдържа много локални оптимуми и трябва да се внимава да не се обърка първият с оптималното решение на проблема.

Фигура 4. Произволна целева функция може да има няколко локални оптимума.

Глобалният оптимум е оптималното решение за цялото дизайнерско пространство. То е по-добро от всички други решения, съответстващи на локалните оптимуми, и това е, което дизайнерът търси. Възможно е да има няколко равни глобални оптимума, разположени в различни частидизайнерско пространство. Това ви позволява да избирате най-добър вариантна равни оптимални опциипо целева функция. IN в такъв случайдизайнерът може да избере опция интуитивно или въз основа на сравнение на получените опции.

Избор на критерии. Основният проблем при поставянето на екстремални задачи е формулирането на целевата функция. Трудността при избора на целева функция се крие във факта, че всеки технически обект първоначално има векторен характер на критериите за оптималност (мултикритерии). Освен това, подобряването на един от изходните параметри, като правило, води до влошаване на другия, тъй като всички изходни параметри са функции на едни и същи контролирани параметри и не могат да се променят независимо един от друг. Такива изходни параметри се наричат ​​конфликтни параметри.

Трябва да има една целева функция (принцип на уникалност). Намаляването на многокритериален проблем до еднокритериален проблем се нарича конволюция на векторен критерий. Проблемът за намиране на неговия екстремум се свежда до проблема математическо програмиране. В зависимост от това как са избрани и комбинирани изходните параметри в скаларната качествена функция, се разграничават частични, адитивни, мултипликативни, минимаксни, статистически критерии и други критерии. IN техническо заданиеза проектиране на технически обект са посочени изисквания за основните изходни параметри. Тези изисквания са изразени под формата на конкретни числени данни, обхват на тяхното изменение, условия на работа и приемлив минимум или максимални стойности. Необходимите връзки между изходните параметри и техническите изисквания (TR) се наричат ​​условия на работа и се записват във формата:

yi< TTi , i О ; yi >TTj, j O;

yr = TTr ± ?yr; r O .

където yi, yj, yr - набор от изходни параметри;

TTi, TTj, TTr - необходимите количествени стойности на съответните изходни параметри съгласно техническите спецификации;

Yr е допустимото отклонение на r-тия изходен параметър от стойността на TTr, посочена в техническите спецификации.

Условията на работа са от решаващо значение при развитието технически средства, тъй като задачата за проектиране е да се избере проектно решение, в което по най-добрия начинвсички работни условия са изпълнени в целия диапазон на промените външни параметрии при изпълнение на всички изисквания на техническите спецификации.

Конкретни критерии могат да се използват в случаите, когато сред изходните параметри може да се идентифицира един основен параметър yi(X), който най-пълно отразява ефективността на проектирания обект. Този параметър се приема като целева функция. Примери за такива параметри са: за енергийно съоръжение - мощност, за технологична машина - производителност, за превозно средство- товароносимост. За много технически обектиТози параметър е цената. Условията на работа на всички останали изходни параметри на обекта се наричат ​​функционални ограничения. Оптимизацията, базирана на такава формулировка, се нарича оптимизация по определен критерий.

Предимството на този подход е неговата простота; значителен недостатък е, че може да се получи голяма граница на ефективност само за основния параметър, който се приема като целева функция, а други изходни параметри изобщо няма да имат граници.

Критерият за претеглена добавка се използва, когато условията на изпълнение позволяват да се разграничат две групи изходни параметри. Първата група включва изходни параметри, чиито стойности трябва да бъдат увеличени по време на процеса на оптимизация y+i(X) (производителност, устойчивост на шум, вероятност безпроблемна работаи т.н.), във втория - изходни параметри, чиито стойности трябва да бъдат намалени y-i (X) (разход на гориво, продължителност на преходния процес, превишаване, отместване и др.). Комбинирането на няколко изходни параметъра, които обикновено имат различни физически измерения, в една скаларна целева функция изисква предварително нормализиране на тези параметри. Методите за нормализиране на параметрите ще бъдат разгледани по-долу. Засега ще приемем, че всички y(X) са безразмерни и сред тях няма такива, които да отговарят на условия за изпълнение от типа равенство. Тогава, в случай на минимизиране на целевата функция, конволюцията на векторния критерий ще има формата

където aj>0 е тегловен коефициент, който определя степента на важност на j-тия изходен параметър (обикновено aj се избира от дизайнера и остава постоянен по време на процеса на оптимизация).

Целевата функция във формата (2.1), изразяваща адитивния критерий, може да бъде записана и в случай, когато всички или основните условия на изпълнение имат формата на равенства. След това целевата функция

определя средноквадратичното приближение на yj(X) към дадените технически изисквания TTj.

Мултипликативният критерий може да се използва в случаите, когато няма условия за изпълнение от тип равенство и изходните параметри не могат да приемат нулеви стойности. Тогава мултипликативната целева функция, която трябва да бъде минимизирана, има формата

Един от най съществени недостатъцикакто адитивните, така и мултипликативните критерии е неотчитането на техническите изисквания за изходните параметри при формулирането на проблема.

Критерият за формата на функцията се използва, когато задачата е зададена за най-доброто съвпадение на дадена (референтна) характеристика yCT(X, y) със съответната изходна характеристика y(X, y) на проектирания обект, където y е някаква променлива, например честота, време, избрана фазова променлива. Тези задачи включват: проектиране на системата автоматично регулиране, осигуряващи необходимия тип преходен процес за контролирания параметър; определяне на параметрите на модела на транзистора, които дават максимално съответствие с неговата теоретична характеристики ток-напрежениес експериментални; търсене на параметри на сеченията на гредата, чиито стойности водят до най-доброто съвпадение на дадената диаграма на напрежението с изчислената и др.

Използването на конкретен критерий за оптимизация в тези случаи се свежда до замяна на непрекъснати характеристики с краен набор от възлови точки и избор на една от следните целеви функции, които да бъдат минимизирани:

където p е броят на възловите точки uj на оста на променливата u; aj - тегловни коефициенти, стойностите на които са по-големи, толкова по-малко трябва да се получи отклонението y(X, φj) - yTT(X, φj) в j-та точка.

Критериите Maximin (minimax) позволяват да се постигне една от целите на оптималния дизайн - най-доброто удовлетворяване на условията за изпълнение.

Нека въведем количествена оценка на степента на изпълнение на j-то условие за ефективност, означим я с zj и я наречем резерв за ефективност на параметъра yj. Изчисляването на маржа за j-тия изходен параметър може да се извърши по различни начини, например,

където aj е тегловният коефициент; yjnom - номинална стойност на j-тия изходен параметър; dj е стойност, характеризираща разпространението на j-тия изходен параметър.

Тук се приема, че всички отношения са сведени до формата yi< TТj. Если yi >TTj, след това -yj< -TТj . Следует принимать аj >1 (препоръчителни стойности 5 ? aj ? 20), ако е желателно да се постигне j-тото Технически изискванияс даден толеранс, т.е. yj = TTj ± ?yj; aj=l, ако е необходимо да се получи максимално възможната оценка zj.

Качество на изпълнение техническа системахарактеризиращ се с вектор на изходните параметри и, следователно, вектор Z=(zm,zm,…,zm). Следователно, целевата функция трябва да се формира като някаква функция μ(Z) на вектора за оценка. Например, ако целевата функция разглежда резерва само на този изходен параметър, който в дадена точка X е най-лошият от гледна точка на изпълнение на изискванията на техническите спецификации, тогава

където m е броят на резервите за работоспособност.

Сега е естествено да се постави проблемът за избор на стратегия за търсене X, която да максимизира минимума от резервите, т.е.

където HD е областта за търсене.

Критерият за оптимизация с целева функция (2.6) се нарича максимален критерий.

Статистически критерии. Оптимизацията с помощта на статистически критерии е насочена към получаване на максимална вероятност P за изпълнение. Тази вероятност се приема като целева функция. Тогава имаме проблема

Нормализация на контролирани и изходни параметри. Пространството на контролираните параметри е метрично. Следователно, когато се избират посоките и стойностите на стъпките на търсене, е необходимо да се въведе една или друга норма, идентифицирана с разстоянието между две точки. Последното предполага, че всички контролирани параметри имат една и съща размерност или са безразмерни.

Възможен различни начининормиране. Като пример, разгледайте метода на логаритмична нормализация, чието предимство е преходът от абсолютни увеличения на параметрите към относителни. В такъв случай аз-и контролиранпараметърът ui се преобразува в безразмерен xi, както следва:

където oi е коефициентът, числено равно на еднопараметър ui.

Нормализирането на изходните параметри може да се извърши с помощта на тегловни коефициенти, както в адитивния критерий, или чрез преминаване от уj към резерви за ефективност zj съгласно (2.5).

Линейно програмиране.

Накратко теоретична информация

Поставяне на цели

Решаването на задача с директно линейно програмиране отговаря на следния въпрос:

с какви интензитети нпроцеси за печелене (предоставяне на различни услуги, производствени процеси), в които мвидове ресурси (фактори на производство) с известен максимален интензитет на използване на тези ресурси, приходите от продажби (печалба) ще бъдат максимални в случай, че интензивността на потреблението на всеки ресурс и интензивността на печалбата (приходите) във всеки от процесите зависят линейно от интензивността на този процес.

Решението на неговия двоен проблем отговаря на следния въпрос:

при какви най-ниски цени на единица ресурс ще бъде неизгодно за икономическия агент да разшири допълнително процеса на получаване на печалба чрез придобиване на нови обеми ресурси, които са оскъдни в настоящите условия на икономическа дейност?

Проблем с директно линейно програмиране може да бъде свързан със следната ситуация. На разположение н начини за печалба (осигуряване н видове услуги) с обеми x i (брой парчета аз предоставените услуги). В този случай те се използват м видове ресурси, запаси й -то от които е равно на b j . В същото време потреблението на всеки ресурс й и размера на печалбата във всеки от процесите аз линейно зависи от броя на предоставените услуги аз -ти тип с коеф а джи И c i , съответно. Матрица А=(а джи )м´н значението е подобно на това от първата част и се нарича още матрица на технологичните или структурните коефициенти. Тогава оптималният план според критерия за максимална печалба може да бъде получен от решаването на следната задача на директно линейно програмиране:

Този проблем може да бъде свързан с разширена матрица със следната форма:

(4.1)

Проблемът, двоен на проблем (4), има следния вид ( z j – изисквани лимитни цени):

При тази формулировка на двойствения проблем (5.1) и (5.3) следват от условието за минимизиране на цените, а от условието за нерентабилност от продължаване на дейността директно възниква условието за превишение или равенство на разходите над приходите от продажби.

Основни понятия на модела

Решение (план, програма) -множество, вектор от специфични стойности на всички променливи параметриуправление на модела - тези величини, които могат да се променят по желание на ръководителя на моделиращия обект. Решенията могат да бъдат приемливи (приложени на практика), неприемливи (неприложими поради ограниченията, съществуващи в модела) и оптимални (най-добрите от приемливите).

Целева функция L(x) – математически израз, свързващ факторите (параметрите) на модела. Икономическият смисъл на целевата функция отразява критерий за оптималност– показател, който има икономическо съдържание и служи за формализиране на конкретна управленска цел, например: максимизиране на печалбата (ред 1 в (4)), максимизиране на качеството на продукта или минимизиране на разходите (5.1).

Ограничителна системамодели - граници, които ограничават диапазон на приемливи(приемливо, осъществимо) решения, записвайки основните вътрешни и външни свойства на обекта, свързани с целта на оптимизацията. Комуникационни уравнения(Тип fj(x) ) – математическа формализация на системата от ограничения (редове 2 и 3 в (4), (5.2, 5.3)). Системата от ограничения отразява икономическия смисъл на комуникационните уравнения.

Система, състояща се от целева функция и комуникационни уравнения - проблем на икономическо-математическото моделиране (ЕММ).В случай, когато целевата функция и уравненията за свързване са линейни и контролните променливи се променят непрекъснато, проблемът EMM се нарича проблем с линейно програмиране (LP).. Основното свойство на множеството от допустими планове (SAP) на задачата LP е, че то е изпъкнал многостен. Едно множество се нарича изпъкнало, ако съдържа всички сегменти, свързващи произволни две точки от това множество. Ако проблемът с LP има решение, то той се намира във върха на MDP. Плановете, разположени във върховете на MDP, се наричат ​​основни. Задачите на линейното програмиране се делят на задачи с ограничения под формата на неравенства (обща задача на ЛП) и под формата на равенства (канонична задача на ЛП). При математическо формализиране на икономически проблеми с помощта на линеен модел се получават общи задачи на ЛП - например (4), (5). Всеки общ проблем може да бъде свързан с каноничен проблем чрез въвеждане на допълнителни променливи. По този начин към задача (4) чрез въвеждане във всяко неравенство от типа „консумация на ресурси £ резерв на ресурси“ (ред 2 в (4)) допълнителна променлива x n+j (неизразходван остатък й th ресурс) се сравнява следният каноничен:

В същото време измерението на проблема (6) - броят на проектните променливи - в сравнение с (4) се увеличава с н преди n+m .

При решаването на задача (4) са важни коефициентите на ресурсна ефективност, сред които тук ще се използват диференциални и инкрементални. Диференциален коефициент на ресурсна ефективност k ji показва цената на рендиране при използване на единица й ти ресурс аз -s услуги. Тези видове услуги, за които всичко k ji се оказват най-малки за всички видове услуги и са най-малко рентабилни. Те не трябва да присъстват в оптималния план. Това позволява, като принуди обема на предоставяне на такива услуги до нула, да намали размера на проблема и по този начин да опрости неговото решение. Те се изчисляват, както следва - k ji =c i /a ji .

коефициент на нарастваща ресурсна ефективност K й е коефициентът на пропорционалност между нарастването на стойността на целевата функция на оптималния план и промяната в запасите, която е причинила това увеличение й -ти ресурс. Може да се счита, че ДА СЕ й показват колко ще се увеличи стойността на целевата функция на първоначалния проблем в оптималния план с увеличаване на маржа й -ти ресурс на единица. От математическа гледна точка това е пълната производна на оптималната стойност на целевата функция по отношение на стойността на маржа й -ти ресурс: ДА СЕ j =dL опт/db j .

), за да реши някакъв проблем с оптимизацията. Терминът се използва в математическото програмиране, изследването на операциите, линейното програмиране, статистическата теория на решенията и други области на математиката предимно от приложен характер, въпреки че целта на оптимизацията може да бъде и решаването на самия математически проблем. В допълнение към целевата функция в задачата за оптимизация могат да бъдат зададени ограничения за променливи под формата на система от равенства или неравенства. Като цяло, аргументите на целевата функция могат да бъдат зададени на произволни множества.

Примери

Гладки функции и системи уравнения

$\backslash left\backslash (\; \backslash begin(matrix)\; F\_1(x\_1,\; x\_2,\; \backslash ldots,\; x\_M)\; =\; 0\; \backslash \backslash \; F\_2(x\_1,\; x\_2,\; \backslash ldots,\; x\_M)\; =\; 0\; \backslash \backslash \; \backslash ldots\; \backslash \backslash \; F\_N(x\_1,\; x\_2,\; \backslash \; ldots,\; x\_M)\; =\; 0\; \backslash end(matrix)\; \backslash right.$

може да се формулира като проблем за минимизиране на целевата функция

$S\; =\; \backslash sum\_(j=1)^N\; F\_j^2(x\_1,\; x\_2,\; \backslash ldots,\; x\_M)\; \backslash qquad\; (1)$

Ако функциите са гладки, тогава проблемът с минимизирането може да бъде решен с помощта на градиентни методи.

За всяка гладка целева функция може да се приравни на $0$частни производни по отношение на всички променливи. Оптимумът на целевата функция ще бъде едно от решенията на такава система от уравнения. В случай на функция $(1)$това ще бъде система от уравнения на най-малките квадрати (LSM). Всяко решение на първоначалната система е решение на системата на най-малките квадрати. Ако първоначалната система е непоследователна, тогава системата на най-малките квадрати, която винаги има решение, ни позволява да получим приблизително решение на оригиналната система. Броят на уравненията в системата на най-малките квадрати съвпада с броя на неизвестните, което понякога улеснява решаването на съвместни начални системи.

Линейно програмиране

Друг известен пример за целева функция е линейна функция, която възниква при проблеми с линейно програмиране. За разлика от квадратичната целева функция, оптимизирането на линейна функция е възможно само ако има ограничения под формата на система от линейни равенства или неравенства.

Комбинаторна оптимизация

Типичен пример за комбинаторна целева функция е целевата функция на задачата на пътуващия търговец. Тази функция е равна на дължината на Хамилтоновия цикъл на графиката. Дефинира се върху набор от пермутации $n-1$върхове на графа и се определя от матрицата на дължините на ръбовете на графа. Точното решение на такива проблеми често се свежда до изброяване на опции.

Напишете отзив за статията "Целна функция"

Бележки

Вижте също

Литература

• Бурак Я. И., Огирко И. В. Оптимално нагряване на цилиндрична обвивка с температурно-зависими характеристики на материала // Мат. методи и физико-механични полета. - 1977. - Бр. 5. - С.26-30

Откъс, характеризиращ целевата функция

Бедният ми съпруг търпи труд и глад в еврейските кръчми; но новината, която имам, ме кара да се вълнувам още повече.
Сигурно сте чували за героичния подвиг на Раевски, който прегърнал двамата си сина и казал: „Ще умра с тях, но няма да се поколебаем!” И наистина, въпреки че врагът беше два пъти по-силен от нас, ние не се поколебахме. Прекарваме времето си възможно най-добре; но на война, като на война. Принцеса Алина и Софи седят с мен по цял ден и ние, нещастни вдовици на живи съпрузи, водим чудесни разговори на пух и прах; само ти, приятелю, липсваш... и т.н.
Най-вече принцеса Мария не разбираше пълното значение на тази война, защото старият принц никога не говореше за нея, не я признаваше и се смееше на Десал на вечеря, когато говореше за тази война. Тонът на принца беше толкова спокоен и уверен, че принцеса Мария, без да разсъждава, му повярва.
През целия месец юли старият княз беше изключително активен и дори оживен. Той също така постави нова градина и нова сграда, сграда за дворните работници. Едно нещо, което притесняваше принцеса Мария, беше, че той спеше малко и, след като промени навика си да спи в кабинета, сменяше мястото на нощувките си всеки ден. Или нареждаше да му сложат походното легло на галерията, после оставаше на дивана или на волтеровия стол в хола и дремеше, без да се съблича, но не m lle Bourienne, а момчето Петруша му четеше; след това прекара нощта в трапезарията.
На 1 август е получено второ писмо от княз Андрей. В първото писмо, получено малко след заминаването му, княз Андрей смирено моли баща си за прошка за това, което си е позволил да му каже, и го моли да му върне услугата. Старият принц отговори на това писмо с нежно писмо и след това писмо отчужди французойката от себе си. Второто писмо на княз Андрей, написано от близо до Витебск, след като французите го окупираха, се състоеше от кратко описание на цялата кампания с план, изложен в писмото, и съображения за по-нататъшния ход на кампанията. В това писмо княз Андрей представя на баща си неудобството от положението си близо до театъра на войната, на самата линия на движение на войските, и го съветва да отиде в Москва.
На вечеря същия ден, в отговор на думите на Десал, който каза, че, както се чу, французите вече са влезли във Витебск, старият княз си спомни писмото на принц Андрей.
„Днес го получих от княз Андрей“, каза той на княгиня Мария, „не го ли прочетохте?“
„Не, mon pere, [татко]“, уплашено отговори принцесата. Тя не можеше да прочете писмо, за което дори не беше чувала.
„Той пише за тази война“, каза принцът с онази позната, презрителна усмивка, с която винаги говореше за истинската война.
„Трябва да е много интересно“, каза Десал. - Принцът може да знае...
- О, много интересно! - каза Mlle Bourienne.
„Иди и ми го донеси“, обърна се старият принц към Mlle Bourienne. – Знаеш ли, на малка маса под преспапие.
M lle Bourienne подскочи радостно.
— О, не — извика той, намръщен. - Хайде, Михаил Иванович.
Михаил Иванович стана и влезе в кабинета. Но щом си тръгна, старият принц, като се огледа неспокойно, хвърли салфетката си и си тръгна сам.
„Те не знаят как да направят нищо, ще объркат всичко.“
Докато той вървеше, принцеса Мария, Десал, мили Буриен и дори Николушка мълчаливо се споглеждаха. Старият княз се върна с бърза крачка, придружен от Михаил Иванович, с писмо и план, които той, като не позволи на никого да чете по време на вечерята, постави до него.