Затраты труда на производство ячменя и кормовой моркови

Производственные ресурсы	Затраты на один ц	Наличие производственных ресурсов
Морковь кормовая	Ячмень
Пашня, га	0,005	0,05
Затраты труда: на конно-ручных работах, ч.-дн.	0,11	0,10
на механизированных работах, тр.-смен	0,0225	0,025

Чтобы получить 1 ц кормовой моркови, требуется 0,005 га пашни, 1 ц ячменя – 0,05 га.

По данным условиям составим неравенства.

По пашне:

0,005Х₁ + 0,05Х₂ ≤ 2000.

По затратам труда:

0,11Х₁ + 0,10Х₂ ≤ 18000

0,0225Х₁ + 0,025Х₂ ≤ 3200.

Оптимальный вариант сочетания культур может оказаться таким, что некоторые производственные ресурсы будут использованы не полностью. Поэтому ставится знак «меньше или равно» (≤).

Из смысла задачи следует, что Х₁ и Х₂ должны быть неотрицательными, то есть Х₁ ≥ 0, Х₂ ≥ 0.

Требуется найти такие неотрицательные значения Х₁ и Х₂, которые в сумме давали бы максимум кормовых единиц. Если искомый максимум обозначить через С, то можно записать:

0,005Х₁ + 0,05Х₂ ≤ 2000

0,11Х₁ + 0,10Х₂ ≤ 18000

0,0225Х₁ + 0,025Х₂ ≤ 3200

С = 0,25Х₁ + 1,2Х₂

Теперь неравенства преобразуем в уравнения. Для этого в каждое неравенство введем дополнительные неотрицательные переменные величины: Х₃, Х₄ и Х₅, обозначающие размеры недоиспользованных ресурсов:

0,005Х₁ + 0,05Х₂ + Х₃ = 2000

0,11Х₁ + 0,10Х₂ + Х₄ = 18000

0,0225Х₁ + 0,025Х₂ + Х₅ = 3200

С = 0,25Х₁ + 1,2Х₂

В нашем примере Х₃ – размер недоиспользованной пашни, Х₄ – человеко-дней, Х₅ – тракторо-смен.

Таким образом, условия задачи сформулированы в виде системы линейных уравнений, содержащей три уравнения с пятью неизвестными, то есть п >т. Такая система имеет множество решений.

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

0,005Х₁ + 0,05Х₂ + Х₃ = 2000

0,11Х₁ + 0,10Х₂ = 18000

0,0225Х₁ + 0,025Х₂ = 3200

В результате получим одно из возможных решений:

Х = (Х₁; Х₂; Х₃; 0; 0).

Решение, где число нулевых переменных не превосходит числа уравнений, называется базисным. При этом переменные Х₁, Х₂ и Х₃, значения которых определяются, являются базисными, а Х₄ и Х₅, заранее приравненные к нулю, - небазисными.

Для решения задачи линейного программирования симплексным методом необходимо знать одно из допустимых базисных решений соответствующей системы условий. Указанное выше решение хотя и является базисным, но может оказаться и недопустимым, если хотя бы одно из значений переменных будет отрицательным.

Чтобы получить допустимое базисное решение, возьмем в качестве базисных дополнительные переменные Х₃, Х₄ и Х₅. При этом Х₁ и Х₂ равны нулю, как небазисные переменные, а Х₃, Х₄ и Х₅ равны свободным членам соответствующих уравнений системы.

Решение подобных задач симплексным методом (вручную) осуществляется путем составления серии так называемых симплексных таблиц. В верхней строке этих таблиц (c_j) даны коэффициенты при неизвестных целевой функции. Левый крайний столбец (c_i) состоит из коэффициентов целевой функции при неизвестных, вошедших в базис. Затем следует столбец базисных переменных и столбец свободных членов. Элементы всех прочих столбцов представляют собой коэффициенты при неизвестных системы уравнений. Наконец, нижняя строка таблицы (z_j – c_j) называется индексной строкой. В столбцах х_j индексной строки содержится оценки плана (решения), а в столбце свободных членов – численное значение целевой функции. Номера строк и столбцов таблицы определяются номерами стоящих в них переменных. Столбец свободных членов и индексная строка – нулевые.

Составим симплексную таблицу для первого базисного решения поставленной задачи (таблица 2.36.).

Таблица 2.36.

Первый вариант индексного плана

сj ci	Базисные переменные	Свободные члены	0,25	1,2
Х1	Х2	Х3	Х4	Х5
	Х3		0,005	0,05
	Х4		0,11	0,1
	Х5		0,0225	0,025
	zj – cj		-0,25	-1,2

Переменные Х₃, Х₄ и Х₅ по условиям характеризуют размер неиспользованных ресурсов. Следует отметить, что в симплексной таблице 2.36. эти переменные являются базисными, поэтому по строкам равны свободным членам. Последние отражают наличные производственные ресурсы. Поскольку они пока не используются, то и значение целевой функции, стоящее на пересечении индексной строки и столбца свободных членов, равно нулю. Остальные элементы индексной строки равны коэффициентам целевой функции при соответствующих переменных, взятых с обратными знаками (это справедливо всегда, когда с_j = 0, i = 1, 2, …, m).

Вариант плана составлен. Теперь возникает вопрос: является ли он оптимальным? Если нет, то как его улучшить?

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

В нашем примере (таблица 2.36.) два элемента индексной строки имеют отрицательные значения, следовательно, составленный план не оптимален. Необходимо прийти ко второму, улучшенному варианту плана на основе поиска нового базисного решения. Для этого составляется очередная аналогичная симплексная таблица. Необходимо отметить, что на каждом шаге (итерации) в базис можно ввести только одну новую переменную. При этом одну из базисных переменных удаляют.

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

Следовательно, в нашем примере в базис следует ввести Х₂. Теперь надо решить вопрос: какую переменную следует удалить из базиса? Проделаем некоторые расчеты. Определим место для Х₂. Для этого по каждой строке свободный член разделим на соответствующий коэффициент при Х₂. Наименьшее частное покажет искомую строку. Причем свободные члены делят только на положительные коэффициенты. Это следует из требования неотрицательности значений базисных неизвестных, как одного из условий в задачах, решаемых методами математического программирования.

Наименьшее число оказалось в строке Х₃:

2000: 0,05 = 40000

18000: 0,1 = 180000

3200: 0,025 = 12800

Следовательно, переменную Х₃ надо удалить из базиса. и на ее место ввести Х₂. Составим вторую симплексную таблицу, то есть найдем второй план (таблица 2.37.).

Таблица 2.37.

Второй вариант искомого плана

сj ci	Базисные переменные	Свободные члены	0,25	1,2
Х1	Х2	Х3	Х4	Х5
	Х2		0,1
	Х4		0,1		-2
	Х5		0,02		-0,5
	zj – cj		-0,13		0,24

Элементы очередной симплексной таблицы рассчитывают на основе численных значений (элементов) предыдущей таблицы, пользуясь соответствующими правилами. Эти правила могут быть выражены двумя простыми формулами. Предварительно введем необходимые обозначения. Переменная, которая в целях улучшения плана вводится в базис, обозначается через Х_k; переменная, удаляемая из базиса, - Х_r. Столбец Х_k и строка Х_r называются главными (ключевыми). Элементы предыдущей таблицы обозначим через – a_ij, где i – номер строки, j – номер столбца. Символы очередной таблицы дополняются штрихом - a′_ij. Элемент, стоящий на пересечении главной строки и главного столбца, называется главным элементом таблицы – a_rk.

Символ элементов главной строки – a_ri, главного столбца – a_ik. Соответствующие элементы очередной таблицы, стоящие в k-ой строке, обозначают через a′_kj, а элементы столбца r - a′_ir. Теперь познакомимся с симплексными формулами.

a_zj

a′_kj = ------,. (2.105.)

a_zk

По формуле находим элементы k-ой строки таблицы 2.37.

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

a′_2.0 = -------- = 40000

0,05

0,005

a′_2.1 = --------- = 0,1

0,05

0,05

a′_2.2 = -------- = 1

0,05

a′_2.3 = ------- = 20

0,5

a′_2.4 = ------ = 0

0,05

a′_2.5 = ------ = 0

0,05

По следующей формуле находим все прочие элементы таблицы 2.37.:

a′_ij = a_ij - a′_kj a_ik, (2.106.)

Элементы строки Х₄:

a′_4.0 = 180000 – 40000 х 0,1 = 14000

a′_4.1 = 0,11 – 1 х 0,1 = 0

a′_4.2 = 0,1 – 1 х 0,1 = 0

a′_4.3 = 0 – 20 х 0,1 = -2

a′_4.4 = 1 – 0 х 0,1 = 1

a′_4.5 = 0 – 0 х 0,1 = 0

Таким же образом вычисляем элементы строки Х₅, то есть из элементов строки Х₅ таблицы 2.36 вычитаем произведения соответствующих элементов (a′_kj a_ik) – см. формулу.

Элементы строки Х₅:

a′_5.0 = 3200 – 40000 х 0,025 = 2200

a′_5.1 = 0,0225 – 0,1 х 0,025 = 0,02

a′_5.2 = 0,025 – 1 х 0,025 = 0

a′_5.3 = 1 – 20 х 0,025 = 0,5

a′_5.4 = 0 – 0 х 0,025 = 0

a′_5.5 = 1 – 0 х 0,025 = 1

По этой формуле устанавливаем элементы индексной строки:

a′_0.0 = 48000; a′_0.1 = -0,13; a′_0.2 = 0; a′_0.3 = 24; a′_0.4 = 0; a′_0.5 = 0.

По второму варианту плана в хозяйстве будет произведено 40000 ц ячменя (Х₂ = 40000), или 48000 ц к.ед. (С = 48000). Но при этом еще 14000 человеко-дней и 2200 тракторо-смен останутся неиспользованными (таблица 2.37.). Чтобы использовать эти трудовые ресурсы, видимо, необходимо запланировать наряду с производством ячменя возделывание более трудоемкой культуры – кормовой моркови.

Проверим план с помощью критерия оптимальности. При определении максимума (а мы добиваемся именно этого!) оптимальное решение должно иметь в индексной строке только неотрицательные элементы. В таблице 2.37. при Х₁ отрицательной (-0,13). Следовательно и второй вариант плана не оптимален.

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

При этом в число базисных переменных вводим Х₁.

Определим переменную (Х₂), удаляемую из базиса:

40000: 0,1 = 400000; 14000: 0,1 = 140000; 2200: 0,2 = 110000.

Как видим, наименьшее частное – в строке Х₅. Следовательно, эта переменная и естьХ₂. После расчета всех необходимых элементов получим третий вариант плана (таблица 2.38.).

Таблица 2.38.

сj ci	Базисные переменные	Свободные члены	0,25	1,2
Х1	Х2	Х3	Х4	Х5
1,2	Х2				22,5		-5
	Х3				0,5		-5
0,25	Х4				-25
	zj – cj				20,75		6,5

Коэффициенты индексной строки таблицы неотрицательны. Следовательно, получено оптимальное решение. Этим оптимальным планом предусматривается произвести 110000 ц кормовой моркови и 29000 ц ячменя. Всего планируется получить 62300 ц к.ед., в том числе 27500 ц к.ед. даст кормовая морковь (110000 х 0,25). Пашня и механизированный труд будут использованы полностью. Так как Х₃ и Х₄ находятся в числе небазисных неизвестных, то есть равны нулю.

Теперь остается определить посевные площади под запланированными культурами.

1. Посевная площадь кормовой моркови – 550 га (111000: 200).

2. Посевная площадь ячменя – 1450 га (29000: 20).

3. Итого – 2000 га (550 + 1450).

Будет затрачено механизированного труда (тракторо-смен).

1. На производство кормовой моркови – 2475 (550 х 4,5).

2. На производство ячменя – 725 (1450 х 0,5).

3. Итого – 3200.

Варианты конно-ручного труда составят (человеко-дней).

7. На производство кормовой моркови – 12100 (550 х 205)

8. На производство ячменя – 2900 (1450 х 2).

9. Итого – 15000.

Следовательно, остается недоиспользованными 3000 чел.-дней (18000 - 15000).

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

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

Для демонстрации этого положения решим еще одну небольшую задачу.

Задача 2. Пусть требуется определить оптимальное сочетание посевных площадей трех культур: пшеницы, гречихи и картофеля. Для возделывания этих культур хозяйство может выделить: пашни 6000 га, 5000 человеко-дней для выполнения механизированных работ и 9000 человеко-дней для конно-ручных работ. Плановая урожайность пшеницы – 20 ц, гречихи – 10 и картофеля – 100 ц.

Затраты труда на гектар (человеко-дней):

Пшеница Гречиха Картофель

Механизированного……………… 0,5 1 5

Конно-ручного…………………… 0,5 0,5 20

Прибыль от 1 ц: пшеницы – 4 руб., гречихи – 10, картофеля – 3 руб.

Требуется найти такое сочетание посевов этих культур, которое обеспечило бы максимум прибыли.

По данным условиям задачи составим вспомогательную таблицу (таблица 2.39.).

Таблица 2.39.

Дата добавления: 2015-07-18