Практическое занятие №3

«Решение задач симплекс – методом»

Цель: научиться решать задачи симплекс - методом.

Задача: решить задачу согласно своему варианту.

Ход роботы:

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

Задача 1: Некая компания производит большие и маленькие скамейки. Каждая скамейка должна быть построена и отполирована. На стройку маленькой скамейки уходит 2 часа, на полировку 3 часа. На постройку большой уходит 4 часа, на полировку 3 часа. Строительных цех работает 100 часов в неделю, а полировочный – 90 часов. Прибыль, получаемая с маленькой скамейки, составляет 5$, а с большой - 7$. Сколько скамеек каждого вида должна производить компания для максимизации прибыли?

Пусть фирма производит х маленьких и y больших скамеек. Тогда для решение задачи необходимо найти x и y, что:

5x+7y=>max

2x+4y<=100

3x+3y<=90

x, y >=0 (А.39)

Введем переменные S₁, S₂>=0, тогда задача примет канонический вид:

5x+7y+0S₁+0S₂=>max

2x+4y+1S₁+0S₂=100

3x+3y+0S₁+1S₂=90

x,y S₁, S₁ >=0 (А.40)

Рассмотрим решение этой задачи, используя симплекс таблицу А.2. Данное решение подходит для всех случаев, когда правая часть уравнений ограничений неотрицательна. Если правая часть уравнений ограничений, после приведения задачи к каноническому виду, содержит отрицательные числа, то используйте вариант решения, разобранный во втором примере.

Таблица А.2 - Решение задачи 1

Рассмотрим пошаговое решение задачи.

1 шаг. В строке C_j выписываем коэффициенты целевой функции при переменных x,y, S₁, S₂. В строках 1,2 – коэффициенты при соответствующих переменных из уравнений ограничений RHS(столбец right hand side), в строках 1, 2 пишем числа 100 и 90 из правой части неравенств ограничений. Переменные, образующие единичную матрицу будем называть базисным, в данном случае S₁ и S₂.

2 шаг.Заполняем столбец CB строки 1, 2 коэффициентами целевой функции при базисных переменных, то есть 0 при S₁ в строке 1(перечисление строки 1и столбца S₁) и 0 при S₂ в строке 2.

3 шаг. Заполняем строку 3 (Z_j) путем перемножения каждого элемента столбца CB на соответствующие элементы строк 1,2 и сложением. То есть первый элемент строки Z_j получается как: 0*2+0*3=0. В данном случае все элементы строки получаются равными 0. Аналогично получается 0 в столбце RHS.

4 шаг. Строка 4 (C_j – Z_j) получается почленным вычитанием элементов строки 3 (Z_j) из элементов строки C_j (всегда из верхней строки на всех шагах).

5 шаг. Ищем в строке 4 (C_j – Z_j) максимальный строгоположительный элемент. Ему соответствует ведущий столбец. В данном случае, в строке 4 выбираем элемент 7, следовательно, ведущим будет столбец y (строки 1,2).

6 шаг. Ищем в ведущем столбце минимально положительное число из формулы (RHS/ведущий столбец). То есть, в данном случае, выбираем между 100/4=25 и 90/3=30. Найдя такое число, определяем ведущую строку, у меня строка 1. Пересечение ведущих столбца и строки дает нам ведущий элемент, в моем случае 4.

7 шаг. Формируем строки 5,6 путем деления ведущих строки на ведущий элемент и формирования единичного столбца на месте ведущего. Не забываем RHS. Далее следуем на шаг 2.

Итерация продолжается до тех пор, пока в строке (C_j – Z_j) не останется положительных элементов (в случае, что оптимальное решение задачи существует).

Тогда в строке Z_j (у нас строка 11) в RHS – столбце получаем значение целевой функции в оптимальной точке (x,y)=(10,20). Значения 10 и 20 получаем из RHS в строках 9, 10.

Задача 2. Рассмотрим более общий случай:

4х₁ + 15х₂ + 12х₃ + 2х₄ -> min

2х₂ + 3х₃ + х₄ >= 1

х₁ + 3х₂ + х₃ - х₄ >= 0

х₁, х₂, х₃, х₄ >=0 (А.41)

Приведем задачу в следующий вид:

-4х₁ - 15х₂ - 12х₃ - 2х₄ -> max

-2х₂ - 3х₃ - х₄ <= -1

-х₁ - 3х₂ - х₃ + х₄ <= 0

х₁, х₂, х₃, х₄ >=0 (А.42)

Введем переменные S₁, S₂ >= 0, тогда задача примет стандартный (канонический) вид:

-4х₁ - 15х₂ - 12х₃ - 2х₄ -> max

0х₁ - 2х₂ - 3х₃ - х₄ + 1S₁ + 0S₂ = -1

-х₁ - 3х₂ - х₃ + х₄ + 0S₁ + 1S₂ = 0

х₁, х₂, х₃, х₄, S₁, S₂ >=0 (А.43)

Теперь необходимо составить симплекс – таблицу А.3.

Таблица А.3 - Решение задачи 2

Рассмотрим пошаговое решение данной задачи.

1 шаг. В строке C_j выписываем коэффициенты целевой функции при переменных х₁, х₂, х₃, х₄, S₁, S₂. В строках 1,2 - коэффициенты при соответствующих переменных из уравнений ограничений. В столбце RHS, в строках 1, 2 пишем числа -1 и 0 из правой части уравнений ограничений. Переменные, образующие единичную матрицу (выделена бежевым) будем называть базисными, в данном случае S₁ и S₂.

2 шаг. Заполняем столбец CB строки 1, 2 коэффициентами целевой функции при базисных переменных, то есть 0 при S₁ в строке 1 (пересечение строки 1 и столбца S₁) и 0 при S₂ в строке 2.

3 шаг. Заполняем строку 3 (Z_j) путем перемножения каждого элемента столбца CB на соответствующие элементы строк 1, 2 и сложением. То есть первый элемент строки Z_j получается как: 0*0 + 0*(-1) = 0. Второй как 0*(-2)+0*(-3). В данном случае все элементы строки получаются равными 0. Аналогично получается 0 в столбце RHS.

4 шаг. Строка 4 (C_j – Z_j) получается почленным вычитанием элементов строки 3 (Z_j) из элементов строки C_j (всегда из верхней строки на всех шагах).

5 шаг. Смотрим на элементы RHS выше строки Z_j (у нас на строки 1 и 2). Если все элементы RHS неотрицательные, то идем на шаг 5". Если есть хоть один отрицательный элемент, идем на шаг 5'.

5' шаг. В каждой строке 1 и 2 вычисляем соотношения RHS/x, где x пробегает значения той же строки, что и RHS, столбцы x₁, x₂, x₃, x₄, S₁, S₂. Мы ищем минимальный строгоположительный элемент среди получившихся чисел (то есть мы можем вычислять RHS/x только для х того же знака, что и RHS). В нашем случае:

Строка 1:

- столбец х₂: (-1)/(-2)=0,5;

- столбец x₃: (-1)/(-3)=0,3333(3);

- столбец x₄: (-1)/(-1)=1;

Строка 2 - все соотношения равны нулю. Минимальный строгоположительный элемент получился в столбце x₃. Этот элемент назовем ведущим, у нас - 3. В таблице он выделен зеленым цветом. Строка и столбец содержащие этот элемент называются ведущими.

Идем на шаг 7.

7 шаг. Формируем строки 5 и 6 путем деления ведущей строки на ведущий элемент и формирования единичного столбца на месте ведущего. Не забываем RHS.

Сделаем совместно еще одну итерацию. На предыдущем шаге мы заполнили строки 5, 6. Далее выполняем последовательно шаг 2, шаг 3 и шаг 4, получаем новую строку (C_j – Z_j), у нас строка 8. Идем на шаг 5 - на второй итерации у нас RHS в строках 5, 6 >0, значит идем на шаг 5".

5" шаг. Ищем в строке 8 (C_j – Z_j) максимальный строгоположительный элемент. Если такой есть, то ему соответствует ведущий столбец (у нас x4). Идем на шаг 6. Если в (C_j – Z_j) нет строгоположительных элементов, то идем в конец.

6 шаг. Ищем в ведущем столбце минимально положительное число из формулы (RHS/ведущий столбец). То есть, в данном случае, выбираем между 0,33/0,33=1 и 0,33/1,33=0,25. Найдя такое число, определяем ведущую строку, у нас строка 6. Пересечение ведущих столбца и строки дает нам ведущий элемент, в нашем случае 1,33 (выделен зеленым). Идем на шаг 7.

Конец: итерации продолжаются до тех пор (в случае, что оптимальное решение задачи существует), пока на шаге 5' или на шагах 5" и 6 мы не сможем отыскать положительного ведущего элемента.

В нашем примере: мы сформировали строки 9, 10, 11. RHS (строки 9, 10) неотрицательна, следовательно, идем на шаг 5". Число 3,50 - максимальный строгоположительный элемент (столбец S₁), но положительного ведущего элемента в этой строке нет.

Тогда в строке Z_j (у нас строка 11) в RHS - столбце получим значение целевой функции в оптимальной точке (x3, x4) = (0,25; 0,25) равное -3,5. Значения 0,25 и 0,25 получаем из RHS в строках 9, 10.

Литература:

1 Таха, Хемди А. Введение в исследование операций, 7-е издание.: Пер. с англ. — М.: Издатель­ский дом "Вильяме". 2005. — 912 с.

2 Моисеев Н.Н. Математические задачи системного анализа. — М.: Наука, 1981. — 488 с.

3 Анфилатов В.С. Системный анализ в управлении: Учебное пособие / Под ред. А.А. Емельянова. — М.: Финансы и статистика, 2002. — 368 с.

Дата добавления: 2017-02-01; Просмотров: 230; Нарушение авторских прав?; Мы поможем в написании вашей работы!