선형 계획법을 사용하여 (역사적으로 최적인) 판타지 Feam 평가

저는 프로그래머이자 Formula 1 팬입니다. F1의 판타지 리그를 시작하면서 자연스럽게 알고리즘에 마음이 쏠렸습니다.

F1 판타지 게임의 목표는 5명의 드라이버와 2개의 팀을 선택하는 동시에 레이스 성적에 따라 최대 포인트를 획득하는 가격 상한선을 유지하는 것입니다. 이것은 제약 조건이 있는 상당히 전통적인 컴퓨터 과학 최적화 문제처럼 들리나요?

보다 정확하게는 모든 역사적 경주 기간에 대해 선형 프로그래밍을 사용하여 최적의 팀을 찾을 수 있습니다. 엄밀히 말하면 이 솔루션은 게임의 단순화된 버전에 대한 것이지만(실제 게임에서는 매주 팀을 변경할 수 있고 일부 와일드카드 요소가 있음) 그럼에도 불구하고 유용한 출발점이 됩니다.

우리의 기능을 통합하려면 최소한의 의존성이 필요했습니다.

• 데이터: 우수한 F1 Fantasy Tools 사이트에서 포인트/가격 데이터를 가져옵니다
• 선형 프로그래밍 라이브러리: 우리는 신뢰할 수 있는 오래된 GLPK 솔버의 JavaScript/WebAssembly 포트인 glpk.js를 사용합니다
• 플랫폼: 우리는 GitHub 페이지를 사용합니다. 여기서 우리의 코드는 MIT 라이선스에 따라 오픈 소스로 제공되며 여기에서 찾을 수 있습니다.

현재 기능은 이 스크린샷과 같이 간단한 인터페이스를 가지고 있습니다.

이 기능의 핵심은 브라우저에서 실행되는 glpk.js 솔버에 공급되는 선형 프로그램의 배후 구성입니다. 다음은 우리 도구로 구성된 실제 선형 프로그램입니다(많은 행이 생략됨).

{
    "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]
    ]
}

F1 명명 구어체에 익숙하지 않은 분들을 위해 설명하자면, 드라이버는 성의 처음 세 글자로 지칭되며(예: VER는 Max Verstappen) 각 팀에는 3글자 니모닉이 있습니다(예: AST는 Aston Martin Motorsports).

따라서 이러한 선형 프로그램에는 드라이버당 변수(3글자 코드로 이름 지정)와 팀당 변수가 있으며, 이 변수는 1(판타지 팀의 경우) 또는 0(판타지가 아닌 팀)의 값을 취해야 합니다. 팀). 그리고 선형 프로그램의 목적은 예산 임계값을 초과하지 않는 가격의 합과 동인 변수의 합이 5이고 팀 변수가 2라는 제약 조건을 적용하여 포인트를 최대화하는 것입니다. 매우 간단합니다. !

그 주에 획득한 포인트의 두 배를 획득한 '2x 드라이버'를 선택할 수 있다는 점이 다릅니다. 이러한 미묘한 차이를 수용하기 위해 우리는 20개의 개별 선형 프로그램(각 프로그램은 2x로 다른 드라이버를 사용함)을 생성하고 해당 20개 프로그램 각각에 대해 glpk.js를 실행하여 최대 점수가 있는 프로그램을 찾습니다.

면책조항: 당사는 Formula One(또는 해당 기업이나 브랜드)과 아무런 관련이 없습니다. 이 기능의 작성자는 단순히 판타지 게임을 즐기는 팬입니다. 이 정보는 정확성에 대해 어떠한 보장도 없이 제공되며, 사용에 따른 책임은 사용자 본인에게 있습니다.'

위 내용은 선형 계획법을 사용하여 (역사적으로 최적인) 판타지 Feam 평가의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!