Материал: 3597

xj 0 (j=1,..., m)

Каждому ограничению ставится в соответствие переменная двойственной задачи. Двойственная задача имеет вид

Задачи (4) – (5) обладают следующими свойствами:

1.В одной задаче целевая функция стремится к максимуму, в другой – к минимуму.

2.Число неизвестных одной задачи равно числу ограничений другой задачи.

3.В каждой задаче система ограничений задается в виде неравенств, причем все они одного смысла, а именно: при нахождении максимума

целевой функции эти неравенства имеют вид , а при нахождении минимума – вид .

4.Свободные члены ограничений исходной задачи являются коэффициентами целевой функции двойственной задачи, а коэффициенты целевой функции исходной задачи – свободные члены ограничений двойственной задачи.

5. Матрицы коэффициентов при переменных в системах ограничений (4) –

(5) транспонированы относительно друг друга.

Задачи линейного программирования, удовлетворяющие перечисленным условиям, называются симметричными взаимно двойственными задачами.

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

Z = 5x1 + 2x2 max

8x1 + 7x2 417, y1

14x1 + 8x2 580, y2

14x1 + x2 591, y3

14

yi 0 (i=1, 2, 3)

Решим исходную задачу симплексным методом

Между переменными задач (4)-(5) существует взаимно-однозначное

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

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

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

Известны сij – затраты на перевозку 1 единицы груза из пункта Аi и Bj. Транспортная задача называется закрытой, если

Теорема. Число базисных неизвестных транспортной задачи равно m+n-1.

Чтобы решить транспортную задачу, необходимо прежде всего найти исходный план. При этом используются два метода: метод ''северозападного угла'' или метод наименьшего элемента.

По методу ''северо-западного угла'' необходимо удовлетворить потребность пункта В1 за счет А1. Если a1>b1, то в клетку А1В1 записываем b1 и этот пункт из рассмотрения исключаем, при этом запоминаем, что в пункте А1 осталось а1-b1 единиц груза. Если же а1<b1, то записываем а1 в А1В1 и исключаем пункт А1. Если же а1=b1, то это число записываем в А1В1, а в следующую (по строке или столбцу) клетку записываем ноль и исключаем пункты А1 и В1. Продолжаем распределять груз до получения допустимого плана.

Пример.

16

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

Алгоритм метода потенциалов

1. Потенциалы строк - Ui и столбцов - Vj удовлетворяют следующему условию: Ui + Vj = Cij для базисных переменных. Так как система для определения потенциалов содержит на одно уравнение меньше, чем число потенциалов, то, чтобы найти решение системы потенциалов, один потенциал задаем произвольно, например, U1=0.

Остальные потенциалы найдем, решая систему уравнений

2. Определяем характеристики для свободных неизвестных (пустых клеток).

Eij = Cij – (Ui + Vj) и записываем их в левом нижнем углу свободных клеток. План будет оптимален, если для всех свободных неизвестных

Так как E33 отрицательна, то план не является оптимальным.

3. Выбираем клетку (3.3) с отрицательной характеристикой и строим контур (цикл). Контур удовлетворяет следующим условиям: а) для каждой клетки можно построить один, и только один контур; б) все вершины контура находятся в заполненной клетке, за исключением клетки, для которой контур строится; в) число вершин – четно.

Вариант для контрольного задания студент выбирает в соответствии с двумя последними цифрами своего учебного шифра по следующему правилу: вторая цифра номера варианта должна совпадать с последней цифрой шифра; если предпоследняя цифра шифра четная, то первая цифра номера варианта должна быть равна 0 или 2, если же предпоследняя цифра нечетная, то первая цифра варианта должна быть равна 1.

Например, при шифре 824016 студент выполняет – вариант 16; при шифре 824086 – вариант 06; при шифре 825010 – вариант 10; при шифре 825060 – вариант 20.

При выполнении и оформлении контрольной работы необходимо руководствоваться следующим:

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

2.Решения задач излагать подробно.