Приведение модели с положительными и отрицательными коэффициентами в целевой функции к стандартному виду

 

Такое приведение осуществляется с помощью замены переменных вида M_i – x_i = y_i так, чтобы выполнялось y_i ≥ 0, а правые части ограничений были положительно определенными. Замена переменных не меняет решения. Если окажется, что правые части могут быть представлены как больше нуля, а знаки неравенств одного вида, то задача решается стандартным способом, в противном случае решение усложняется.

Рассмотрим пример:

Найти max z =3x₁ – 2x₂ при ограничениях:

2x₁ +x₂ ≤ 11,

-3x₁ + 2x₂ ≤ 10,

3x₁ + 4x₂ ≥ 20, .

Сделаем замену переменной, положив y₂ = (M -x₂), получим

Найти max z =3x₁ + 2y₂ при ограничениях:

2x₁ - y₂ ≤ 11 -M, M ≤ 11,

-3x₁ – 2y₂ ≤ 10-2M, M ≤ 5,

-3x₁ + 4y₂ ≤ - 20 +4M, M ≥ 5.

Неравенства выполняются при M=5 и принимают вид:

2x₁ - y₂ ≤ 6,

-3x₁ – 2y₂ ≤ 0,

-3x₁ + 4y₂ ≤ 0.

Введя замену переменных 3x₁ / z = q₁, 2y₂ / z = q₂, получим

q₁ / 9 - q₂ / 12 ≤ ν, ν = 1 /z,

-q₁ - q₂ ≤ 0,

-q₁ + 2q₂ ≤ 0,

q₁ + q₂ = 1 из условия z.

Второе неравенство выполняется всегда и может быть отброшено, третье неравенство не зависит от ν и из условия наличия экстремума на границе области из последних двух уравнений q₁ = 2q₂ и q₁ + q₂ = 1 находим q₁ = 2/3, q₂ = 1/3. Подстановка в первое уравнение даёт ν = 5/108 и обратная развертка даёт искомое решение: z =108/5, x₁= 24/5, y₂ = 18/5, x₂ = 7/5, что совпадает с точным решением.

При большей размерности задач для решения игровой модели можно использовать метод итераций.

 

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

ЛИТЕРАТУРА

 

1. Вентцель Е.С. Исследование операций. Задачи, принципы, методология. М., Наука, 1980.

2. Вентцель Е. С. «Исследование операций»-М.: Наука, 1980

3. Геронимус Б.А. Экономико-математические методы в планировании на автомобильном транспорте. М.: Транспорт, 1982

4. Данциг Дж. Линейное программирование, его применения и обобщения. М.: Прогресс, 1966.

5. Давыдов Э. Г. Исследование операций: Учебное пособие для студентов вузов. - М.: Высш. шк., 1990.

6. Дегтярев Ю. И. Исследование операций: Учебник для вузов по спец. АСУ.- М.: Высш. шк., 1986.

7. Зайченко Ю.П. Исследование операций. Киев, Вища школа, 1988.

8. Зайченко Ю.П., Шумилова C.A. Исследование операций: Cб. задач 2-е изд., перераб. и доп. - К.: Высш. шк.,1990.

9. Мину М. Математическое программирование. Теория и алгоритмы: Пер. c фр. и предисловие А.И. Штерна. - М.: Наука. Гл. ред. физ. - мат. лит.,1990.

10. Таха Х. Введение в исследование операций: В 2-х книгах. Кн.2. Пер. с англ. - М.: Мир, 1985.

11. Юдин Д.Б., Гольштейн Е.Г. Линейное программирование. М., Физматгиз, 1963.

 

ПРИЛОЖЕНИЕ

 

Таблица П1. Варианты заданий транспортной модели

N

Стоимость перевозки

N

Стоимость перевозки

Ai

Ai

Bj

Bj

Ai

Ai

Bj

Bj

Ai

Ai

Bj

Bj

Ai

Ai

Bj

Bj

Ai

Ai

Bj

Bj

Ai

Ai

Bj

Bj

Ai

Ai

Bj

Bj

Ai

Ai

Bj

Bj

Ai

Ai

Bj

Bj

Ai

Ai

Bj

Bj

Ai

Ai

Bj

Bj

Ai

Ai

Bj

Bj

Ai

Ai

Bj

Bj

Ai

Ai

Bj

Bj

Ai

Ai

Bj

Bj

Ai

Ai

Bj

Bj

Ai

Ai

Bj

Bj

Ai

Ai

Bj

Bj

Ai

Ai

Bj

Bj

Ai

Ai

Bj

Bj

Ai

Ai

Bj

Bj

Ai

Ai

Bj

Bj

 

 

Таблица П2. Варианты заданий задачи о назначениях

N

Стоимость работы

N

Стоимость работы