Материал: УП - Методы оптимальных решений

Аналогично делаем вывод и для игрока В.

Задание для самостоятельной работы

Решить матричную игру m×n с помощью линейного программирования.

1. 2.

3. 4.

5. 6.

7. 8.

9. 10.

11. 12.

13. 14.

15. 16.

17. 18.

19. 20.

21. 22.

23. 24.

25. 26.

27. 28.

29. 30.

6. Транспортная задача линейного программирования

6.1. Постановка транспортной задачи и ее математическая модель

Транспортная задача (ТЗ): некоторый однородный продукт сосредо­точен у m поставщиков А₁, А₂, …, А_n в количестве а₁, а₂, …, а_m единиц. Его необходимо доставить n потребителям В₁, В₂, …, Вn, спрос которых выражается величинами b₁, b₂, …, b_n единиц. Известна стоимость с_ij перевозки единицы груза из i-го (i = ) пункта отправления в j-й (j = ) пункт назначения. Требуется составить план перевозок, который полностью удовлетворяет спрос потребителей в грузе, и при этом суммарные транспортные издержки будут минимальными. Для построения математической модели транспортной задачи рассмотрим матрицу.

Х= где х_ij ≥ 0 (i = ) обозначает количество единиц груза, которое необходимо доставить из i-го пункта отправления в j-й пункт назначения. Матрицу Х называют матрицей перевозок, где х Удельные транспортные издержки _{(расходы) запишем в форме матрицы С= и называется она} матрицей тарифов. Для наглядности условия транспортной задачи можно записать табл. 29, которая называется распределительной.

Таблица 29

Составим математическую модель задачи: цель транспортной задачи – минимизировать общие затраты на перевозки, то есть

^Найти

систему ограничений получаем из следующих условий задачи:

а) все грузы должны быть вывезены, т. е. (эти уравнения получаются из строк таблицы);

_{б) все потребности должны быть удовлетворены, т. е.} (эти уравнения получаются из столбцов).

_{Итак, система ограничений имеет вид:}

План перевозок Х= называется допустимым, если он удовле­творяет системе ограничений транспортной задачи, а допустимый план перевозок, доставляющий минимум целевой функции, называется оптимальным.

Решение транспортной задачи обусловливается следующей теоремой.

Теорема (о существование опорного плана). Для того чтобы транспортная задача имела допустимые (опорные) планы, необходимо и достаточно выполнение равенства .

6.2. Закрытая и открытая модели транспортной задачи

Модель транспортной задачи называется закрытой, если суммарный объем груза, имеющийся у поставщиков равен суммарно-_{му спросу по­требителей, т. е. выполняется равенство .} Если для транспортной задачи выполняется одно из условий:

_{или (15)}

_{, (16)}

то модель задачи называется открытой. Для того чтобы решить транспортную задачу с открытой моделью, надо преобразовать ее в закрытую. Если дано условие (7.1), то необходимо ввести фиктивный (n + 1) пункт назначения В_n+1, т. е в матрице задачи вводится дополнительный столбец. Спрос фиктивного потребителя полага-_{ют равным не балансу, т. е. bn+1 = , а все тарифы равными 0,} т. е. С_i,n+1 = 0 ( ).

Аналогично, если дано в задаче условие (16): вводится фиктив-_{ный поставщик Аm+1, запас груза которого равен Аm+1= - , а} тарифы распределительной таблицы равны 0, то есть С_m+1,j = 0 (j = ).

При преобразовании открытой задачи в закрытую целевая функция не меняется, т. к. все слагаемые, соответствующие дополнительным пе­ревозкам, равны 0.

6.3. Построение исходного опорного плана

Построение опорных планов, а также из преобразование будем производить в распределитель­ной таблице. Если переменная , то это число записываем в клетку (i, k) и считаем ее занятой (базисной), если же , то клетку (i, k) оставляем свободной.

Число занятых опорным планом клеток должно быть равно (m + n - 1).

1. Метод северо-западного угла

Сущность его состоит в следующем: в распределительной таблице будем распределять груз, начиная с загрузки левой верхней (условно называем северо-западной) клетки (1:1), двигаясь затем от нее по строке вправо или по столбцу вниз.