ЗАДАНИЕ 2. Для выполнения этого задания необходимо изучить алгоритм симплекс-метода для решения задач линейного программирования.

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

Типовой пример:

Для производства двух видов продукции А и В затрачивается три вида сырья. На производство единицы продукции А затрачивается 3 ед. сырья первого вида, 4 ед. сырья второго вида, 3 ед. сырья третьего вида. На производство единицы продукции В затрачивается 1 ед. сырья первого вида, 3 ед. сырья второго вида, 4 ед. сырья третьего вида. Прибыль от реализации единицы продукции А составляет 6 ден. ед., от единицы продукции В – 3 ден. ед.

Производство обеспечено сырьем в количестве 30 ед. – первого вида, 52 ед. – второго, 60 ед. – третьего.

Определить максимальную прибыль от реализации продукции. Решить задачу симплексным методом и средствами табличного процессора Excel.

Решение:

Пусть х₁ – количество выпускаемой продукции А, х₂ – количество выпускаемой продукции В. Тогда 3х₁+х₂ – затраты сырья первого вида на производство всей продукции, а поскольку запасы сырья не могут превышать имеющихся запасов, имеет место неравенство: 3х₁+х₂ 30. Аналогично для сырья второго вида – 4х₁+3х₂ 52 и для сырья третьего вида – 3х₁+4х₂ 60.

Полученные неравенства образуют систему ограничений задачи, целевая функция которой будет иметь вид: f = 6х₁+3х₂ (прибыль от реализации всей продукции).

Таким образом, необходимо найти максимум функции f = 6х₁+3х₂ при ограничениях:

Приведем задачу к каноническому виду, введя новые неотрицательные переменные х₃, х₄, х₅, значения которых равны соответственно остаткам сырья первого, второго и третьего видов.

Система ограничений примет вид:

Отсюда

Первое базисное решение Б1: (0; 0; 30; 52; 60), значение целевой функции при этом решении f1=6·0+3·0=0.

Cоставим первую симплекс-таблицу:

Таблица 1

а) в f -строке выбираем наименьшее число – (–6), соответствующий столбец считаем «ключевым»;

б) находим наименьшее из отношений элементов столбца свободных членов к элементам «ключевого» столбца:

min следовательно, первая строка является «ключевой»;

в) на пересечении «ключевых» строки и столбца определяем «ключевой» элемент – 3.

Перейдем к следующей симплекс-таблице:

Таблица 2

Свободные Базисные	I	-х3	-х2
х1	10
х4	12		5 3
х5	30	-1	3
f	60	2	-1
			*

1) f₂ =

2) –c₂ =

3) x₄ = x₅ =

4) a₂₂ = a₃₂ =

Второе базисное решение Б₂: (10; 0; 0; 12; 30), значение целевой функции при этом решении f₂=6·10+3·0=60.

Полученное решение не является оптимальным, т. к. f- строка второй симплекс-таблицы имеет отрицательный элемент, поэтому переходим к следующей симплекс-таблице, считая соответствующий столбец ключевым. Так как min , то «ключевой» будет вторая строка. Таким образом, «ключевой» элемент второй симплекс-таблицы равен .

Заполним третью симплекс-таблицу:

Таблица 3

Свободные Базисные	I	-х3	-х4
х1	7, 6
х2	7, 2
х5	8, 4
f	67, 2

1) f₂ =

2) –c₂ =

3) x₁ = x₅= .

Третье базисное решение Б₃: (7, 6; 7, 2; 0; 0; 8, 4), значение целевой функции при этом решении f₃=6·7, 6+3·7, 2=67, 2.

Полученное решение оптимально, т. к. в f -строке все элементы положительны.

Таким образом, максимальная прибыль от реализации всей продукции составляет 67, 2 ден. ед. при выпуске 7, 6 ед. продукции вида А и 7, 2 ед. продукции вида В.

Далее приведем решение этой задачи другим способом – средствами табличного процессора Excel.

Вернемся к математической модели – найти максимум функции f = 6х₁+3х₂ при ограничениях:

Для решения этой задачи необходимо воспользоваться надстройкой Поиск решения, которая находится на вкладке Данные в разделе Анализ.

Если эта надстройка отсутствует её необходимо установить следующим образом: в верхнем левом углу Excel нажимаем на кнопку Office и в нижней части появившегося окна (рис. 3) выбираем кнопку Параметры Excel.

Рис. 3. Диалоговое окно Office

После её активации, в появившемся окне выбираем пункт Надстройки/Поиск решения и нажимаем кнопку Перейти (рис. 4).

Рис. 4. Окно ExcelПараметры

В появившемся окне (рис. 5) выбираем необходимую нам надстройку Поиск решения и нажимаем ОК.

Рис. 5. Окно ExcelНастройки

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

Рис. 6. Вкладка Данные

В Excel вводим в соответствующие ячейки (рис. 7, 8) формулы математической модели задачи, записанной ранее.

Рис. 7. Ввод формул математической модели задачи

Рис. 8. Результат ввода формул математической модели задачи

Ячейку, содержащую значение целевой функции советуем сделать активной (хотя это необязательно). В нашем случае это ячейка D1.

На вкладке Данные в разделе Анализ выбираем Поиск решений (рис. 9):

Рис. 9. Выбор встроенной функции Поиск решений

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

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

Помещаем курсор в окошко Изменяя ячейки (рис. 10) и на Рабочем листе выделяем необходимые ячейки. В нашем примере – диапазон A2: B2.

Рис. 10. Выделение необходимого диапазона ячеек

В разделе Ограничения нажимаем на кнопку Добавить и в диалоговом окне (рис. 11) вводим соответствующие значения (рис. 12).

Рис. 11. Окно ввода ограничений

Рис. 12. Ввод первого ограничения

Далее нажимаем Добавить и вводим следующую пару (рис. 13):

Рис. 13. Ввод второго ограничения

Снова нажимаем Добавить и вводим следующую пару (рис 14):

Рис. 14. Ввод третьего ограничения

Так как значения х1 и х2, согласно условию, не могут быть меньше нуля, то снова нажимаем Добавить и вводим соответствующее ограничение (рис. 15):

Рис. 15. Ввод ограничения для х1

Снова нажимаем Добавить и вводим аналогично еще одно ограничение (рис. 16):

Рис. 16. Ввод ограничения для х2

Далее нажимаем ОК. Диалоговое окно должно выглядеть следующим образом (рис. 17):

Рис. 17. Результат ввода всех ограничений

Нажимаем кнопку Параметры и выставляем галочку в пункте Линейная модель (рис. 18):

Рис. 18. Выбор линейной модели задачи

Нажимаем ОК, далее нажимаем ещё раз ОК и получаем результат, представленный на рисунке 19.

Рис. 19. Результат решения исходной задачи

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