Материал: Методические указания для организации выполнения курсовой работы по курсу Высшая математика. Пантелеев И.Н

Последняя строка снова содержит отрицательное число. В базис вводим вектор P5 , ис-

ключаем P4 .

В 4-й строке последней симплексной таблицы нет отрицательных чисел. Значит найденный опорный план X * = (3, 2, 0, 0, 5, 0) является оптимальным. Значение целевой функции zmax = 12 .

Составим двойственную задачу.

Умножим третье ограничение на-1, тогда все неравенства будут содержать знак«≤». Задача примет вид исходной задачи симметричной пары 1:

x1 , x2 ³ 0.

Число переменных в двойственной задаче равно числу ограничений в исходной задаче, т.е. трём: y1 , y2 , y3 .

Умножим правые части ограничений на соответствующие переменные двойственной задачи и сложим их, получим целевую функцию: g = y1 + 8y2 - 3y3 .

Целевая функция исходной задачи исследуется на максимум, следовательно, целевая функция двойственной задачи исследуется на минимум.

11

Окончательно двойственная задача имеет следующий вид:

Найдём её решение, используя теоремы двойственности. По первой теореме двойст-

Из соотношений второй теоремы двойственности следует, что если какое-то ограничение исходной задачи выполняется в виде строгого неравенства, то соответствующая двойственная оценка равна нулю. Подставим найденное оптимальное решение в систему ограничений исходной задачи:

-1* 3 + 2 * 2 = 1 = 1, 2 * 3 +1* 2 = 8 = 8, 2 * 3 +1* 2 = 7 > 3.

Третье ограничение выполняется в виде строгого неравенства, следовательно, y3* = 0 .

Если некоторая компонента xi* оптимального плана исходной задачи отлична от нуля, то соответствующее ограничение двойственной задачи выполняется в виде равенства. В нашем примере и x1* = 3 ¹ 0 , и x2* = 2 ¹ 0 , следовательно, оба ограничения двойственной задачи выполняются в виде равенства.

Решив систему, получим y1 = 4 / 5, y2 = 7 / 5.

Окончательно Y * = (4 / 5, 7 / 5, 0), g min = 12.

Решение двойственной задачи можно получить другим способом, используя формулу

Y * = CБ P-1 .

Матрица P-1 находится в последней симплексной таблице. Ее столбцы расположены под столбцами единичной матрицы, образующими базис начального опорного решения, т. е. под векторами P3 , P4 , P6 (именно для этой цели мы продолжали вычислять вектор P6 ):

12

5. Транспортная задача

Пусть имеется m поставщиков А1, А2, ..., Аm однородного груза в количествах соответственно а1, а2, .., .аm единиц и n потребителей В1, В2, ..., Вn этого груза, потребность которых составляет соответственно b1, b2 ..., bn единиц.

Известны стоимости перевозок (тариф) единицы груза от i-го поставщика к j-му потре-

бителю - сij (i=1,m; j=1,n).

Требуется составить такой план перевозок, который обеспечит минимальные транспортные расходы.

Возможны три ситуации:

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

2) количество груза у всех поставщиков больше потребности в данном грузе всех -по требителей:

В первом случае модель задачи называется закрытой, во втором и третьем – открытой. Теорема. Для разрешимости транспортной задачи необходимо и достаточно, чтобы за-

пасы груза в пунктах отправления были равны потребностям в грузе в пунктах назначения, т.

m n

е. чтобы выполнялось равенство åai = åb j .

i=1 j =1

В случае превышения запаса над потребностью вводится фиктивный (n + 1)-й пункт на-

m n

значения с потребностью bn+1 = åai - åb j и соответствующие тарифы считаются равными

i =1 j =1

транспортной задаче, из оптимального плана которой получается оптимальный план исходной задачи.

Решение транспортной задачи включает следующие этапы:

1. Нахождение первоначального опорного плана(метод северо-западного угла, метод минимальной стоимости). При этом число заполненных клеток должно быть равно m+n-1.

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

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

13

тель имеют нулевые запасы или запросы, то в клетку ставится перевозка, равная нулю (базисный нуль), и после этого исключается из рассмотрения поставщик или потребитель.

Метод минимальной стоимости позволяет построить решение, близкое к оптимальному, так как использует матрицу стоимостей транспортной задачи. На каждом шаге заполняется только одна клетка, соответствующая минимальной стоимости, и исключается из рассмотрения только один поставщик или один потребитель. Очередную клетку, соответствующую минимальной стоимости, заполняют по тем же правилам, что и в методе северозападного угла. Поставщик исключается из рассмотрения, если его запасы исчерпаны полностью. Потребитель исключается из рассмотрения, если его запросы удовлетворены полностью. При этом если поставщик еще не исключен, но его запасы равны нулю, то на том шаге, когда от поставщика требуется поставить груз, в соответствующую клетку таблицы заносится базисный нуль и лишь затем поставщик исключается из рассмотрения.

2. Проверка опорного плана на оптимальность, например, методом потенциалов.

Пример. Четыре предприятия используют три вида сырья. Потребности в сырье каждого из предприятий соответственно равны100, 90, 170 и 30 ед. Сырьё сосредоточено в трёх пунктах, а запасы соответственно равны 200, 160, и 140 ед. Тарифы перевозок заданы матрицей

Составить такой план перевозок, при котором общая стоимость перевозок является минимальной?

Данная задача является открытой, так как потребности в сырье100+90+170+30=390 меньше запасов 200+160+140=500. Введём 5-го фиктивного потребителя с потребностью b5 = 500 - 390 = 110 .

Теперь исходные данные задачи запишем в виде таблицы, а опорный план получим методом северо-западного угла.

Заполнение таблицы начинаем с клетки(1,1). х11 = min(a1=200,b1=100)=b1=100 – запасы А1 позволяют полностью удовлетворить потребности пункта В1, значит исключаем этого потребителя из рассмотрения. Теперь запасы пункта A1 считаем равными a1=200-100=100 ед. В оставшейся части таблицы левой верхней клеткой является (1,2): х12 = min(a1,b2)=b2=90

– снова запасы удовлетворяют потребность полностью. Внесём значение в соответствующую клетку и исключим из рассмотрения столбец В2. Запасы пункта А1 считаем равными a1=10090=10 ед. Теперь «северо-западным углом» является клетка (1,3). х13 = min(a1,b3)=a1=10 – запасы могут удовлетворить потребность пунктаB3 частично. Заполняем клетку (1,3) и исключаем из рассмотрения строкуA1. Потребности пункта B3 считаем равными b3=17010=160. х23 = min(a2,b3)=a2=b3=160 – запасы A2 исчерпаны, потребность B3 удовлетворена. Но по правилам мы не можем вычеркнуть и строку и столбец одновременно. Поэтому исключим из рассмотрения сначала столбец B3, а в клетку (2,4) запишем х24 =0 (так как запасы А2 уже исчерпаны) и только теперь вычеркнем строку А2. И так далее. Получим следующую таблицу.

Число заполненных клеток равно7 и m+n-1=3+5-1=7 – план невырожденный. Оптимальный план найдём методом потенциалов.

14