Изменение коэффициента в целевой функции при переменной, не вошедшей в базисное решение

Изменение коэффициента при небазисной переменной приводит к изменению только одного элемента индексной строки, соответствующей этой переменной.

, где - величина, на которую был изменен коэффициент .

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

Демонстрационная задача (ДЗ): (Безгинов А.Н., «Линейные модели»).

В хозяйстве сложились следующие основные отрасли: молочное скотоводство (коровы), свиноводство, кормопроизводство и производство зерна. На продажу используется 90% зерна, остальное на корм скоту. В соответствии с планом поставок хозяйство должно произвести не менее трех тонн свинины. По условиям содержания животных хозяйство может содержать не более 110 коров. Общая площадь пашни в хозяйстве – 900 га. Запас кормов на пастбищах и сенокосах 1000 ц.к.е. другие исходные данные приведены в таблице 33.

Таблица 33

Исходные данные по некоторым ресурсам и технологическим коэффициентам для задачи ДЗ

Виды ресурсов, норм и т.д., единицы измерения

Нормативные коэффициенты для различных отраслей хозяйства

Ресурсы хозяйства

Производство зерна

Скотоводство

Свиноводство

Производство кормов

Трудозатраты

чел. ч./га,

чел. ч./гол.

Ден. затраты

тыс.руб/га

тыс.руб/гол

Урожайность, ц.к.е./га

Нормы кормления, ц.к.е./гол: Общая

Концентраты

Продуктив-ность, л/гол

кг/гол

Чистый доход, тыс.руб/ц.к.е.

тыс.руб/л

0,2

тыс.руб/кг

Доход хозяйства определяется продажей молока, свинины и части зерна. Необходимо определить оптимальное сочетание отраслей хозяйства. В ходе расчетов вычислить общий объем реальных денежных расходов хозяйства. Баланс кормов составить по всем видам животных, а также отдельно по коровам и свиньям.

В соответствии с исходными данными, сформируем группу основных переменных:

Х₁ – площадь пашни под зерновыми, га;

X₂ – поголовье коров, гол;

Х₃ – поголовье свиней, гол;

Х₄ - площадь пашни под кормовыми культурами, га;

X₅ – общие реальные денежные расходы хозяйства, руб.

На все переменные накладывается условие неотрицательности:

Целевая функция – суммарный чистый доход от всех видов товарных отраслей. При формировании целевой функции необходимо учесть размерность соответствующих нормативных коэффициентов (последняя строка табл.1), долю зерна на продажу (0,9), урожайность зерна и продуктивность животных. В итоге получим:

Z = 10*0,9*25*X₁ + 0.2*4000*X₂ + 1*100*X₃ = 225*X₁ +800*X₂ + 100*X₃.

Построим систему ограничений.

1. Ограничение по площади пашни (учитываются все культуры, под которые отводится пашня).

Х₁ + Х₄ 900

2. Ограничение по трудовым ресурсам.

В соответствии с нормами трудозатрат (первая строка табл.1) имеем:

5*Х₁ + 50*Х₂ + 100*Х₃ + 50*Х₄ 40000

3. Ограничение по денежным ресурсам.

Х₅ 90000

4. Ограничение по кормовому балансу.

Общий вид ограничения таков:

«потребность в кормах” “производство кормов”

При записи ограничений должны быть учтены нормы кормления, урожайность кормовых культур, доля зерна (0,1), используемого на фураж.

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

По всем видам животных:

80*Х₂ + 40*Х₃ 0,1*25*Х₁ + 50*Х₄ + 1000

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

По концентратам:

30*Х₂ + 10*Х₃ 2,5*Х₁

В правой части этого неравенства используется только переменная Х₁, т.к. здесь должны быть учтены только концентрированные корма.

5. Отдельно по коровам (по всем видам кормов):

80*Х₂ 2,5*Х₁ + 50*Х₄ + 1000

6. Отдельно по свиньям (по всем видам кормов):

40*Х₃ 2,5*Х₁ + 50*Х₄

7. Ограничение по поголовью коров:

Х₂ 110

8. Ограничение по гарантированному производству свинины:

100*Х₃ 3000

9. Уравнение для расчета общих денежных затрат (см. вторую строчку табл. 1):

70*Х₁ + 25*Х₂ + 100*Х₃ + 300*Х₄ = Х₅

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

С учетом всего сказанного получим следующую систему ограничений:

Х₁ + Х₄ 900 (1)

5*Х₁ + 50*Х₂ + 100*Х₃ + 50*Х₄ 40000 (2)

Х₅ 90000 (3)

-2,5*Х₁ + 80*Х₂ + 40*Х₃ - 50*Х₄ 1000 (4)

-2,5*Х₁ + 30*Х₂ + 10*Х₃ 0 (5)

-2,5*Х₁ + + 40*Х₃ – 50*Х₄ 0 (6)

Х₂ 110 (7)

100*Х₃ 3000 (8)

70*Х₁ + 25*Х₂ + 100*Х₃ + 300*Х₄ = 0 (9)

Добавим к этой системе требование, накладываемое на целевую функцию:

Z = 225*Х₁ + 800*Х₂ + 100*Х₃ max, (10)

и условия неотрицательности переменных:

Х 0, j = 1,…,5. (11)

В совокупности соотношения (1) … (11) образуют развернутую математическую формулировку общей задачи линейного программирования в неканоническом представлении. В обобщенном виде та же задача записывается по следующей схеме:

Z =

i=1,…,m,

где m – общее число ограничений;

n – общее число основных переменных, а символ означает либо “ ” либо “ ” либо “ = ”.

Общую развернутую запись задачи, оформленную в виде таблицы, называют математической моделью задачи. Табличная форма это наиболее удобное представление задачи при работе на ЭВМ (см. табл. 2).

Таблица 2