Часть 2 .Линейное и дискретное программирование

ЛАБОРАТОРНЫЙ ПРАКТИКУМ

по дисциплине «Математические методы в экономике»

Часть 2.Линейное и дискретное программирование

Для подготовки студентов по направлениям 080500 - менеджмент и 080100 - экономика

 

Москва 2008

 

 

УДК 519.85 (085)

ББК 22.18 & 73

Л 97

Рекомендовано к изданию методической комиссией экономического факультета. Протокол №___ от _________2008 г.

Председатель методической комиссии

экономического факультета, д.э.н. Шакиров Ф.К.

 

Рецензенты: Алексанов Д.С., доцент, заведующий кафедрой информационно-консультационных технологий в АПК; Копёнкин Ю.И., профессор кафедры экономической кибернетики РГАУ - МСХА имени К.А. Тимирязева.

Лядина Н.Г., Ермакова Е.А., Светлова Г.Н., Уразбахтина Л.В., Хотов А.В.

Лабораторный практикум по дисциплине «Математические методы в экономике».Часть 1.Линейное и дискретное программирование. Уч. пособие. М.: ФГОУ ВПО ргау - МСХА им. К.А. Тимирязева, - 127 с.

Для студентов экономического факультета специальности 080116 – Математические методы в экономике, изучающих дисциплину«Математические методы и модели исследования операций» и студентов направления 080500 – “Менеджмент” специальности 080502 - Экономика и управление на предприятиях АПК, изучающих дисциплину «Математические методы в экономике», для студентов учетно-финансового факультета специальностей 080105и 080801, изучающих дисциплину«Экономико-математические методы и модели» на кафедре экономической кибернетики ргау - МСХА имени К.А. Тимирязева.

Современное состояние экономики требует от специалистов знаний по использованию экономико-математических методов в области планирования и управления. Для знакомства с дисциплиной на примерах излагаются теоретические вопросы линейного программирования, подробно рассматриваются основные понятия и обозначения, правила перехода от одной формы к другой, правила преобразований Жордана-Гаусса, лежащие в основе преобразований однократного замещения, применения фундаментальной теоремы, симплексного и М- метода, излагаются основы теории двойственности, рассматриваются транспортные задачи и дискретное программирование. Излагаются возможности решения задач линейного программирования на ЭВМ. Приводятся примеры условий задач для лабораторных занятий и методические рекомендации по их выполнению.

 

Содержание

Введение. 4

Лабораторная работа № 13 «Решение задач линейного программирования в приложении MS Excel «Поиск решения»». 5

Лабораторная работа № 14 «Метод искусственного базиса или М- метод». 16

Лабораторная работа №15-17 «Основы теории двойственности». 25

Лабораторная работа №18 «Транспортная задача на минимум целевой функции» 46

Лабораторная работа № 19 «Особенности решения транспортной задачи на максимум» 59

Лабораторная работа № 20 Видоизменения транспортной задачи (блокировка перевозок, ограничение пропускной способности). 67

Лабораторная работа № 21 «Транспортная задача с учетом производственных затрат» 81

Лабораторная работа № 22 «Решение задач о назначениях». 86

Лабораторная работа №23 «Целочисленное программирование». 100

Лабораторная работа № 24 «Параметрическое программирование с параметром в целевой функции». 107

Лабораторная работа № 25. «Параметрическая транспортная задача с параметром в целевой функции». 116

Глоссарий основных понятий. 125

Рекомендуемая литература. 129

 

 

 

Введение

Учебное пособие предназначено для использования студентами согласно Государственного образовательного стандарта высшего профессионального образования по специальности «Математические методы в экономике» (квалификация – экономист-математик), утвержденной 14 апреля 2000 г., который предусматривает следующие требования к содержанию дисциплины ОПД.Ф.02 «Математические методы и модели исследования операций»:

Экономические приложения (примеры типовых задач). Теория линейного программирования. Теория двойственности и экономические приложения. Численные методы решения задач линейного программирования. Задачи целочисленного программирования, их экономические приложения и методы решения.

Цель работы – дать основные теоретические понятия о задачах линейного программирования – раздел «Экономические приложения (примеры типовых задач)», необходимые для постановки и решения профессиональных задач, а также научить записывать экономические и математические условия задач в различных эквивалентных формах и переходить от записи в одной форме к другой - часть разделов «Теория линейного программирования» и «Численные методы решения задач линейного программирования».

 

 

Лабораторная работа № 13 «Решение задач линейного программирования в приложении MS Excel «Поиск решения»»

Теоретическая часть

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

Наилучшие результаты она позволяет получить для задач выпуклого (в том числе линейного) программирования при условии отсутствия ограничений типа «равно».

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

Результаты оптимизации оформляются в виде отчетов трёх типов:

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

· Устойчивость. Содержит сведения о чувствительности решения к малым изменениям в формуле целевой функции или в формулах ограничений. Отчет не создается для моделей, значения переменных в которых ограничены множеством целых чисел.

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

·

Для решения задачи оптимизации необходимо:

1. На рабочем листе Excel создать таблицу исходных данных, в которой должны отображаться формулы. Для этого необходимо предварительно дать команду Сервис/Параметры, выбрать вкладку Вид и установить флажок Формулы.

2. Запустить процедуру поиска решения, дав команду Сервис/Поиск решения, и в появившемся диалоговом окне Поиск решения заполнить поля:

· Установить целевую ячейку:

· Изменяя ячейки:

· Ограничения:

Целевая ячейка — ячейка на рабочем листе с таблицей исходных данных, куда занесена формула целевой функции.

Изменяемые ячейки — ячейки из таблицы исходных данных, отражающие значения переменных, которые необходимо найти в результате оптимизации. Ячейки не должны содержать формулы, их значения должны влиять на значение целевой ячейки[1].

Ограничения - задаются посредством кнопки Добавить и отражают связь формул ограничений с их свободными членами. Ограничения могут быть как скалярными (например, A1< =3; A2< =A3, где A1, A2, A3 — имена ячеек Excel), так и векторными (например, A1: A10> =B1: B10, где A1: A10, B1: B10 — диапазоны ячеек).

3. Получить отчеты оптимизации и провести их анализ.

 

Общая постановка задачи

Задача 1

Фирма производит две модели изделий. Для каждого изделия модели А требуется 3 ед. сырья, а для модели В – 4. Фирма от своих поставщиков получает до 1700 ед. сырья в неделю. Для каждого изделия модели А требуется 0, 2 ч машинного времени, а для изделия В – 0, 5 ч. В неделю можно использовать 160 ч машинного времени. Сколько изделий каждой модели следует выпускать фирме в неделю, чтобы получать максимальную прибыль, если каждое изделие модели А приносит 2 ден. ед. прибыли, а каждое изделие модели В – 4ден. ед. прибыли?

Переменные задачи:

x₁ - количество изделий типа А, ед.

x₂ - количество изделий типа В, ед.

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

3х₁+4х₂ £ 1700 – баланс сырья (ед.)

0, 2х₁+0, 5х₂ £ 160 – баланс времени (ч)

Целевая функция:

max Z = 2x₁+4x₂ –максимум прибыли.

 

Задача 2

Молочный завод производит молоко, кефир и сметану. На производство 1 ц молока, кефира и сметаны требуется соответственно 1, 01; 1, 01; 9, 45 ц молока. Производство молока предполагает пастеризацию и разлив молока по 1л пакетам. Затраты рабочего времени при разливе 1 ц молока и кефира составляют 0, 17 и 0, 18 машино-часа. Расфасовка 1 ц сметаны на специальном автомате занимает 3, 15 часа. Всего за сутки молочный завод может переработать 140 ц молока. Основное оборудование может быть занято в течение 21, 0 машино-часа, а автомат по расфасовке сметаны - в течение 16 час. Прибыль от реализации 1ц молока, кефира и сметаны соответственно равна 31, 23 и 137 руб. Завод должен производить ежедневно не менее 90 ц молока в сутки.

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

Математическая формулировка задачи линейного программирования:

x₁ — выпуск пастеризованного молока, ц/сут.

x₂ — выпуск кефира, ц/сут.

x₃ — выпуск сметаны, ц/сут.

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

Баланс молока (сырья): 1, 01x₁ + 1, 01x₂ + 9, 45x₃ [140 (ц/сут.).

Балансы оборудования: 0, 17x₁ + 0, 18x₂ [ 21 (ч/сут.), 3, 15x₃ [ 16 (ч/сут.)

Минимальный выпуск продукции: x₁ [ 90 (т/сут.), x₂ [ 10 (ц/сут.).

Условия неотрицательности: x₁ m 0, x₂ m 0, x₃ m 0 (ц/сут.).

Целевая функция:

max Z =31x₁ + 230x₂ +137x₃ (руб.).

Пример выполнения работы

Задача 1

Задача 2

Последовательность выполнения:

1. Сформировать на рабочем листе таблицу, описывающую модель задачи. Внести в ячейки необходимые формулы.

2. Дать команду Сервис-Поиск решения.

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

Если в задаче все ограничения одного типа, то их можно задать выделением группы ячеек.

 

4. В диалоговом окне Поиск решения нажать кнопку Выполнить.

Замечание. В различных версиях MS Excel (95, 97, 2000, XP) наименования управляющих элементов диалоговых окон Поиск решения и Параметры поиска решения могут быть неодинаковыми, но расположение и назначение их остаются неизменными.

5. В диалоговом окне Результаты поиска решения установить переключатель Сохранить найденное решение, выбрать все 3 типа отчетов, щелкая по их названиям левой кнопкой мыши, и нажать кнопку ОК.

6. Проанализировать полученные отчеты .

Результаты решения выводятся на лист 1 (Отчет по результатам.)

 

Лист 1 Отчет по результатам

 

На листе 2 (исходные данные) в строке 8 (значения по решению) выводятся значения соответствующих переменных, в ячейке E8 - значение целевой функции, в ячейках E3: E6 – значения выполнения ограничений.

Лист 2 Исходные данные

 

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

Если принять во внимание вышеизложенные факторы, то модель может быть расширена за счет них ограничениями по:

· трудовым затратам;

· упаковке в расчете на сутки;

· учету возможных каналов реализации;

· степени задержки поставки молока партнером в пределах (суток, недели).

Контрольные вопросы

1. Для чего используется процедура «Поиск решения»?

2. Какие задачи могут решаться «Поиском решения» наиболее эффективно?

3. В виде каких отчетов оформляются результаты оптимизации при использовании средства «Поиск решения»?

4. Из скольких зон состоит таблица для процедуры «Поиск решения»?

5. Как ввести векторное ограничение при использовании поиска решения?

6. Как выбирать начальные значения переменных при решении модели с помощью средства «Поиск решения»?

Лабораторная работа № 14 «Метод искусственного базиса или
М- метод»

Теоретическая часть

Правила перехода к М-задаче от исходной (основной) задачи

1. В ограничения типа меньше или равно (£ ) вводим неотрицательные дополнительные переменные с коэффициентом плюс единица.

2. В ограничения типа больше или равно (³ ) вводим неотрицательные дополнительные переменные с коэффициентом минус единица.

3. В ограничения, не содержащие базисные переменные, вводим неотрицательные искусственные базисные переменные y_i.

4. В целевую функцию дополнительные переменные вводятся с нулевым коэффициентом.

5. В целевую функцию искусственные базисные переменные при решении задачи на максимум целевой функции вводятся с коэффициентом " -М", а при решении задачи на минимум целевой функции вводятся с коэффициентом " +М", где " М" большое положительное число: М ³ 10⁴.

Алгоритм М-метода решения задачи на максимум целевой функции

1. М-задача записывается в симплексную таблицу.

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

3. Подсчитываются оценки по формуле оценок:

, j=0, 1,..., n

и записываются в последнюю строку таблицы.

4. Проверка решения на оптимальность по признаку: решение задачи на максимум целевой функции оптимально, если все оценки при переменных неотрицательные. Если критерий выполняется, то переход к пункту 12, если нет, то переход к пункту 5.

5. Разрешающий столбец выбирается по минимальной отрицательной оценке.

6. Если в разрешающем столбце есть хотя бы один положительный элемент, то переходим к пункту 7. Если нет, то целевая функция М-задачи не ограничена, переход к пункту 14.

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

8. По наименьшему симплексному отношению находится разрешающая строка.

9. На пересечении разрешающего столбца и разрешающей строки находится разрешающий элемент.

10. Пересчет таблицы по общим правилам и заполнение новой таблицы.

11. Переход к пункту 4.

12. Запись оптимального решения М-задачи и значения целевой функции.

13. Если все искусственные переменные М-задачи равны нулю, то запись соответствующего решения основной задачи. Если хоты бы одна из искусственных переменных отлична от нуля, то необходимо корректировать условие основной задачи.

14. Если целевая функция М-задачи не ограничена, то необходимо в М-задачу ввести дополнительное ограничение:

х₁+ х₂+…+ х_n£ М и решить новую М-задачу. Если после решения новая М-задача

а) будет иметь оптимальное решение с нулевыми искусственными переменными, то целевая функция основной задачи не ограничена;

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

Пример выполнения работы

Пример

 

Каноническая форма записи:

 

В системе ограничений канонической формы нет единичного базиса. Необходимо ввести в 1-е и 3-е ограничения искусственные базисные переменные и перейти к М-задаче. Получим:

 

 

 

№1	Cj							-M	-M	7-2M	со сс
Ci	П БП	ai0	X1	X2	X3	X4	X5	Y1	Y2	KΣ
-M	Y1					-1
	X5		2								4 i*
-M	Y2
Z	Dj	-23M	-4M - - 4 j*	-3M -2	-2M --1	M				-31M -7	X

 

№2	Cj							-M	-M	7-2M	со C0
Ci	П БП	ai0	X1	X2	X3	X4	X5	Y1	Y2	KΣ
-M	Y1			1/2	1/2	-1	-1/2			9/2
	X1			1/2	1/2		1/2			13/2
-M	Y2			1/2	-1/2		-3/2			5/2	6 i*
Z	Dj	-7М+16	0	-М j*		M	2М+2			-5М+19	X

 

№3	Cj							-M	-M	7-2M	со C0
Ci	П БП	ai0	X1	X2	X3	X4	X5	Y1	Y2	KΣ
-M	Y1				1	-1			-1		1 i*
	X1								-1
	Х2				-1		-3				-
	Dj	-М+16	0		-М+1 j*	М	-М+2		2М		X

 

№4	Cj							-M	-M	7-2M
Ci	П БП	ai0	X1	X2	X3	X4	X5	Y1	Y2	KΣ
	Х3					-1			-1
	X1							-1
	Х2					-1	-2
Z	Dj		0					М-1	М+1	2М+17

Так как все оценки при переменных неотрицательные, то решение М-задачи оптимальное. Так как все оценки при свободных переменных не равны нулю, то оптимальное решение единственное. Х_м^*(0, 7, 1, 0, 0, 0, 0), max Z_м = 15.

Искусственные переменные в оптимальном решении равны нулю, поэтому их можно отбросить и получить соответствующее оптимальное решение основной задачи: Х^*(0, 7, 1, 0, 0), max Z = 15. Базисная переменная Х₁ равна нулю, поэтому оптимальное решение – вырожденное.

Теоретическая часть

Пример 1

Записать двойственную задачу для следующей прямой задачи.

Найти max Z = х₁ – 2х₂+х₃ – 4х₄

х₁ + 2х₂+ 3х₃ – 4х₄ = 5

х₁ - 3х₂+ х₃ + 6х₄ = 2

2х₂ - 8х₃ – 6х₄ £ 3

2х₁ + х₂ - х₃ + 5х₄ £ 4

х₁ ³ 0, х₂ ³ 0

1. Вводим переменные двойственной задачи – Y_1, Y_2, Y_3, Y_4.

2. Записываем целевую функцию двойственной задачи:

Найти min T = 5Y₁+ 2Y₂ + 3Y₃+ 4Y₄

3. Записываем систему ограничений двойственной задачи:

Y₁+Y₂ + 2Y₄ ³ 1

2Y₁- 3Y₂+ 2Y₃ + Y₄ ³ -2

3Y₁+ Y₂ - 8Y₃ - Y₄ = 1

-4Y₁+ 6Y₂ - 6Y₃ + 5Y₄ = -4

4. Вводим условия неотрицательности для переменных двойственной задачи

Y₃ ³ 0, Y₄ ³ 0 (Y₁ и Y2 – произвольные).

Пример

Записать исходную задачу. Решить симплексным методом, проанализировать коэффициенты последней симплексной таблицы и двойственные оценки.

Рассмотрим следующую задачу: в хозяйстве имеется 200 га орошаемой и 500 га богарной пашни. Предполагается возделывать на этих участках турнепс и подсолнечник на силос. Трудовые ресурсы хозяйства 12000 чел.-дн., ресурс поливной воды – 500 тыс. м³.

Таблица. Эффективность возделывания с.-х. культур.

Показатель	Турнепс	Подсолнечник
на богаре	на поливе	на богаре	на поливе
1. Затраты труда на 1га, чел.-дн.
2. Норма полива, тыс.м3/га	-		-
3. Выход кормов, ц к.ед./га

Определить оптимальное распределение площади пашни, обеспечивающее максимальное производство кормов.

Составим задачу линейного программирования.

Определить значения переменных:

Х₁, га – площадь посева турнепса на богаре;

Х₂, га – площадь посева турнепса на поливе;

Х₃, га – площадь посева подсолнечника на богаре;

Х₄, га – площадь посева подсолнечника на поливе,

которые обеспечат получение максимального значения целевой функции Z, ц к.ед. max Z = 30 Х₁+50 Х₂+22 Х₃+60 Х₄

при условиях:

баланс богарной пашни, га: Х₁+Х₃ £ 500

баланс орошаемой пашни, га: Х₂+Х₄ £ 200

баланс трудовых ресурсов, чел.-дн., 40 Х₁+50 Х₂+20 Х₃+30 Х₄ £ 12000

баланс ресурсов воды для полива, тыс.м³: Х₂+2Х₄ £ 500

Х_j ³ 0, ( j = 1¸ 4).

Приведем задачу к каноническому виду и занесем в первую симплексную таблицу исходное опорное решение.

Первая симплексная таблица

№1

Cj

Ci

П БП

аi0

X1

X2

X3

X4

X5

X6

X7

X8

C0

X5

-

X6

I*

X7

X8

Z

Dj

-30

-50

-22

-60

Х

J*

 

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

Последняя симплексная таблица

№4	Cj
Ci	П БП	аi0	X1	X2	X3	X4	X5	X6	X7	X8
	X5		-1	-1				3/2	-1/20
	X4
	X3							-3/2	1/20
	X8			-1				-2
Z	D j								11/10

 

В таблице приведено оптимальное решение (единственное):

 

Максимальное количество кормов – 18600 ц к.ед. будет получено при возделывании подсолнечника на силос на богаре на площади 300 га и на поливе на площади 200 га. При этом недоиспользуется 200 га богарной пашни и 100 тыс. м³ воды для полива. Полностью используются трудовые ресурсы (X₇=0) и орошаемая пашня (X₆ = 0). Турнепс на корм не возделывается (X₁ =0, X₂ = 0).

Каждой прямой задаче линейного программирования можно поставить в соответствие двойственную. Рассмотрим экономический смысл двойственной задачи.

Переменные Y₁, Y₂, Y₃, Y₄ – условные цены соответствующих ресурсов. Необходимо определить оптимальный план ^*(Y₁, Y₂, Y₃, Y₄) при условиях: Y₁+40Y₃ ³ 30

Y₂+ 50Y₃ + Y₄ ³ 50

Y₁+ 20Y₃ ³ 22

Y₂ +30Y₃ + 2Y₄ ³ 60

Y_i ³ 0, i = 1¸ 4

min T = 500Y₁+ 200Y₂ + 12000Y₃+ 500Y₄

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

 

Решим Y-задачу М-методом.

Найти

при условиях:

Y₁+ 40Y₃ - Y₅+ W₁=30

Y₂+ 50Y₃ + Y₄ – Y₆ + W₂ = 50

Y₁+ 20Y₃ – Y₇ + W₃ = 22

Y₂ +30Y₃ + 2Y₄ – Y₈ + W₄ = 60

Y_i ³ 0, i = 1¸ 8; W_i ³ 0, i = 1¸ 4

Последняя симплексная таблица М-задачи.

Cj

-500

-200

-12000

-500

Сi

П БП

ai0

Y1

Y2

Y3

Y4

Y5

Y6

Y7

Y8

-12000

Y3

11/10

1/20

-1/20

Y6

-1

-1

Y5

-2

-200

Y2

-3/2

3/2

-1

Z

D j

-18600

 

Так как искусственные переменные W_i = 0, i = 1 ¸ 4, то их в таблицу записывать не стали.

Сопоставляя конечные симплексные таблицы прямой и двойственной задач можно заметить, что нет необходимости решать их отдельно. Решая прямую задачу, мы одновременно получаем и решение двойственной задачи. Симплексный метод обладает такой особенностью, что при решении одной из двойственной пары автоматически получается решение другой задачи без дополнительных вычислений Z_max = T_min = 18600 (значения целевых функций прямой и двойственной задачи совпадают).

Оценки свободных дополнительных переменных полностью совпадают со значениями переменных, вошедших в базис двойственной задачи: Y₁ =D₅, Y₂ =D₆, Y₃ =D₇, Y₄ =D₈, (Y₅ =D₁, Y₆ =D₂, Y₇ =D₃, Y₈ =D₄).

Эти величины получили название двойственных оценок (объективно-обусловленных оценок) ограниченных ресурсов.

Y_i - условные цены соответствующих ресурсов.

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

Это позволяет установить пропорции взаимозаменяемости ресурсов, оценить их важность, эффективность с точки зрения критерия оптимальности, выявить " узкие места" и вскрыть внутренние резервы плана. Рассмотрим двойственные оценки нашей задачи.

Богарная пашня и ресурс поливной воды (x₅ и x₈) недоиспользуются, т.е. их имеется больше, чем нужно, поэтому их оценки равны нулю (У₁ = 0, У₄ = 0). При нулевой оценке ресурса изменение его объема в пределах избыточности не вызовет никаких колебаний в структуре производства и не повлияет нa значение целевой функции. Приобретение лишней единицы избыточного ресурса всегда уменьшает доход хозяйства, так как она остается неиспользованной. Ресурсы, используемые в полном объеме, всегда имеют положительную оценку.

Условия задачи определяют оценку каждого фактора, внутреннюю для данного производства. Следует иметь ввиду, что эта оценка является относительной. Одни и те же производственные факторы для разных предприятий и районов представляют различную ценность.

В нашем примере полностью используются орошаемая пашня и трудовые ресурсы, наибольшее значение имеет ресурс " орошаемая пашня" (оценка D₆ = 27, а D₇ =11/10). Чтобы выяснить, что означает здесь двойственные оценки, рассмотрим экономическое содержание всех показателей симплексной таблицы.

Проведем такой анализ для полученного оптимального плана Х-задачи.

Площадь орошаемой пашни используется в решении полностью (х₆ =0). Пусть небазисная переменная x₆ войдет в базис с единичной интенсивностью: x₆=1 (т.е. недоиспользуется I га орошаемой пашни, ресурс составит 199 га). Это приведет к следующим изменениям в оптимальном плане (см. коэффициенты в столбце x₆ последней симплексной таблицы).

Площадь подсолнечника на орошаемой пашни (x₄) сократится на 1гa (a₂₆=1), площадь подсолнечника на богаре (х₃) увеличится на 3/2 га (a₃₆ = -3/2), недоиспользование богарной пашни (х₅) сократится на 3/2 га (a₁₆ = 3/2), освободится 2 тыс.м³ поливной воды (a₄₆ = -2).

Тогда сокращение посевов х₄ приведет к потерям кормов в размере 60 ц к.ед. (С₄), а за счет увеличения посевов х₃ будет произведено 3/2 * 22 = 33 ц к.ед. (С₃ = 22). В результате производство кормов сократится на 60 - 33 = 27 (ц к.ед, ). Это и есть D₆ -оценка данного ресурса. Следовательно, эта оценка показывает, сколько кормов производится в расчете на I га орошаемой пашни (при сложившейся структуре производства) или сколько дополнительной продукции можно будет получить, привлекая дополнительно единицу данного ресурса.

Мы изменяли объем только одного вида ресурса: орошаемой пашни, а объем трудовых ресурсов не менялся. Не повлияют ли изменения в оптимальном плане на использование труда? На каждый гектар подсолнечника, возделываемого при орошении, затрачивается 30 чел./дн., а на богаре - 20 чел./дн., следовательно, при сокращении посевов на орошаемой пашне освобождается 30 чел./дн. труда и их можно использовать для выращивания подсолнечника на площади 1, 5 га (1, 5x20= 30 чел./дн.). Таким образом, увеличение посевов подсолнечника на богаре будет обеспечено трудовыми ресурсами.

Аналогично можно провести анализ и по коэффициентам переменной х₇ (трудовые ресурсы).

Теоретическая часть

Общая постановка задачи

Транспортная задача – одна из распространенных задач линейного программирования. Она позволяет определить оптимальный план перевозок груза.

В общем виде задачу можно представить следующим образом: в m пунктах производства А₁, А₂, …, А_m имеется однородный груз в количестве а₁, а₂, …, а_m. Этот груз необходимо доставить в n пункты назначения В₁, В₂, …, В_n в количестве b₁, b₂, …, b_n. Стоимость перевозки единицы груза (тариф или расстояния) из пункта А_i в пункт В_j равна С_ij. Требуется найти план перевозки, обеспечивающий минимальную стоимость перевозки. При этом весь груз должен быть вывезен и все потребности удовлетворены.

Пусть Х_ij – количество груза перевозимого от i –ого поставщика к j-ому потребителю.

Первая группа ограничений - весь груз должен быть вывезен:

Х₁₁ + Х₁₂ + …+ Х_1n = а₁

Х₂₁ + Х₂₂ + …+ Х_2n = а₂

_{……………………………………..}

Х_m1 + Х_m2 + …+ Х_mn = а_m

 

 

Вторая группа ограничений – все потребности должны быть удовлетворены.

 

Х₁₁ + Х₂₁ + …+ Х_m1 = b₁

Х₁₂ + Х₂₂ + …+ Х_m2 = b₂

_{……………………………………..}

Х_1n + Х_2n + …+ Х_mn = b_m

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

Х_ij ³ 0, i = 1¸ m; j = 1¸ n

Целевая функция

min Z = C₁₁Х₁₁ + C₁₂Х₁₂ + …+ C_1nХ_1n + C₂₁ Х₂₁ + C₂₂Х₂₂ + …+ C_2nХ_2n + …+ C_mnХ_mn

 

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

найти

при условиях:

	(i = l, ..., m),	(1)
	(j = 1, ..., n),	(2)
xij ³ 0	(i = l, ..., m; j = l, ..., n).

 

Всякое неотрицательное решение систем уравнений (1)-(2), определяемое матрицей X=(x_ij ), называют опорным планом транспортной задачи, а план X*=(x_ij ), при котором функция Z принимает минимальное значение - называется оптимальным планом транспортной задачи.

Особенность транспортной задачи:

· система ограничений есть система уравнений (т.е. транспортная задача задана в канонической форме);

· коэффициенты при переменных системы ограничений равны единице или нулю;

· каждая переменная входит в систему ограничений два раза: один раз – в систему (1) и один раз – в систему (2).

Для записи транспортной задачи принято использовать распределительную таблицу.

 

12345Следующая ⇒

Поделиться: