Материал: 1820

вершине С(6,4) многоугольника. Линейная функция, выраженная через нп, имеет вид

поэтому значение F X4 24 является максимальным.

Задачи

1.Решить задачи 1-4 из предыдущего параграфа симплексным методом.

2.Решить задачи симплексным методом:

1)F 10 x1 x2 x3 2x4 x5 max

x1 3x2 2x3 6

3x2 2x3 x4 12x2 x3 x5 10

xi 0

2) F 10 4x1 x2 x3 x4 2x5 max

2x1 3x2 x3 6

3x2 4x3 x4 12x2 x3 x5 10

xi 0

3) F 2x1 3x2 2x3 x4 x5 min

5x1 2x2 x3 10

2x1 x2 x4 12x1 2x2 x5 6

xi 0

3.Двойственные задачи

3.1Практическое занятие №8 (4 часа). Двойственные задачи

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

Методические указания.

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

21

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

2)Коэффициенты при переменных в линейной функции одной задачи являются свободными членами системы ограничений в другой.

3)Каждая из задач задана в стандартной форме, причем в задаче максимизации все неравенства вида « », а в задаче минимизации все неравенства вида « ».

4)Матрицы коэффициентов при переменных в системах ограничений обеих задач являются транспонированными друг другу:

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

6) Условия неотрицательности переменных имеются в обеих задачах.

Алгоритм составления двойственной задачи:

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

ограничений привести к виду « », а если минимум – к виду « ».

2) составить расширенную матрицу исходной системы A1, состоящую из матрицы A, столбца свободных членов системы ограничений, строки коэффициентов при переменных в линейной функции.

3)Найти матрицу A1/ , транспонированную к матрице A1.

4)Сформулировать двойственную задачу на основании полученной матрицы A1/ и условия неотрицательности перменных.

Первая теорема двойственности.

Для взаимодвойственных ЗЛП имеет место один из взаимоисключающих случаев:

1)В исходной и двойственной задачах имеются оптимальные решения, при этом значения целевых функций на оптимальных решениях совпадают: max F X min Z Y .

2)В исходной задаче допустимое множество не пусто, а целевая функция на этом множестве не ограничена сверху. При этом у двойственной задачи будет пустое допустимое множество.

3)В двойственной задаче допустимое множество не пусто, а целевая функция на этом множестве неограниченна снизу. При этом у исходной задачи будет пустое допустимое множество.

4)Обе из рассматриваемых задач имеют пустые допустимые множества.

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

F x1 2x2 max

22

Решение:

1) Так как исходная задача на максимизацию, то приведем все неравенства системы ограничений к виду « », для чего обе части первого и четвертого неравенства умножим на -1. Получим

2x1 x2 1,

x1 4x2 24, x1 x2 3,

x1 x2 5.

2)Составим расширенную матрицу системы:

1 4 24

1 1 5

4) Сформулируем двойственную задачу:

Zy1 24y2 3y3 5y4 min

2y1 y2 y3 y4 1,

y1 4y2 y3 y4 2,

y1 0, y2 0, y3 0, y4 0.

Задачи

1.Для задач из параграфа 2.3 составить двойственные, решить симплексным методом. Убедиться в том, что оптимальные значения линейных функций исходной и двойственной задач совпадают.

2.Даны две взаимодвойственные задачи:

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

3. Даны две взаимодвойственные задачи:

23

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

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

4.1Практическое занятие № 9 (4 часа). Транспортная задача.

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

Методические указания.

Важным частным случаем ЗЛП является транспортная задача. Рассмотрим на примере решение таких задач.

Пример.

В пунктах Ai i 1,n выпускается однородная продукция в количестве ai i 1,n , единиц.

Себестоимость единицы продукции в пункте Ai i 1,n равна Ci i 1,n . Готовая продукция поставляется в пункты Bj j 1,m , потребности которых составляют bj j 1,m единиц.

Стоимость Cij перевозки единицы продукции из пункта Ai в пункт Bj известна.

Требуется:

1)Найти оптимальный план перевозок, который обеспечивает минимальные суммарные затраты на производство и доставку продукции;

2)Составить экономико-математическую модель задачи;

3)Найти величину Zmin минимальных затрат.

Пусть n 3, m 4. Все необходимые данные даны в таблице:

Решение:

Задача является открытой, так как запасы суммарный спрос меньше суммарного предложения: 140+180+240 = 560 > 540 = 80+160+120+180 единиц, т.е. суммарные мощности поставщиков и потребителей не совпадают. Для того, чтобы привести задачу к закрытому типу, необходимо ввести фиктивного потребителя b5 с потребностью в 560-540=20 единиц

продукции. Стоимость перевозки в пункт потребления b5 из всех пунктов производства считаем равным 0.

Пусть xij – количество единиц продукции, перевозимой из пункта Ai в пункт Bj . Задача заключается в минимизации общих транспортных расходов:

3 5

ZCij Ci xij min i 1 j 1

при ограничениях

24

и естественном условии неотрицательности количества поставляемой продукции xij 0 i 1,3, j 1,5

Математическая модель задачи выглядит следующим образом:

Z X 6x11 5x12 9x13 9x14 3x15 8x21 4x22 7x23 11x24 3x25

9x31 12x32 8x33 5x34 2x35 min

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

Рассмотрим "северо-западный угол" незаполненной таблицы, то есть клетку, соответствующую первомупоставщикуи первомупотребителю.Поставим туданаименьшееиз значений 140и 80, т.е80. Тогда спрос первого потребителя будет удовлетворён, вычеркнем из дальнейшего рассмотрения первый столбец, а у первого поставщика осталось 140-80=60 единиц нераспределённой продукции. Далее рассматриваем "северо-западный угол" оставшейся таблицы, то есть клетку, соответствующую первому поставщику и второму потребителю, ставим туда наименьшее из значений 160 и 60, т.е. 60. Вся продукция первого поставщика распределена, значит вычёркиваем первый столбец, у второго потребителя потребность уменьшилась до 160-60=100. Аналогично продолжаем заполнять таблицу. Послеn+m-1шаговполучаемопорныйплан:

2) Составим начальный опорный план методом наименьших стоимостей. В правом верхнем углу каждойячейкизаписываем Cij' Cij Ci

25