кількості суден для здійснення даного графіка перевезень і т. п.
. Іншим важливим поштовхом до побудови теорії цілочислового програмування став новий підхід до деяких екстремальним комбінаторним задачах. У них потрібно знайти екстремум целочисленной лінійної функції, заданої на кінцевому безлічі елементів. Такі завдання прийнято називати завданнями з альтернативними змінними. В якості прикладів можна назвати завдання комівояжера (бродячого торговця), про оптимальний призначення, теорії розкладу, або календарного планування, і завдання з додатковими логічними умовами (наприклад, типу В«або - абоВ», В«якщо - тоВ» і т. п.) .
Історично першою задачею цілочислового типу є опублікована в 1932 р. угорським математиком Е. Егерварі завдання про призначення персоналу. У 1955 р. на Другому симпозіумі по лінійному програмуванню була розглянута задача про бомбардувальнику, відома як завдання про ранці. p align="justify"> Мета даної роботи: У даній роботі я розгляну Цілочисельне лінійне програмування (ЦЛП) орієнтоване на вирішення завдань лінійного програмування, також розгляну завдання про призначення. На їх прикладі вирішу завдання з цієї області. p align="justify"> 1. Цілочисельне лінійне програмування
Цілочисельне лінійне програмування (ЦЛП) орієнтовано на вирішення завдань лінійного програмування, в яких всі або деякі змінні повинні приймати цілочисельні (або дискретні) значення. Незважаючи на інтенсивні дослідження, що проводяться протягом останніх десятиліть, відомі обчислювальні методи вирішення завдань ЦЛП далекі від досконалості. На сьогодні не існує надійних обчислювальних алгоритмів вирішення таких завдань. br/>
. Постановка транспортної задачі за критерієм вартості в матричної формі
Транспортна задача (ТЗ) формулюється таким чином. У m пунктах відправлення A1, ...., Am зосереджений однорідний вантаж в кількостях відповідно a1, ...., am одиниць. Наявний вантаж необхідно доставити споживачам B1, ...., Bn попит яких виражається величинами b1, ...., bn одиниць. Відома вартість сij перевезення одиниці вантажу з i-го пункту відправлення в j-й який повністю задовольняє попит споживачів у вантажі, і при цьому сумарні транспортні витрати мінімізуються.
Для побудови економіко-математичної моделі ТЗ розглянемо матрицю
В
де позначає кількість одиниць вантажу, яке необхідно доставити з i-го пункту відправлення в j-й пункт призначення.
Матрицю Х = [хij] т Г— п будемо називати матрицею перевезень. Передбачається, що всі xij? 0. Питомі транспортні витрати (витрати) запишемо у формі матриці C = [cij] m Г—
