Решение

Обозначим х₁ – количество выпущенных изделий вида А (шт.), х₂ – количество выпущенных изделий вида В (шт.).

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

F(X) = 30х₁ + 40х₂  max

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

12х₁ + 4х₂  300 (ограничение на количество сырья вида I);

4х₁ + 4х₂  120 (ограничение на количество сырья вида II);

3х₁ + 12х₂  252 (ограничение на количество сырья вида III);

х₁  0; х₂  0. (условие неотрицательности переменных).

В итоге получаем следующую экономико-математическую модель:

F(X) = 30х₁ + 40х₂  max

1 2х₁ + 4х₂ £ 300;

4х₁ + 4х₂ £ 120;

3х₁ + 12х₂ £ 252;

х₁  0; х₂  0.

Приведем решение этой задачи в пакете Excel:

Создаем форму для решения задачи

Вводим исходные данные, зависимость для целевой функции и зависимости для ограничений:

Получаем следующую форму:

После выбора команды Сервис/Поиск решения оформляем диалоговое окно.

Назначим целевую функцию и вводим ограничения:

Вводим параметры для решения ЗЛП:

Важно установить флажки в окнах Линейная модель (это обеспечит применение симплекс-метода) и Неотрицательные значения. Далее нажимаем ОК и выполняем поиск решения.

После нажатия клавиши Выполнить в диалоговом окне Поиск решения осуществляется реализация модели и выдается сообщение об успешности решения:

Ниже приведены результаты решения задачи:

Получен оптимальный план (12; 18).

Максимальное значение прибыли 1080 руб.

Задача 2

1. Определите вид задачи ЛП.

2. Приведите задачу к симплексной форме.

3. С помощью симплекс-метода определить, имеет ли решение данная задача, и найти его.

Задача 2.2.

Решение

Задача уже задана в канонической форме:

I. Среди векторов , нет единичных. Поэтому в левую часть всех уравнений системы ограничений задачи добавим дополнительные неотрицательные переменные и запишем М-задачу (M→∞):

В качестве базисных выступают переменные .

Выразим базисные переменные через свободные переменные :

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

X_{1 оп.} (0; 0; 0; 19; 20)

Если подставить в выражение для целевой функции начальное опорное решение, то получим F(X_{1 оп.}) = .

Вычисляем оценки разложений векторов условий по базису опорного решения по формуле:

,

где: - вектор коэффициентов целевой функции при базисных переменных;

- вектор разложения соответствующего вектора по базису опорного решения;

с_к - коэффициент целевой функции при переменной х_к.

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

i	Базис	сi	1	-2	-4	М	М	F(X)
			x1	x2	x3	x4	x5	А0
1	x4	-М	3	5	2	1	0	19
2	x5	-М	5	6	1	0	1	20
∆ j			-1	2	4	0	0	0
(М-функция)			-8	-11	-3	0	0	-39

Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты. Вводим в базис соответствующую переменную x₂, так как это наибольший коэффициент по модулю. Столбец x₂ становится разрешающим. Среди коэффициентов разрешающего столбца есть положительные, следовательно, можно выбрать разрешающую строку.

Для выбора разрешающей строки найдем минимальное отношение свободного члена из столбца А₀ к соответствующему положительному коэффициенту из разрешающего столбца, т.е. min{19/5; 20/6} = min{3,8; 3,33} = 3,33. Таким образом, в качестве разрешающей строки берем вторую строку таблицы и выводим переменную х₅ из базиса. На втором шаге итерации базис будет состоять из переменных x₄, х₂.

Заполняем вторую симплексную таблицу, предварительно поделив вторую строку на ключевой элемент. Производим симплексное преобразование:

– вторую (разрешающую) строку умножаем на -5 и прибавляем к первой строке;

– вторую (разрешающую) строку умножаем на -2 и прибавляем к третьей строке;

– вторую (разрешающую) строку умножаем на 11 и прибавляем к четвертой строке.

Получаем:

i	Базис	сi	1	-2	-4	М	М	F(X)
			x1	x2	x3	x4	x5	А0
1	x4	-М	-1,17	0,00	1,17	1,00	-0,83	2,33
2	x2	-М	0,83	1,00	0,17	0,00	0,17	3,33
∆ j			-2,67	0,00	3,67	0,00	-0,33	-6,67
(М-функция)			1,17	0,00	-1,17	0,00	1,83	-2,33

Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты. Вводим в базис соответствующую переменную x₃. Столбец x₃ становится разрешающим. Среди коэффициентов разрешающего столбца есть положительные, следовательно, можно выбрать разрешающую строку.

Для выбора разрешающей строки найдем минимальное отношение свободного члена из столбца А₀ к соответствующему положительному коэффициенту из разрешающего столбца, т.е. min = min{ 2; 20} = 2. Таким образом, в качестве разрешающей строки берем первую строку таблицы и выводим переменную х₄ из базиса. На третьем шаге итерации базис будет состоять из переменных x₃, х₂.

Заполняем третью симплексную таблицу, предварительно поделив первую строку на ключевой элемент. Производим симплексное преобразование:

– первую (разрешающую) строку умножаем на -0,17 и прибавляем ко второй строке;

– первую (разрешающую) строку умножаем на -3,67 и прибавляем к третьей строке;

– первую (разрешающую) строку умножаем на 1,17 и прибавляем к четвертой строке.

Получаем:

i	Базис	сi	1	-2	-4	М	М	F(X)
			x1	x2	x3	x4	x5	А0
1	x3	-М	-1,00	0,00	1,00	0,86	-0,71	2,00
2	x2	-М	1,00	1,00	0,00	-0,14	0,29	3,00
∆ j			1,00	0,00	0,00	-3,14	2,29	-14,00
(М-функция)			0,00	0,00	0,00	1,00	1,00	0,00

Новый опорный план является оптимальным, так как все ∆_j > 0 (с учетом М – функций).

Оптимальный план выпуска продукции: x₁ = 0, x₂ = 3, x₃ = 2.

Максимальное значение целевой функции составляет

F_max(Х) = 0 – 2·3 – 4·2 = -14.

II. Получим оптимальный план выпуска продукции с помощью надстройки Поиск решения (Ехсеl). Искать решение будем для преобразованной системы (*).

Создаем форму для решения и вводим формулы:

Получаем следующую форму:

Задаем целевую ячейку и ограничения с помощью встроенной программы Поиск решения:

Нажимаем выполнить и получаем решение:

Решение F_max(Х) = -14 – совпало с решением, найденным ранее симплекс-методом.

Ответ: максимальное значение целевой функции составляет F_max(Х)= -14. Оптимальный план выпуска продукции: x₁ = 0, x₂ = 3, x₃ = 2.