На каноничната форма ZLP - линейно програмиране проблем на форма брадва = В, където а - коефициент матрица, б - векторни ограничения.
Инструкции. Изберете броя на променливите и на броя на редовете (броят на ограничения). Полученият разтвор се съхранява във файла Word.
ZLP математически модел, наречен първичната. ако ограниченията в него се представят като уравнения предвидени nonnegativeness променливи.
Математическият модел се нарича канонично. ако ограниченията на системата представени като система за линейно независими уравнения m (система ранг г = т), системата е маркиран база единица. Идентифицирани свободни променливи и обективна функция се изразяват по отношение на свободните променливи. В този случай дясната неотрицателно (двупосочно ≥ 0).
Променливите, включени в едно от уравненията на системата с коефициент от един и отсъства в останалите уравнения се наричат основни неизвестни. и всички останали - безплатно.
Решението на системата се нарича основен. ако той е свободен променливи, равни на 0, и има следния вид:
Xbaz = (0, 0 ;. В1 ..., ВМ), F (Xbaz) = c0
Основният разтвор е точка на ъгъл на набор от разтвори, т.е. определя връх на решения полигон модел. Сред тези решения е, в които целевата функция приема оптимална стойност.
Основен разтвор се нарича позоваването, ако това е допустимо, т.е. всички дясна страни на уравнения (или неравенства) са положителни би ≥ 0.
Компактният формата на каноничната модел е както следва:
AX = б
X ≥ 0
Z = CX (макс)
Понятието възможно разтвор, областта на възможни решения, оптималното решение на линейното програмиране проблем.
Определение 1. вектор X, което отговаря ZLP на системни ограничения, включително условия неотрицателност, ако има такива, се нарича осъществимо решение ZLP.
Определение 2. Комплектът от всички възможни решения образува област на възможни решения (SDT) ZLP.
Определение 3. валидно решение, за които целевата функция достига максимум (или минимум) се нарича оптимално решение.
Пример №1. След проблем PL редуцира до каноничен вид: F (X) = 5x1 + 3x2 → макс под ограничения:
2x1 + 3x2 ≤20
3x1 + х2 ≤15
4x1 ≤16
3x2 ≤12
Моделът е писано в стандартен формат. Въведете компания неотрицателни променливи x3. x4. х5. x6. които се добавят към лявата страна на неравенството ограничаващите. Целевата функция на всички допълнителни променливи са въведени с коефициентите равни на нула:
Смисълът на първото неравенство (≤) влезе в основната променлива х3. Във втория смисъла на неравенство (≤) въвеждане на основния променлива x4. В третата неравенството въведе основна променлива х5. През 4 неравенство - основна променлива X6. Ние получи каноничната форма на модела:
2x1 + 3x2 + 1x3 + 0x4 + 0x5 + 0x6 = 20
3x1 + 1x2 + 0x3 + 1x4 + 0x5 + 0x6 = 15
4x1 + 0x2 + 0x3 + 0x4 + 1x5 + 0x6 = 16
0x1 + 3x2 + 0x3 + 0x4 + 0x5 + 1x6 = 12
F (X) = 5x1 + 3x2 + 0x3 + 0x4 + 0x5 + 0x6 → макс