lrsfouier - Dalam Talian di Awan

JADUAL:

NAMA

lrslib - Tukar antara penetapan semula polyhedra cembung.

SINOPSIS

lrs input.ine

lrs input.ine | lrsbuffer

lrsfouier fail.ine [fail keluar]

redund input.ine

DESCRIPTION

Polihedron boleh dihuraikan dengan senarai ketaksamaan (H-wakil) atau melalui senarai
daripada bucu dan sinar melampaunya (perwakilan V). lrs ialah atur cara C yang menukarkan a
Perwakilan H bagi polyhedron kepada perwakilan Vnya, dan begitu juga sebaliknya. Masalah-masalah ini
dikenali masing-masing di puncak penghitungan and cembung badan kapal masalah.

milik Fukuda Soalan Lazim halaman[1] mengandungi pengenalan yang lebih terperinci kepada masalah itu, bersama-sama dengan
banyak petua berguna untuk pengguna baru.

lrsbuffer boleh mengeluarkan beberapa output pendua. redund mendapati ketidaksamaan yang berlebihan dalam
input.

FAIL FORMATS

Format fail dibangunkan bersama dengan Komei Fukuda dan serasi dengan CDD[2].

Input untuk lrs ialah perwakilan H- atau V- politope.

nama
{baris perwakilan}
{pilihan}
{lineariti[3]}
memulakan
mn rasional
{matriks input}
akhir
{pilihan}

nama ialah nama yang dibekalkan pengguna untuk polytope. Komen mungkin muncul sebelum permulaan atau
selepas akhir, dan untuk mengelakkan tafsiran sebagai pilihan, harus bermula dengan yang istimewa
aksara seperti "*" atau "#".

nama ialah nama yang dibekalkan pengguna untuk polytope. perwakilan selaras sama ada
"H-representation" atau "V-representation". Jika diabaikan, perwakilan-H diandaikan. The
pekali input dibaca dalam format percuma, dan tidak disemak untuk jenisnya. Pekali ialah
dipisahkan oleh ruang putih. m ialah bilangan baris dan n bilangan lajur input
matriks.

H-perwakilan
Integer m ialah bilangan ketaksamaan, dan integer n ialah dimensi bagi
input +1. Senarai ketaksamaan mengandungi pekali ketaksamaan bentuk

a0 + a1x1+ ... + an-1 xn-1 >= 0.

Ketaksamaan ini adalah input sebagai garis

a0 a1... an-1

Pekali boleh dimasukkan sebagai integer atau rasional dalam format x/y.

Perwakilan V
Integer m ialah bilangan bucu dan sinar, dan integer n ialah dimensi
input +1. Setiap bucu diberikan dalam bentuk

1 v0 v 1... vn-1

Setiap sinar diberikan dalam bentuk

0 r0 r 1... rn-1

di mana r0 r 1... rn-1 ialah titik pada sinar.

Mesti terdapat sekurang-kurangnya satu bucu dalam setiap fail. Untuk polyhedra bersempadan tidak akan ada
sinar masuk. Pekali boleh dimasukkan sebagai integer atau rasional dalam format x/y.

Nota Untuk CDD pengguna: lrs menggunakan pada asasnya format fail yang sama seperti CDD. Fail disediakan untuk
CDD harus berfungsi dengan sedikit atau tiada pengubahsuaian. Perhatikan bahawa perwakilan V
sepadan dengan pilihan "hull" dalam CDD. Pilihan khusus untuk CDD boleh ditinggalkan dalam input
fail dan akan diabaikan oleh lrs. Perhatikan fail input untuk lrs dibaca dalam format percuma,
selepas talian m n rasional, lrs akan mencari betul-betul m*n rasional atau integer dipisahkan
dengan ruang putih (kosong, pemulangan pengangkutan, tab dll.). lrs tidak akan "menggugurkan" lajur tambahan
input jika n kurang daripada bilangan lajur yang dibekalkan.

Asas Pilihan
Hampir semua pilihan diletakkan selepas pernyataan akhir, mengekalkan keserasian dengan CDD.
Jika ini tidak berlaku, ia akan disebut secara eksplisit.

semua asas Pilihan ini mengarahkan lrs untuk menyenaraikan setiap bucu (atau facet) bagi setiap tapaknya.
Output Penduaan[4].[5] Pilihan ini sering digabungkan dengan printcobasis.

terikat x Gunakan dengan perwakilan H - untuk lrs atau nash Sama ada memaksimumkan atau meminimumkan
pilihan hendaklah dipilih. x ialah integer atau rasional. Untuk memaksimumkan (resp.
minimization) pokok carian terbalik dipotong apabila nilai objektif semasa
adalah kurang (resp. lebih) daripada x.

cache nlrs menyimpan n kamus terkini dalam pepohon carian terbalik. Ini mempercepatkan
langkah menjejak ke belakang, tetapi memerlukan lebih banyak ingatan.

debug asas permulaan asas penamatCetak surih samar tetapi terperinci, kamus dll.
bermula pada #B=startingbasis dan berakhir pada #B=endingbasis. debug 0 0 memberikan yang lengkap
mengesan.

digit n diletakkan sebelum yang memulakan kenyataan n ialah bilangan maksimum digit perpuluhan
digunakan. Jika ini melebihi program ditamatkan dengan mesej (biasanya boleh
dimulakan semula). Lalai ditetapkan kepada kira-kira 100 digit. Pada akhir larian mesej ialah
diberikan memberitahu pengguna saiz integer maksimum yang dihadapi. Ini mungkin digunakan untuk
mengoptimumkan penggunaan memori dan kelajuan pada larian berikutnya (jika melakukan anggaran misalnya).

dualperturb Jika lrs dilaksanakan dengan pilihan memaksimumkan atau meminimumkan, carian terbalik
pokok berakar pada puncak optimum untuk fungsi ini.Jika terdapat ganda optimum
bucu, output selalunya tidak akan lengkap. Pilihan ini memberikan sedikit gangguan kepada
objektif untuk mengelakkan perkara ini. Mesej amaran diberikan jika kamus permulaan adalah dwi
merosot.

anggaran k Anggarkan saiz keluaran. Digunakan bersama dengan maxdepth - lihat
Anggaran.[6]

geometri // H-representation atau pilihan voronoi sahaja // Dengan pilihan ini, setiap sinar adalah
dicetak bersama-sama dengan bucu yang ia adalah kejadian. Untuk maklumat lanjut lihat
Sinar Geometri masuk Petua and Komen-komen[5].

kesanPilihan ini dihidupkan secara automatik printcobasis , jadi lihat di bawah untuk a
penerangan tentang pilihan ini terlebih dahulu. Boleh digunakan dengan printcobasis n. (Ver 4.2b) .PP Untuk
perwakilan H input, indeks semua ketaksamaan input yang mengandungi bucu/sinar yang
akan dikeluarkan. Untuk wajah ringkas, tiada keluaran baharu, kerana indeks ini
sudah disenaraikan. Jika tidak, ketidaksamaan ketat tambahan disenaraikan selepas titik bertindih.
.PP Untuk perwakilan V input, indeks semua bucu/sinar input yang terletak pada facet
yang akan dikeluarkan. Indeks berbintang menunjukkan bahawa bucu ini juga berada dalam
cobasis, tetapi tidak terkandung dalam faset. Ia timbul kerana operasi mengangkat yang digunakan
dengan perwakilan V input.

#insidenSama seperti printcobasis. Disertakan untuk keserasian dengan cdd.

kelinearan k i1i2 i ... ikInput mengandungi k lineariti dalam baris i1i2i ... ikdaripada
fail input adalah persamaan. Lihat Kelinearan.[3]

maxdepth k Pencarian akan dipotong pada kedalaman k. Semua tapak dengan kedalaman kurang daripada atau
sama dengan k akan dikira. k ialah integer bukan negatif, dan pilihan ini digunakan untuk
anggaran - lihat Anggaran.[6]Nota: Untuk perwakilan-H, sinar pada kedalaman k tidak akan
dilaporkan. Untuk perwakilan V, faset pada kedalaman k tidak akan dilaporkan.

memaksimumkan a0 a1... an-1 // H-representasi sahaja //

meminimumkan a0 a1... an-1 // H-representasi sahaja //

Jika digunakan dengan lrs, puncak permulaan memaksimumkan (atau meminimumkan) fungsi a0 + a1x1+ ...
+ an-1 xn-1.Pilihan dwiperturb mungkin diperlukan untuk mengelakkan dwi degenerasi.Lihat Nash
Keseimbangan dan Linear Pengaturcaraan[7]

maxoutput n Hadkan bilangan talian keluaran yang dihasilkan (sama ada bucu+sinar atau faset) kepada n

pemikiran k Penjejakan ke belakang akan ditamatkan pada kedalaman k, untuk integer bukan negatif ka. ini
boleh digunakan untuk menjalankan carian terbalik pada subpokok sebagai proses berasingan, contohnya dalam a
persekitaran pengkomputeran teragih.

bukan negatif // Pilihan ini mesti datang sebelum pernyataan mula // //perwakilan H sahaja
// Pepijat: Hanya boleh digunakan jika asalnya ialah bucu polihedron Untuk masalah di mana
input ialah perwakilan H dalam bentuk b+Ax>=0, x>=0 (iaitu semua pembolehubah
bukan negatif, semua kekangan ketidaksamaan) tidak perlu memberikan bukan negatif
kekangan secara eksplisit jika pilihan bukan negatif digunakan. Pilihan ini tidak boleh digunakan untuk
Perwakilan V, atau dengan pilihan kelinearan (dalam hal ini kelinearan akan menjadi
dianggap sebagai ketidaksamaan). Pilihan ini boleh digunakan dengan redund , tetapi yang tersirat
kekangan nonnegativiti tidak diuji sendiri untuk lebihan. Untuk menguji segala-galanya
adalah perlu untuk memasukkan kekangan bukan negatif secara eksplisit dalam fail input. (Dalam Ver
4.1, asalan mestilah bucu).

printcobasis k;Diubah suai dalam lrs 4.0 Setiap cobasis k'th dicetak. Jika k ditinggalkan, maka
cobasis dicetak untuk setiap bucu/sinar/faset yang dikeluarkan. Untuk jangka masa panjang ia berguna
untuk mencetak cobasis sekali-sekala supaya program boleh dimulakan semula jika perlu.
Perwakilan H: Jika input ialah perwakilan-H, cobasis ialah senarai indeks bagi
ketaksamaan daripada fail input yang mentakrifkan puncak atau sinar semasa. Lihat pilihan
kesan di atas untuk maklumat lanjut. Untuk sinar, cobasis juga dicetak. Dalam kes ini
cobasis ialah cobasis puncak dari mana sinar terpancar. Salah satu indeks
dibintangi, ini menunjukkan ketidaksamaan yang akan digugurkan daripada cobasis untuk mentakrifkan
sinar. Sebagai alternatif, jika semua asaspilihan digunakan, semua cobases akan dicetak.
Perwakilan V: Jika input ialah perwakilan V, cobasis ialah senarai input
bucu / sinar yang mentakrifkan aspek semasa. Lihat pilihan kesan di atas untuk lebih lanjut
maklumat. Untuk memulakan lrs daripada aspek ini semua 4 indeks mesti diberikan dalam susunan ini
(tinggalkan *).

printslack Baru dalam Ver 4.2 ; // Gunakan dengan H-representation // lrs mencetak senarai
indeks ketaksamaan input yang dipenuhi sepenuhnya untuk puncak semasa, iaitu.
pembolehubah kendur sepadan adalah positif. Jika bukan negatif ditetapkan, senarai itu akan turut
masukkan indeks n+i bagi setiap pembolehubah keputusan xi iaitu positif. projek Digunakan oleh
lrsfouier[8] sahaja.

restart V# R# B# kedalaman {facet #s or puncak/sinar #s} Diubah suai dalam lrs4.0 lrs boleh
dimulakan semula dari mana-mana cobasis yang diketahui. Pengiraan akan diteruskan ke penamatan biasa. Semua
daripada maklumat yang terkandung dalam output daripada a printcobasis pilihan. The bagi of
yang indeks is sangat penting, masukkannya tepat seperti yang muncul dalam output daripada
larian yang digugurkan sebelum ini.

permulaan kobasis i1i2i ... dalam-1 Ini membolehkan pengguna menentukan cobasis yang diketahui untuk
memulakan carian terbalik. i1i2i ... dalam-1 ialah senarai ketidaksamaan (untuk
Perwakilan H) atau bucu/sinar (untuk perwakilan V) yang mentakrifkan cobasis. Jika ia adalah
tidak sah, atau pilihan ini tidak dinyatakan, lrs akan mencari cobasis permulaannya sendiri. The
pepohon carian terbalik dipenggal(dipangkas) setiap kali bucu baharu ditemui. Nota: Ini
adakah nota semestinya menghasilkan set semua bucu yang bersebelahan dengan bucu optimum dalam
polihedron, tetapi hanya subset daripadanya.

kata kerjaCetak maklumat yang lebih terperinci sedikit tentang larian.

jumlah // Perwakilan V sahaja // Hitung volum - lihat bahagian jumlah Pengiraan.[9]

voronoi // Perwakilan V sahaja - letakkan sejurus selepas penyataan tamat // Kira
Gambar rajah Voronoi - lihat bahagian Voronoi Gambar rajah.[10]

NOTA

1. halaman FAQ
http://www.ifor.math.ethz.ch/staff/fukuda/polyfaq/polyfaq.html

2. cdd
http://www.cs.mcgill.ca/%7Efukuda/soft/cdd_home/cdd.html

3. lineariti
http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Linearities

4. Penduaan Output
http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Output%20Duplikasi

5.
http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Hints%20and%20Comments

6. Anggaran.
http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Estimation

7. Pengaturcaraan Linear
http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Linear%20Programming

8. lrsfouier
http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#fourier

9. Pengiraan Isipadu.
http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Volume%20Computation

10. Gambarajah Voronoi.
http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Voronoi%20Diagrams

Gunakan lrsfouier dalam talian menggunakan perkhidmatan onworks.net