Elektron jadval yordamida chiziqli optimallash masalasini amalga oshirish.(Simpleks metodi ). Reja

Simpleks usulini batafsil tahlil qilish
Yaqinda oddiy usul algoritmini amalga oshiruvchi dasturni noldan yaratish zarurati paydo bo'ldi. Ammo hal qilish jarayonida men muammoga duch keldim: Internetda algoritmning batafsil nazariy tahlilini ko'rishingiz mumkin bo'lgan juda ko'p manbalar (uning mantiqiy asoslari: nima uchun biz ma'lum qadamlar qo'ymoqdamiz) va amaliy amalga oshirish bo'yicha maslahatlarni to'g'ridan-to'g'ri ko'rishingiz mumkin. , algoritm. Keyin men o'zimga va'da berdim - topshiriqni bajarishim bilanoq, men ushbu mavzu bo'yicha o'z postimni yozaman. Biz bu haqda gaplashamiz, aslida. Xabar juda rasmiy tilda yoziladi, ammo aniqlik kiritishi kerak bo'lgan sharhlar bilan ta'minlanadi. Ushbu format ilmiy yondashuvni saqlab qoladi va shu bilan birga, bu masalani o'rganishda ba'zilarga yordam beradi.
Chiziqli dasturlash masalasining bayoni
Ta'rif: Chiziqli dasturlash - chiziqli tenglamalar va tengsizliklar tizimlari tomonidan berilgan n o'lchovli fazo to'plamlari bo'yicha ekstremal masalalarni yechish nazariyasi va usullariga bag'ishlangan matematik fan.
U
mumiy chiziqli dasturlash muammosi (bundan buyon matnda LP) quyidagi shaklga ega:
LP muammosining kanonik shakli:

Izoh: Har qanday LP muammosi kanonik muammoga tushiriladi. Ixtiyoriy LP muammosidan kanonik shaklga o'tish algoritmidir.
LP muammosini echishning grafik usuli shuni ko'rsatadiki, optimal echimni topish burchak nuqtasi bilan bog'liq. Bu simpleks usulini ishlab chiqishda asosiy tushunchadir. Ta'rif: m tenglama va n ta noma'lum (m < n) sistemasi bo'lsin. O'zgaruvchilarni ikkita to'plamga ajratamiz: (n-m) o'zgaruvchilar nolga teng, qolgan m o'zgaruvchilar esa boshlang'ich tenglamalar tizimini yechish orqali aniqlanadi. Agar bu yechim yagona bo'lsa, u holda nolga teng bo'lmagan m o'zgaruvchilar asosiy deyiladi; nol (n-m) o'zgaruvchilar erkin (asosiy bo'lmagan) va o'zgaruvchilarning mos keladigan qiymatlari asosiy echim deb ataladi.
Simpleks usuli
Simpleks usuli barcha mumkin bo'lgan burchak nuqtalarini oddiy sanab o'tishdan qochib, optimal echimni samarali topishga imkon beradi. Usulning asosiy printsipi: hisob-kitoblar qandaydir "boshlang'ich" asosiy echimdan boshlanadi, so'ngra maqsad funktsiyasi qiymatini "yaxshilaydigan" echimlar izlanadi. Bu faqat ba'zi o'zgaruvchilarning o'sishi funktsional qiymatning oshishiga olib keladigan bo'lsa mumkin.
Simpleks usulini qo'llash uchun zarur shartlar:
Muammo kanonik shaklga ega bo'lishi kerak.
Muammo aniq ajratilgan asosga ega bo'lishi kerak.
Ta'rif: Aniq ajratilgan asos bu shakl vektori:
Hisob-kitoblarning qulayligi va ravshanligi uchun odatda simpleks jadvallari qo'llaniladi:

Birinchi qatorda barcha o'zgaruvchilarning "nomi" ko'rsatilgan.
Birinchi ustunda asosiy o'zgaruvchilar raqamlari, oxirgi katakda esa Z harfi ko'rsatiladi (bu funktsional satr).
"Jadvalning o'rtasida" cheklash matritsasining koeffitsientlarini ko'rsating - aij.
Oxirgi ustun cheklash tizimining mos keladigan tenglamalarining o'ng qismlari vektoridir.
Eng o'ng katak - maqsad funktsiyasining qiymati. Birinchi iteratsiyada u 0 ga o'rnatiladi. Eslatma: Bazis - o'zgaruvchilar, cheklash matritsasidagi koeffitsientlar, ular ostida bazis vektorlarini hosil qiladi.
Eslatma: Agar dastlabki masaladagi cheklovlar ≤ ko’rinishdagi tengsizliklar bilan ifodalangan bo’lsa, u holda masala kanonik ko’rinishga keltirilsa, kiritilgan qo’shimcha o’zgaruvchilar boshlang’ich asosiy yechimni tashkil qiladi.
Eslatma: Funktsional qatordagi koeffitsientlar “-” belgisi bilan olinadi.
Simpleks usuli algoritmi:
1. Biz asosga kiritadigan o'zgaruvchini tanlaymiz. Bu yuqorida ko'rsatilgan printsipga muvofiq amalga oshiriladi: biz o'zgaruvchini tanlashimiz kerak, uning oshishi funktsional o'sishiga olib keladi. Tanlov quyidagi qoidaga muvofiq amalga oshiriladi:
Agar vazifa minimal bo'lsa, oxirgi qatorda maksimal ijobiy elementni tanlaymiz.
Agar vazifa maksimal bo'lsa, biz minimal salbiyni tanlaymiz.
Bunday tanlov, haqiqatan ham, yuqorida aytib o'tilgan printsipga mos keladi: agar muammo minimal bo'lsa, unda qancha ko'p raqam olib tashlansa, funksionallik tezroq kamayadi; maksimal uchun, buning aksi to'g'ri - raqam qanchalik katta bo'lsa, funktsional tezroq o'sadi.
Eslatma: Maksimal masalada minimal manfiy sonni olsak ham, bu koeffitsient funksionalning o'sish yo'nalishini ko'rsatadi, chunki simpleks jadvalidagi funksional qator “-” belgisi bilan olinadi. Minimallashtirish bilan o'xshash vaziyat.
Ta'rif: Simpleks jadvalining tanlangan koeffitsientga mos keladigan ustuni etakchi ustun deb ataladi.
2. Biz bazaga kiritadigan o'zgaruvchini tanlaymiz. Buning uchun asosiy o'zgaruvchilardan qaysi biri yangi asosiy o'zgaruvchi o'sganda eng tez nolga borishini aniqlashingiz kerak. Algebraik jihatdan bu quyidagicha amalga oshiriladi:
To'g'ri qismlarning vektori bosh ustunga bo'linadi
Olingan qiymatlar orasida minimal ijobiyni tanlang (salbiy va nol javoblar hisobga olinmaydi)
Ta'rif: Bunday satr yetakchi qator deb ataladi va bazisdan olinadigan o'zgaruvchiga mos keladi.
Eslatma: Aslida, biz cheklash tizimining har bir tenglamasidan eski bazis o'zgaruvchilarni qolgan o'zgaruvchilar nuqtai nazaridan ifodalaymiz va yangi bazis o'zgaruvchining o'sishi qaysi tenglamaga tezroq 0 berishini ko'rib chiqamiz. Bunday vaziyatga kirish degani biz yangi cho'qqiga "qoqilib qoldik". Shuning uchun nol va salbiy elementlar hisobga olinmaydi, chunki bunday natijani olish, bunday yangi asosiy o'zgaruvchini tanlash bizni tashqarida hech qanday echimlar mavjud bo'lmagan hududdan uzoqlashtirishini anglatadi.

Fodalanilgan adabiyotlar
1. Акулич H.JI. Математическое программирование в примерах и задачах. — “Высшая школа”, М: 1986.
2. Гуревич Т.Ф., Лушук В.О. Сборник задач по математическому программированию. — “Колос”, М: 1977.
3. Данциг Д. Линейное программирование его применение и обобщение. - “Прогресс”, М:, 1975.
4. Калихман И.Л. Сборник задач по математическому программированию. -Высшая школа, М., 1975.
5. Канторович Л.В., Горстко А.Б. Математическое оптимальное программирование в экономике. - Знание. М., 1968.
6. Кузнецов Ю.Н.,Кузубов В.И., Волошенко А.Б. Математическое программирование. — Высшая школа, М., 1976.