Menilai Feam Fantasi (Sejarah Optimum) dengan Pengaturcaraan Linear

Saya seorang pengaturcara dan peminat Formula 1. Apabila saya mula bermain liga fantasi F1, fikiran saya secara semula jadi tertumpu kepada algoritma.

Matlamat dalam permainan fantasi F1 adalah untuk memilih 5 pemandu dan 2 pasukan, sambil kekal di bawah had harga, yang berdasarkan prestasi perlumbaan, memperoleh jumlah mata maksimum. Ini kelihatan seperti masalah pengoptimuman sains komputer yang agak tradisional dengan kekangan, bukan?

Lebih tepat lagi, untuk mana-mana tingkap sejarah perlumbaan, kami boleh menggunakan Pengaturcaraan Linear, untuk mencari pasukan yang optimum. Tegasnya, penyelesaian ini adalah untuk versi permainan yang dipermudahkan (permainan sebenar membolehkan anda membuat perubahan pada pasukan anda dari minggu ke minggu, serta mempunyai beberapa faktor kad bebas), tetapi tetap merupakan titik permulaan yang berguna.

Mengumpulkan keupayaan kami memerlukan kebergantungan minimum:

• data: kami mengambil data mata/harga daripada tapak Alat Fantasi F1 yang sangat baik
• pustaka pengaturcaraan linear: kami menggunakan glpk.js, yang merupakan port JavaScript/WebAssembly penyelesai GLPK lama yang boleh dipercayai
• platform: kami menggunakan halaman GitHub, di mana kod kami adalah sumber terbuka di bawah Lesen MIT dan boleh didapati di sini

Keupayaan semasa mempunyai antara muka yang mudah, seperti yang ditunjukkan dalam tangkapan skrin ini.

Inti kebolehan ialah pembinaan di belakang tabir program linear, yang kemudiannya disalurkan kepada penyelesai glpk.js yang berjalan dalam penyemak imbas anda. Berikut ialah atur cara linear sebenar yang dibina oleh alat kami (dengan banyak baris ditinggalkan).

{
    "name": "LP",
    "objective": {
        "direction": 2,
        "name": "obj",
        "vars": [
            {
                "name": "VER",
                "coef": 593
            },
            {
                "name": "OCO",
                "coef": 112
            },
   [...18 additional drivers, omitted for brevity]

            {
                "name": "AST",
                "coef": 360
            },
   [...9 additional teams, omitted for brevity]

        ]
    },
    "subjectTo": [
        {
            "name": "cons1",
            "vars": [
                {
                    "name": "VER",
                    "coef": 30
                },
                {
                    "name": "NOR",
                    "coef": 23
                },
[...18 additional drivers, omitted for brevity]

                {
                    "name": "MCL",
                    "coef": 23.2
                },
[...9 additional teams, omitted for brevity]

            ],
            "bnds": {
                "type": 3,
                "ub": 100,
                "lb": 0
            }
        },
        {
            "name": "cons2",
            "vars": [
                {
                    "name": "VER",
                    "coef": 1
                },
                {
                    "name": "OCO",
                    "coef": 1
                },
[...18 additional drivers, omitted for brevity]

            ],
            "bnds": {
                "type": 5,
                "ub": 5,
                "lb": 5
            }
        },
        {
            "name": "cons3",
            "vars": [
                {
                    "name": "RED",
                    "coef": 1
                },
[...9 additional teams, omitted for brevity]
Show quoted text
[...18 additional drivers, omitted for brevity]

        {
            "name": "cons29",
            "vars": [
                {
                    "name": "FER",
                    "coef": 1
                }
            ],
            "bnds": {
                "type": 4,
                "ub": 1,
                "lb": 0
            }
        },
[...9 additional teams, omitted for brevity]

    ],
    "generals": [
        "VER",
        "OCO",
[...18 additional drivers, omitted for brevity]
        "ALP",
[...9 additional teams, omitted for brevity]
    ]
}

Bagi mereka yang tidak biasa dengan bahasa sehari-hari penamaan F1, pemandu dirujuk oleh tiga huruf pertama nama keluarga mereka (cth. VER ialah Max Verstappen), dan setiap pasukan mempunyai mnemonik 3 huruf (cth. AST ialah Aston Martin Motorsports).

Jadi dalam program linear ini, terdapat pembolehubah setiap pemandu (dinamakan dengan kod tiga huruf mereka) dan pembolehubah setiap pasukan, yang mesti mengambil nilai 1 (pada pasukan fantasi anda) atau 0 (bukan pada fantasi anda pasukan). Dan objektif program linear adalah untuk memaksimumkan mata, tertakluk kepada jumlah harga yang tidak melebihi ambang belanjawan, dan juga tertakluk kepada kekangan bahawa jumlah pembolehubah pemandu ialah 5, dan pembolehubah pasukan ialah 2. Sangat mudah !

Sesuatu yang menarik ialah anda boleh memilih "pemandu 2x", yang memperoleh dua kali ganda mata yang mereka peroleh minggu itu. Untuk menampung nuansa ini, kami menjana 20 atur cara linear yang berasingan (masing-masing mengambil pemacu yang berbeza sebagai 2x), dan menjalankan glpk.js pada setiap 20 program tersebut, untuk mencari program yang mempunyai mata maksimum.

Penafian: kami tidak mempunyai kaitan dengan Formula Satu (atau mana-mana syarikat atau jenama mereka). Pengarang keupayaan ini hanyalah seorang peminat yang gemar bermain permainan fantasi. Maklumat ini diberikan tanpa jaminan tentang ketepatannya, gunakan atas risiko anda sendiri.'

Atas ialah kandungan terperinci Menilai Feam Fantasi (Sejarah Optimum) dengan Pengaturcaraan Linear. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!