3. Порядок выполнения работы

Задание 1. Найти оптимальное решение задачи распределения ресурсов, используя алгоритм симплекс-метода.

Задание 2. Найти оптимальное решение той же задачи распределения ресурсов, используя надстройку Поиск решения.

3.1. Выполнение задания 1

Рассмотрим реализацию алгоритма симплекс-метода на примере.

Пример 1.1.1

Для производства двух видов продукции фирма использует два вида ресурсов: ресурс 1 – сырье, ресурс 2 – время изготовления продукции на оборудовании. Запасы ресурсов ограничены: в день может быть использовано не более 1 000 кг сырья и суммарное время работы оборудования не превосходит 25 часов. Нормы затрат каждого ресурса на единицу каждого продукта и рыночные цены заданы в табл. 1.1.1

Таблица 1.1.1

Ресурс	Нормы затрат на ед. продукции		Запас ресурса
	продукт 1	продукт 2
сырье	a11 =5	a12 =10	b1=1000
время изготовления	a21 =0,1	a22 =0,3	b2=25
цена за ед. продукции	c1=40	c2 =100

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

Обозначим:

x₁– план выпуска продукции 1,

x₂– план выпуска продукции 2,

s₁ – остаток от производства ресурса 1,

s₂ – остаток от производства ресурса 2.

Запишем каноническую форму задачи:

найти план x₁, x₂, s₁, s₂, который дает максимальную выручку

(1.1.10)

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

, (1.1.11)

, (1.1.12)

.

Решение

3.3.1. Построение начального базисного плана

Пусть в начальном базисном плане

x₁,x₂– свободные переменные (т.е.x₁=x₂=0), а

s₁=1000 иs₂=25 базисные переменные.

В симплекс-методе удобно использовать симплекс-таблицы.

Рассмотрим построение первой симплекс-таблицы для выбранного начального базисного решения. В ячейки С7:С8 введем числовые значения 1 000 и 25 базисных переменныхs₁иs₂. Остальные столбцы состоят из коэффициентов перед переменнымиx_jв левых частях ограничений (1.1.11), (1.1.12). Последняя строка симплекс-таблицы состоит из значений целевой функцииZ = 0 и коэффициентов целевой функцииZ.

Переход от одного базисного плана к другому сопровождается преобразованием симплексных таблиц. Такой переход называется итерацией.

3.3.2. Итерация 1. Каждая итерация состоит из нескольких действий.

1) Проверка критерия оптимальности. Если в последней строке симплекс-таблицы нет отрицательных значений, то получено оптимальное решение. В нашем примере значения, расположенные в последней строке симплекс-таблицы в столбцах переменных x₁ и x₂ отрицательны. Поэтому эта таблица не определяет оптимального плана.

2) Определение новой базисной переменной. Отрицательные значения в последней строке показывают, что производства обоих продуктов являются прибыльными и единица первого продукта увеличивает выручку на 40, а единица второго продукта – на 100. Поэтому следует вводить в базис одну из переменных x₁ или x₂. Выберем x₂ в качестве новой базисной переменной, т.е. вводим в базис производство второго продукта. Соответствующий переменной x₂ столбец назовем ведущим столбцом (в таблице этот столбец выделен).

3) Определение новой свободной переменной. Для определения новой свободной переменной составим отношения столбца значений базисных переменных (второго столбца) к положительным элементам ведущего столбца и найдем среди них минимальное значение.

• В ячейку G7 введем формулу =B7/D7 и ячейку G8 введем формулу =B8/D8.

Так как минимальное значение достигается в ячейку G8, то базисная переменная s₂ переходит в свободные. Вторую строку назовем ведущей (в таблице эта строка выделена). Число на пересечении ведущей строки и ведущего столбца назовем ведущим элементом.

4) Пересчет симплекс-таблицы. Теперь для нового базиса s₁, x₂ составим новую симплекс-таблицу. Ее можно получить из старой симплекс-таблицы следующим образом.

Все элементы ведущей (второй) строки, разделенные на ведущий элемент 0,3, образуют вторую строку новой таблицы. Например, элементу второй строки 25 первой симплекс- таблицы будет соответствовать элемент второй строки новой симплекс- таблицы.

• Для пересчета этого элемента в ячейку B14 введем формулу =B8/$D8$

и скопировать эту ячейку в C14:F14.

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

новый элемент	= старый элемент -	(элемент ведущего столбца)·(элемент ведущей строки)
		ведущий элемент

Приведем пример пересчета элемента 1 000 в первой строке. Заметим, что пересчитываемому элементу 1000 соответствуют элемент 10 ведущего столбца и элемент 25 в ведущей строке. Тогда элементу 1 000 соответствует элемент в новой таблице:

.

• Для пересчета этого элемента в ячейку B13 введем формулу

=B7-B8*$D$7/$D8$ и скопировать эту ячейку в C13:F13.

Аналогично пересчитывается последняя строка. Например, первому элементу 0 последней строки соответствует элемент 25 в ведущей строке и элемент -100 в ведущем столбце. Тогда первый элемент последней строки новой таблицы будет равен:

.

• Для пересчета этого элемента в ячейку B15 введем формулу

=B9-B8*$D$9/$D8$ и скопировать эту ячейку в C15:F15.

В результате пересчета получили новую симплекс-таблицу и переходим ко второй итерации.

Итерация 2

1. Критерий оптимальности. Значение, расположенное в последней строке симплекс-таблицы в столбце переменной x_1, отрицательно. Поэтому эта таблица не определяет оптимального плана.

2) Определение новой базисной переменной. Отрицательное значение в последней строке показывает, что производство первого продукта является прибыльным и его единица увеличивает выручку на. Поэтому переменнуюx₁ нужно вводить в базис. Соответствующий столбец будет ведущим.

3) Определение новой свободной переменной. Для определения новой свободной переменной составим отношения столбца значений базисных переменных (второго столбца) к положительным элементам ведущего столбца и найдем среди них минимальное:

.

• В ячейку G13 введем формулу =B13/С13 и ячейку G8 введем формулу =B14/С14.

Так как минимальное значение достигается на первом отношении, то базисная переменная первой строки s₁переходит в свободные. Таким образом,

x₁иx₂– базисные переменные, а

s₁,s₂– свободные переменные.

В симплекс- таблице выделены ведущий столбец (соответствующий переменной x₁) и первая строка - ведущая строка. Теперь для нового базиса x₁, x₂ вычислим новую симплекс-таблицу.

4) Пересчет симплекс-таблицы. Все элементы ведущей (первой) строки, разделенные на ведущий элемент, образуют первую строку новой таблицы. Остальные элементы новой таблицы вычисляются, как и на первой итерации. Результаты пересчета приведены вB18:F21.

Итерация 3

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

Анализ оптимальной симплекс-таблицы

• Значения во втором столбце определяют базисные переменные x₁ = 100,x₂ = 50. Все переменные, не входящие в первый столбец, являются свободными и поэтому равны 0:s₁=0,s₂=0. Значение целевой функции прямой задачиZ = 9 000 (в ячейкеB21).

Таким образом, оптимальный план прямой задачи

X*={x₁=100,x₂=50,s₁=0,s₂= 0}:

первый продукт производится в количестве 100 единиц (x₁=100);

второй продукт производится в количестве 50 единиц (x₂=50);

оба ресурса используются в производстве полностью (s₁=s₂=0).

• В последней строке симплекс-таблицы значения 0 в столбцах x₁ и x₂ означают, что производства первого и второго продуктов рентабельны: Δ₁=0, Δ₂=0;

значение 4 в столбце s₁означает, что теневая цена 1 кг сырья равна 4:y₁=4;

значение 200 в столбце s₂означает, что теневая цена работы 1 часа оборудования равна 200:y₂=200.

Таким образом, оптимальное решение двойственной задачи:

Y* = { y₁=4,y₂=200, Δ_{1 =0}, Δ₂=0 }.