Дәріс 14
Матрицалық ойынды СПЕ-не келтіру
Сызықтық программалау есебінің канондық түрін матрицалыққа және векторлар арқылы жазуға болады.
Теорема 3.2. Сызықтық программмалау есебінің шектееу жүйесінің барлық мүмкін болу шешімдерінің жиыны дөңес б.т. Сонымен Сызықтық программалау есебінің мүмкін болу шешімдерінің жиыны дөңес болады, яғни дөңес көпжақтық немесе дөңес көпжақты облыс ретінде көрсетіледі. Дөңес көпжақты облысты енді шешімдер көпжақтығы д.а.
Шешімдер көпжақтығының қай нүктесінде СПЕ-ң оптималды шешімі орналасуы мүмкін.
Теорема 3.3. Егер СПЕ-ң оптималды шешімі бар болса, онда сызықтық функция өзінің максималды мәнін шешімдер көпжақтығының бұрыштық нүктенің біреуінде қабылдайды. Егер сызықтық функция өзінің максималды мәнін бірнеше бұрыштық нүктеде қабылдайтын болса, онда ол максималды мәнді, ол нүктенің дөңес сызықтық комбинациясы болатын кез келген нүктеде де қабылдайды.
Дәлелдеуі: Шешімдер көпжақтығы шектелген болсын. Оның бұрыштық нүктелерін х1,х2,...хр деп белгілейік. Ал оптималды шешімін Х* бұрыштық нүкте болса, онда теореманың бірінші бөлімі дәлелденді. Егер Х* бұрыштық нүкте болмаса, онда 3.1. теорема бойынша Х*-ны шешімдер көпжақтығының бұрыштық нүктелерінің сызықтық комбинациясы ретінде көрсетуге болады.
 .  сызықтық функция болғандықтан
 3.12.
Достарыңызбен бөлісу: |
