ОСНОВЫ СИСТЕМНОГО АНАЛИЗА МЕТОДИЧЕСКИЕ УКАЗАНИЯ

МИНИСТЕРСТВО АГРАРНОЙ ПОЛИТИКИ УКРАИНЫ

ЛУГАНСКИЙ НАЦИОНАЛЬНЫЙ АГРАРНЫЙ УНИВЕРСИТЕТ

 

Кафедра

физико-математических

дисциплин

 

 

Л.И. Леви, Е.А. Рыбинцева

 

ОСНОВЫ СИСТЕМНОГО АНАЛИЗА

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

 

к практическим занятиям,

Индивидуальной и самостоятельной работе

С заданиями для расчетно-графической работы

 

Для студентов инженерных специальностей

аграрных высших учебных заведений Украины

 

ЛУГАНСК – 2007

УДК 681.513:62-50

 

 

Составители:

 

ЛЕВИ Л.И., доктор технических наук, профессор, зав. кафедрой физико-

математических дисциплин;

 

РЫБИНЦЕВА Е.А., ассистент кафедры физико-математических дисциплин.

 

 

Основы системного анализа: Методические указания к практическим занятиям, индивидуальной и самостоятельной работе с заданиями для расчетно-графической работы для студентов инженерных специальностей аграрных высших учебных заведений Украины / Л.И. Леви, Е.А. Рыбинцева. – Луганск, изд-во ЛНАУ, 2007. – 66с.

 

 

Рецензенты:

 

ГРИБАНОВ В.М., доктор технических наук, профессор, зав. кафедрой прикладной математики Восточноукраинского национального университета им. В. Даля;

 

КОВАЛЬ А.В., кандидат физико-математических наук, доцент кафедры физико-математических дисциплин Луганского национального аграрного университета.

 

 

Издание рассмотрено и рекомендовано к печати на заседании кафедры физико-математических дисциплин (протокол № 1 от 5 сентября 2007г.);

 

на заседании методической комиссии строительного факультета (протокол № 1 от 12 сентября 2007г.).

 

СОДЕРЖАНИЕ

Введение Рекомендации по выполнению контрольной работы
	Графический метод решения задач линейного программирования
1.1	Формализация задачи линейного программирования, решаемой графическим методом
1.2	Алгоритм решения задачи линейного программирования графическим методом
1.3	Типовой пример
1.4	Индивидуальное задание №1
	Симплексный метод решения задач линейного программирования
2.1	Постановка задачи линейного программирования, решаемой симплексным методом
2.2	Алгоритм симплекс-метода
2.3	Типовой пример
2.4	Индивидуальное задание №2
	Применение метода искусственного базиса для решения задач линейного программирования (М-задача)
3.1	Постановка и методика решения М-задачи
3.2	Типовой пример
3.3	Индивидуальное задание №3
	Закрытая модель транспортной (распределительной) задачи
4.1	Формализация распределительной задачи
4.2	Методы построения первоначального опорного плана
4.3	Решение транспортной задачи методом потенциалов
4.4	Алгоритм последовательного улучшения опорного плана перевозок
4.5	Типовой пример
4.6	Индивидуальное задание №4
	Открытая модель транспортной задачи
5.1	Постановка и методика решения открытой транспортной задачи
5.2	Типовой пример
5.3	Индивидуальное задание №5
Литература

ВВЕДЕНИЕ

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

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

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

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

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

 

РЕКОМЕНДАЦИИ ПО ВЫПОЛНЕНИЮ КОНТРОЛЬНОЙ РАБОТЫ

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

ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ

ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Формализация задачи линейного программирования,

Решаемой графическим методом

z = c1x1 + c2x2 и ограничениями в виде неравенств

Алгоритм решения задачи линейного программирования

Графическим методом

1. Записать уравнения граничных прямых. 2. Построить графики граничных прямых на плоскости. 3. Выделить область решения каждого неравенства системы.

Типовой пример

Пусть дана следующая задача.

Найти максимум целевой функции

z = 2x₁ + 2x₂

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

x₁ ³ 0, x₂ ³ 0.

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

Решение.

Запишем уравнения граничных прямых и построим их графики на плоскости x₁Оx₂ (рис.1).

l₁ : x₁ + 2x₂ = 7, l₃ : x₂ = 3,

l₂ : 2x₁ + x₂ = 8, l₄ : x₁ + 2x₂ = 2.

Возьмем какую-нибудь пробную точку, например точку О(0; 0) (если это возможно). Выясним, какую полуплоскость определяет каждое неравенство (направления полуплоскостей отмечены стрелками). Определим область допустимых решений (многоугольник АВСDEF) как пересечение полученных полуплоскостей (рис.2).

Строим вектор-градиент(2; 2) и линию уровня c, взяв в качестве c₀ значение ноль: c : 2x₁ + 2x₂ = 0.

Перемещая параллельно самой себе линию уровня С в направлении вектора-градиента (2; 2), находим экстремальную точку Е как точку пересечения прямых l₁ и l₂ (рис.3). Координаты точки Е находим, решив систему из уравнений этих прямых:

В результате получим точку Е(3; 2).

Вычислим значение целевой функции в полученной точке Е(3; 2):

z(3; 2) = 3 ∙ 2 + 2 ∙ 2 = 10.

Ответ: z_max = 10 при x₁ = 3, x₂ = 2.

 

 

Рис. 1 Рис. 2

 

Рис. 3

1.4. Индивидуальное задание №1

 

Решить графическим методом задачу оптимизации в условиях следующей модели:

 

1. z = –x₁ + x₂ + 2 ®min 2. ­­z = 3x₁ + 2x₂ ®max

–x₁ + x₂ £1 x₁ + x₂ ³1

3x₁ + 2x₂ ³6 –5x₁ + x₂ £0

–3x₁ – x₂ ³–9 5x₁ – x₂ ³0

x₁³0, x₂ ³0 x₁ – x₂ ³–1

x₁– x₂ £4. x₁ + x₂ £6

x₁³0, x₂ ³0.

3. z = –x₁ + 4x₂ ®max 4. z = –x₁ + x₂ ®max

3x₁ + 2x₂ £12 –2x₁ + x₂ £2

2x₁ – x₂ £0 x₁ – 2x₂ £2

–3x₁ + 2x₂ £3 x₁ + x₂ £5

x₁ + 2x₂ £3 x₁ ³0, x₂ ³0.

x₁ ³0, x₂ ³0.

 

5. z = 3x₁ – x₂ ®min 6. z = –x₁ – 2x₂ ®max

2x₁ + 5x₂ – 10 £0 x₁ – x₂ £1

2x₁ + x₂ – 6 £0 x₁ + x₂ ³2

x₁ + 2x₂ – 2 ³0 x₁ – 2x₂ £0

x₁ ³0, x₂ ³0. x₁ ³0, x₂ ³0.

 

7. z = 2x₁ + x₂ ®max 8. z = 3x₁ + 4x₂ ®max

x₁ + x₂ £20 –1 £–x₁ + x₂ £1

0 £x₁ £10 x₁ + x₂ ³–1

0 £x₂ £30 –x₁ + x₂ £2

x₁ + x₂ ³10. 2x₁ – x₂ £2

x₁ ³0, x₂ ³0.

 

9. z = –2x₁ + 5x₂ ® min 10. z = –x₂ + x₁ ® min

7x₁ + 2x₂ ³ 14 x₁+ 3x₂ £12

5x₁ + 6x₂ £30 3x₁ – x₂ ³6

3x₁ + 8x₂ ³24 3x₁ + 12x₂ ³0

x₁ ³0, x₂ ³0. x₁ ³0, x₂ ³0.

 

 

11. z = 2x₁ – 3x₂ ®max 12. z = 3x₁ – 2x₂ ®min

4x₁ + 3x₂ ³ 12 7x₁ + 2x₂ ³ 14

3x₁ + 4x₂ £ 24 –x₁ + 2x₂ ³ 2

3x₁ + 8x₂ ³ 24 7x₁ + 7x₂ £ 28

x₁ ³ 0, x₂ ³ 0. x₁ ³ 0, x₂ ³ 0.

13. z = 6x₁ + x₂ ® min 14. z = x₁ + x₂ ® max

x₁ + x₂ ³ 3 2x₁ + 5x₂ ³ 10

x₁ – x₂ £ 3 –2x₁ + 3x₂ £ 12

–6x₁ + 4x₂ £ 12 2x₁ + 4x₂ £ 20

x₁ ³ 2, x₂ £ 8. x₁ ³ 0, x₂ ³ 0.

 

15. z = 3x₁ + x₂ ® max 16. z = 2x₁ + 4x₂ ® max

–2 £ x₁ + x₂ £ 2 –x₁ + x₂ £ 1

–2 £ –x₁ + x₂ £ 2 x₁ + x₂ ³ 2

0 £ x₁ £ 1 0 £ x₁ £ 10

0 £ x₂ £ 3 ¤ 2 . 0 £ x₂ £ 10.

 

17. z = 4x₁ + x₂ ® min 18. z = 2x₁ + x₂ + 4 ® min

x₁ + x₂ ³ 2 x₁ + x₂ ³ 4

x₁ – x₂ £ 2 8x₁ – 4x₂ ³ 16

4x₁ – 4x₂ ³ –8 x₁ ³ 2

x₁ ³ 1 0 £ x₂ £ 9.

0 £ x₂ £ 4.

 

19. z = –x₁ + 4x₂ ® max 20. z = 2x₁ + 3x₂ ® min

3x₁ + 2x₂ £ 12 x₁ + x₂ £ 4

2x₁ – x₂ £ 0 6x₁ + 2x₂ ³ 8

–3x₁ + 2x₂ £ 3 x₁ + 5x₂ ³ 4

x₁ + 2x₂ £ 3 0 £ x₂ £ 3

x₁ ³ 0, x₂ ³ 0. 0 £ x₁ £ 3.

 

21. z = 2x₁ + x₂ ® max 22. z = 2x₁ + x₂ ® max

–x₁ + x₂ £ 4 x₁ – 2x₂ £ 6

0 £ x₁ £ 4 x₁ + 3x₂ £ 8

0 £ x₂ £ 5 0 £ x₁ £ 4

–x₂ + x₁ £ 0. 0 £ x₂ £ 2.

 

23. z = –2x₁ + 5x₂ ® min 24. z = 5x₁ + x₂ ® max

7x₁ + 2x₂ £ 8 x₁ + x₂ ³ 2

5x₁ + 6x₂ £ 30 x₁ – x₂ £ 2

3x₁ + 8x₂ ³ 24 4x₁ + 8x₂ £ 16

x₁ ³ 0, x₂ ³ 0. x₁ ³ 1, 0 £ x₂ £ 3.

25. z = x₁ + 2x₂ ® min 26. z = x₁ + 2x₂ ® min

2x₁ + 4x₂ £ 8 2x₁ + 4x₂ £ 8

0 £ x₁ £ 2 –x₁ + 2x₂ £ 2

0 £ x₂ £ 1. x₁ ³ 0, x₂ ³ 0.

 

27. z = 8x₁ + 6x₂ ® max 28. z = 2x₁ + x₂ ® max

4x₁ + 3x₂ £ 12 –x₁ – 2x₂ ³ –4

7x₁ + 5x₂ £ 35 5x₁ + x₂ £ 40

0 £ x₁ £ 3 2x₁ – 2x₂ £ 7

0 £ x₂ £ 19 ¤ 3. x₁ + x₂ £ 4

x₁ ³ 0, x₂ ³ 0.

 

29. z = 2x₁ – 3x₂ ® min 30. z = 3x₁ + x₂ ® max

–4x₁ + 5x₂ £ 20 10x₁ + 7x₂ £ 70

2x₁ + x₂ ³ 6 8x₁ + 10x₂ £ 80

5x₁ – 2x₂ £ 20 x₁ ³ 0, x₂ ³ 0.

x₁ – x₂ £ 6

x₁ ³ 0, x₂ ³ 0.

 

СИМПЛЕКСНЫЙ МЕТОД РЕШЕНИЯ ЗАДАЧ

ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Постановка задачи линейного программирования, решаемой

Симплексным методом

  В зависимости от вида ограничений различают две формы общей модели ЗЛП:… ЗЛП называется канонической, если ограничения представлены в виде равенств:

Таблица 1

Базисные переменные	Свободные члены	Свободные переменные	Симплексные отношения
x1	x2	…	xn
xn+1	b1	a11	a12	…	a1n
xn+2	b2	a21	a22	…	a2n
…	…	…	…	…	…
xn+m	bm	am1	am2	…	amn
Оценочная строка	z0	–с1	–с2	…	–сn

 

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

 

Алгоритм симплекс-метода

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

Типовой пример

Пусть дана следующая содержательная постановка задачи.

 

Для изготовления трех видов изделий, которые обозначим А, В, С, используется три вида ресурсов; их обозначим I, II, III. Затраты ресурсов каждого вида на производство одного изделия видов А, В, С в относительных единицах, объем имеющихся ресурсов каждого вида, а также прибыль от реализации единицы готового изделия всех видов в денежных единицах (ден. ед.) представлены в таблице 2.

 

Таблица 2

Виды ресурсов	Затраты по видам ресурсов на единицу продукции	Объемы имеющихся ресурсов
А	В	С
I
II
III
Прибыль от реализации				–

 

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

Задачу решить симплексным методом.

Решение.

Учитывая количество ресурсов, затрачиваемых на изготовление единицы продукции, а также их наличие, составим систему ограничений: 2x1 + 4x2 + 3x3 £ 48, 4x1 + 2x2 + 3x3 £ 60,

Таблица 4

Базисные переменные	Свободные члены	Свободные переменные	Симплексные отношения
x6	x2	x3
x4		–2/3		7/3
x5		–4/3		5/3
x1		1/3		1/3	–
Оценочная строка			–4	–1	–

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

.

Остальные элементы новой симплексной таблицы 4 вычислим по правилу прямоугольника:

Применяя описанный выше алгоритм, построим новую симплексную таблицу (таблица 5).

Таблица 5

Базисные переменные	Свободные члены	Свободные переменные	Симплексные отношения
x6	x4	x3
x2		1/6	1/4	7/12
x5		–1	–1/2	1/2
x1		1/3		1/3
Оценочная строка		4/3		4/3

 

В оценочной строке новой таблицы нет отрицательных элементов. Это означает, что соответствующее базисное решение x₂ = 6; x₅ = 0; x₁ = 12; x₆ = 0; x₄ = 0; x₃ = 0 является оптимальным.

Соответствующее значение целевой функции z_max = 96.

Таким образом, необходимо производить 12 изделий вида А, 6 изделий вида В; изделия вида С производить нецелесообразно. При этом максимальная прибыль от реализации продукции составит 96 ден. ед.

 

2.4. Индивидуальное задание №2

Пусть дана следующая содержательная постановка задачи.

Для производства двух видов изделий (обозначим их буквами А и В), используется три вида технологического оборудования (обозначим их цифрами I, II, III). Использование оборудования на производство единицы продукции видов А и В (в часах), общий резерв использования оборудования (в часах), а также прибыль от реализации готового изделия видов А и В (в ден. ед.) представлены в таблице.

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

Задачу решить симплекс-методом.

 

Вариант 1.

Тип оборудования	Затраты времени работы оборудования на единицу продукции	Резерв использования оборудования
А	В
I
II
III
Прибыль от реализации			–

 

Вариант 2.

Тип оборудования	Затраты времени работы оборудования на единицу продукции	Резерв использования оборудования
А	В
I
II
III		8,4	204,6
Прибыль от реализации			–

 

Вариант 3.

Тип оборудования	Затраты времени работы оборудования на единицу продукции	Резерв использования оборудования
А	В
I
II
III
Прибыль от реализации			–

 

Вариант 4.

Тип оборудования	Затраты времени работы оборудования на единицу продукции	Резерв использования оборудования
А	В
I
II
III
Прибыль от реализации			–

 

Вариант 5.

Тип оборудования	Затраты времени работы оборудования на единицу продукции	Резерв использования оборудования
А	В	С
I
II
III	–
Прибыль от реализации				–

Вариант 6.

Тип оборудования	Затраты времени работы оборудования на единицу продукции	Резерв использования оборудования
А	В
I
II
III
Прибыль от реализации			–

Вариант 7.

Тип оборудования	Затраты времени работы оборудования на единицу продукции	Резерв использования оборудования
А	В
I
II
III
Прибыль от реализации			–

Вариант 8.

Тип оборудования	Затраты времени работы оборудования на единицу продукции	Резерв использования оборудования
А	В
I
II
III
Прибыль от реализации			–

Вариант 9.

Тип оборудования	Затраты времени работы оборудования на единицу продукции	Резерв использования оборудования
А	В	С
I
II
III
Прибыль от реализации				–

 

 

Вариант 10.

Тип оборудования	Затраты времени работы оборудования на единицу продукции	Резерв использования оборудования
А	В
I
II
III
Прибыль от реализации			–

Вариант 11.

Тип оборудования	Затраты времени работы оборудования на единицу продукции	Резерв использования оборудования
А	В
I	0,7	0,1	5,4
II	0,5	1,0	6,0
III	–	0,5	3,0
IV	1,5	1,5	12,0
V	2,0	–	12,0
Прибыль от реализации	7,0	5,0	–

Вариант 12.

Тип оборудования	Затраты времени работы оборудования на единицу продукции	Резерв использования оборудования
А	В
I
II
III
Прибыль от реализации			–

Вариант 13.

Тип оборудования	Затраты времени работы оборудования на единицу продукции	Резерв использования оборудования
А	В
I
II
III
Прибыль от реализации			–

Вариант 14.

Тип оборудования	Затраты времени работы оборудования на единицу продукции	Резерв использования оборудования
А	В
I
II
III
Прибыль от реализации			–

Вариант 15.

Тип оборудования	Затраты времени работы оборудования на единицу продукции	Резерв использования оборудования
А	В
I
II
III
Прибыль от реализации			–

Вариант 16.

Тип оборудования	Затраты времени работы оборудования на единицу продукции	Резерв использования оборудования
А	В
I
II
III
Прибыль от реализации			–

Вариант 17.

Тип оборудования	Затраты времени работы оборудования на единицу продукции	Резерв использования оборудования
А	В
I
II
III
Прибыль от реализации			–

Вариант 18.

Тип оборудования	Затраты времени работы оборудования на единицу продукции	Резерв использования оборудования
А	В
I
II
III
Прибыль от реализации			–

Вариант 19.

Тип оборудования	Затраты времени работы оборудования на единицу продукции	Резерв использования оборудования
А	В
I
II
III
Прибыль от реализации			–

 

 

Вариант 20.

Тип оборудования	Затраты времени работы оборудования на единицу продукции	Резерв использования оборудования
А	В
I
II
III
Прибыль от реализации			–

Вариант 21.

Тип оборудования	Затраты времени работы оборудования на единицу продукции	Резерв использования оборудования
А	В
I
II
III
Прибыль от реализации			–

Вариант 22.

Тип оборудования	Затраты времени работы оборудования на единицу продукции	Резерв использования оборудования
А	В
I
II
III
Прибыль от реализации			–

Вариант 23.

Тип оборудования	Затраты времени работы оборудования на единицу продукции	Резерв использования оборудования
А	В
I
II
III	0,5	–	6,5
IV	–
Прибыль от реализации			–

Вариант 24.

Тип оборудования	Затраты времени работы оборудования на единицу продукции	Резерв использования оборудования
А	В
I	1,5	4,2	102,3
II	1,2	1,6	48,4
III	2,6	1,8	78,2
Прибыль от реализации			–

 

Вариант 25.

Тип оборудования	Затраты времени работы оборудования на единицу продукции	Резерв использования оборудования
А	В
I
II
III
Прибыль от реализации			–

Вариант 26.

Тип оборудования	Затраты времени работы оборудования на единицу продукции	Резерв использования оборудования
А	В
I
II
III
Прибыль от реализации			–

Вариант 27.

Тип оборудования	Затраты времени работы оборудования на единицу продукции	Резерв использования оборудования
А	В
I
II
III	0,5	–	6,5
IV	–
Прибыль от реализации			–

Вариант 28.

Тип оборудования	Затраты времени работы оборудования на единицу продукции	Резерв использования оборудования
А	В
I
II
III
Прибыль от реализации			–

Вариант 29.

Тип оборудования	Затраты времени работы оборудования на единицу продукции	Резерв использования оборудования
А	В
I
II
III	–
IV		–
Прибыль от реализации			–

Вариант 30.

Тип оборудования	Затраты времени работы оборудования на единицу продукции	Резерв использования оборудования
А	В
I
II
III
Прибыль от реализации			–

ПРИМЕНЕНИЕ МЕТОДА ИСКУССТВЕННОГО БАЗИСА ДЛЯ РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

(М-ЗАДАЧА)

 

Постановка и методика решения М-задачи

Он состоит в следующем. В рассмотрение вводится т искусственных переменных xn+1, xn+2, … , xn+m и решается расширенная задача (М-задача). Она… z = c1x1 + c2x2 + … + cnxn + Mxn+1 + Mxn+2 + … + Mxn+m при условиях

Типовой пример

 

Дана следующая содержательная постановка задачи.

 

Цех выпускает два вида продукции (обозначим их А и В). Производственное оборудование цеха состоит из трех видов (обозначим их I, II, III). Использование оборудования различных видов на производство единицы продукции видов А и В (в часах), а также общий резерв использования оборудования (в часах) представлены в таблице 2.

 

Таблица 2

Станки	Затраты времени работы оборудования	Резерв использования оборудования
А	В
I	0,4	0,8
II	0,8	0,4
III	0,2	0,24

 

Прибыль от реализации единицы готовой продукции А составляет 3 ден. ед., а продукции В – 6 ден. ед.

Продукции вида А должно быть произведено не менее 200 единиц, вида В – не менее 100 единиц. Составить план производства продукции видов А и В, обеспечивающий максимальную прибыль.

Задачу решить модифицированным симплекс-методом.

Решение.

Составим математическую модель задачи.

Пусть х₁, х₂ – количество продукции видов А и В соответственно.

Сформулируем условия задачи.

1. Ограничения по затратам времени работы оборудования различных видов:

0,4 х₁ + 0,8х₂ ≤ 320;

0,8 х₁ + 0,4х₂ ≤ 320;

0,2 х₁ + 0,24х₂ ≤ 120.

2. Ограничения по выпуску продукции:

х₁ ≥ 200; х₂ ≥ 100.

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

z = 3x₁ + 6x₂ → max.

Запишем условия задачи в каноническом виде с помощью дополнительных переменных x₃, x₄, x₅, x₆ x₇:

z = 3x₁ + 6x₂ + 0x₃ + 0x₄ + 0x₅ + 0x₆ + 0x₇ → max

В данной системе уравнений дополнительные переменные х₆ и х₇ имеют коэффициент «–1», поэтому построить первоначальную симплексную таблицу обычным способом невозможно. Для такого построения в четвертое и пятое уравнения введем искусственные переменные у₁ и у₂ с коэффициентами «+1».

В целевую функцию искусственные переменные у₁ и у₂ введем с очень большими по абсолютной величине отрицательными коэффициентами –М.

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

z = 3x₁ + 6x₂ + 0x₃ + 0x₄ + 0x₅ + 0x₆ + 0x₇ – My₁ – My₂ → max

0,4 х₁ + 0,8х₂ + х₃ = 320;

0,8 х₁ + 0,4х₂ + х₄ = 320;

0,2 х₁ + 0,24х₂ + х₅ = 120;

х₁ – х₆ + у₁ = 200;

х₂ – х₇ + у₂ = 100.

Рассматривая переменные х₃, х₄, х₅, у₁ и у₂ в качестве базисных, приравняем нулю остальные (свободные) переменные и получим первоначальное опорное решение:

х₃ = 320; х₄ = 320; х₅ = 120; у₁ = 200; у₂ = 100.

Оформим его в виде симплексной таблицы (таблица 3).

Таблица 3

Базисные переменные	Свободные члены	Свободные переменные	Симплексные отношения
х1	х2	х6	x7
х3		0,4	0,8
х4		0,8	0,4
х5		0,2	0,24
y1				–1
y2					–1	–
Оценочная строка (m+1)-я		–3	–6			–
(m+2)-я строка	–300	–1	–1			–

 

В (m+2)-й оценочной строке стоят суммы коэффициентов при свободных переменных в четвертой и пятой строках (эти строки соответствуют искусственным переменным y₁ и y₂), взятые с отрицательными знаками.

Поскольку задача решается на максимум, то критерием оптимальности является отсутствие отрицательных величин в (m+2)-й строке. В данном случае (m+2)-й строке есть отрицательные оценки, поэтому опорный план не является оптимальным и может быть улучшен.

Столбец, содержащий переменную x₁, выбирем разрешающим, так как он содержит отрицательную оценку «–1» в (m+2)-й строке.

Разрешающую строку определим по минимальному симплексному отношению. Разрешающей будет строка, содержащая переменную y₁, которой соответствует минимальное симплексное отношение 200.

Разрешающий элемент, стоящий на пересечении разрешающей строки и разрешающего столбца, равен 1.

В новой симплексной таблице переменная y₁ переходит в число свободных переменных и далее не учитывается. При этом соответствующий столбец исключается из таблицы. Переменная x₁ переходит в число базисных. Обычным способом осуществляем переход к новой симплексной таблице (таблица 4).

 

 

Таблица 4

Базисные переменные	Свободные члены	Свободные переменные	Симплексные отношения
х2	х6	x7
х3		0,8	0,4
х4		0,4	0,8
х5		0,24	0,2		333,(3)
x1			–1		–
y2				–1
Оценочная строка (m+1)-я		–6	–3		–
(m+2)-я строка	–100	–1			–

 

В (m+2)-й строке есть отрицательная оценка «–1», поэтому опорный план не является оптимальным и может быть улучшен. При этом разрешающим столбцом является столбец, содержащий переменную x₂, разрешающей строкой является строка, содержащая переменную y₂, разрешающий элемент равен 1.

Рассчитываем новую симплексную таблицу (таблица 5). В ней переменная x₂ перейдет в число базисных, а y₂ – в число свободных и записываться не будет. Так как искусственные переменные будут исключены из таблицы, то (m+2)-я строка будет содержать только нули и в таблицу не заносится.

 

Таблица 5

Базисные переменные	Свободные члены	Свободные переменные	Симплексные отношения
x6	x7
х3		0,4	0,8
х4		0,8	0,4
х5		0,2	0,24	233,(3)
x1		–1		–
x2			–1	–
Оценочная строка (m+1)-я		–3	–6	–

 

Таблица 5 – обычная симплексная таблица. Так как в оценочной строке есть отрицательные оценки, то опорный план не является оптимальным. Осуществляя один шаг последовательного улучшения опорного плана симплекс-методом, получим таблицу 6.

Таблица 6

Базисные переменные	Свободные члены	Свободные переменные	Симплексные отношения
x6	x3
y2		0,5	1,25
х4		0,6	–0,5
х5		0,08	–0,3
x1		–1
x2		0,5	1,25
Оценочная строка (m+1)-я			7,5

В оценочной строке таблицы 6 нет отрицательных элементов. Это означает, что соответствующее базисное решение x₁ = 200; x₂ = 300; x₃ = 0; x₄ = 40; x₅ = 8; x₆ = 0; x₇ = 200 является оптимальным. Соответствующее значение целевой функции z_max = 2400.

 

3.3. Индивидуальное задание №3

Необходимо организовать производство продукции видов А и В, обеспечивающее максимальную прибыль. Продукции вида А должно быть произведено не менее d₁ единиц, вида В – не менее d₂ единиц. Затраты ресурсов на производство единицы продукции каждого вида, объем имеющихся ресурсов, а также прибыль от реализации единицы готовой продукции каждого вида приведены в таблице.

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

При решении следует использовать модифицированный симплекс-метод.

 

Вариант 1.

Производственные ресурсы	Виды продукции	Объем ресурсов
А	В
Исходное сырье, кг
Затраты труда, чел.-дней	0,03	0,03	2,31
Затраты труда машин, машино-дней	0,05	0,04	3,52
Прибыль от реализации, ден. ед.			d1 = 10 d2 = 12

 

Вариант2.

Производственные ресурсы	Виды продукции	Объем ресурсов
А	В
Исходное сырье, кг
Затраты труда, чел.-дней	0,1	0,08	7,04
Затраты труда машин, машино-дней	0,01	0,02	1,32
Прибыль от реализации, ден. ед.			d1 = 12 d2 = 13

 

Вариант 3.

Производственные ресурсы	Виды продукции	Объем ресурсов
А	В
Исходное сырье, кг
Затраты труда, чел.-дней	0,3	0,3	26,4
Затраты труда машин, машино-дней	0,5	0,6
Прибыль от реализации, ден. ед.			d1 = 5 d2 = 20

Вариант 4.

Производственные ресурсы	Виды продукции	Объем ресурсов
А	В
Исходное сырье, кг
Затраты труда, чел.-дней	0,05	0,06	2,95
Затраты труда машин, машино-дней	0,1	0,02	1,9
Прибыль от реализации, ден. ед.			d1 = 2 d2 = 15

Вариант 5.

Производственные ресурсы	Виды продукции	Объем ресурсов
А	В
Исходное сырье, кг
Затраты труда, чел.-дней	0,06	0,08	2,42
Затраты труда машин, машино-дней	0,3	0,84	20,46
Прибыль от реализации, ден. ед.			d1 = 6 d2 = 8

Вариант 6.

Производственные ресурсы	Виды продукции	Объем ресурсов
А	В
Исходное сырье, кг
Затраты труда, чел.-дней	0,01	0,02	0,9
Затраты труда машин, машино-дней	0,02	0,01	0,75
Прибыль от реализации, ден.ед.			d1 = 12 d2 = 8

Вариант 7.

Производственные ресурсы	Виды продукции	Объем ресурсов
А	В
Исходное сырье, кг
Затраты труда, чел.-дней	0,2	0,8
Затраты труда машин, машино-дней	0,4	0,2
Прибыль от реализации, ден. ед.			d1 = 12 d2 = 20

Вариант 8.

Производственные ресурсы	Виды продукции	Объем ресурсов
А	В
Исходное сырье, кг	2,5		147,5
Затраты труда, чел.-дней	0,05	0,02	1,15
Затраты труда машин, машино-дней	0,15	0,03	2,85
Прибыль от реализации, ден. ед.			d1 = 3 d2 = 8

 

Вариант 9.

Производственные ресурсы	Виды продукции	Объем ресурсов
А	В
Исходное сырье, кг
Затраты труда, чел.-дней	0,8	0,4
Затраты труда машин, машино-дней	0,2	0,5
Прибыль от реализации, ден. ед.			d1 = 10 d2 = 20

Вариант 10.

Производственные ресурсы	Виды продукции	Объем ресурсов
А	В
Исходное сырье, кг
Затраты труда, чел.-дней	0,06	0,04	2,62
Затраты труда машин, машино-дней	0,05	0,04	2,25
Прибыль от реализации, ден. ед.			d1 = 12 d2 = 6

Вариант 11.

Производственные ресурсы	Виды продукции	Объем ресурсов
А	В
Исходное сырье, кг
Затраты труда, чел.-дней	0,6	0,8	24,8
Затраты труда машин, машино-дней
Прибыль от реализации, ден. ед.			d1 = 9 d2 = 3

Вариант 12.

Производственные ресурсы	Виды продукции	Объем ресурсов
А	В
Исходное сырье, кг
Затраты труда, чел.-дней	0,12	0,06	2,76
Затраты труда машин, машино-дней	0,15	0,05	3,2
Прибыль от реализации, ден. ед.			d1 = 6 d2 = 8

Вариант 13.

Производственные ресурсы	Виды продукции	Объем ресурсов
А	В
Исходное сырье, кг
Затраты труда, чел.-дней	0,03	0,04	1,24
Затраты труда машин, машино-дней	0,03	0,01	0,64
Прибыль от реализации, ден. ед.			d1 = 4 d2 = 6

 

Вариант 14.

Производственные ресурсы	Виды продукции	Объем ресурсов
А	В
Исходное сырье, кг
Затраты труда, чел.-дней	0,6	0,3	13,8
Затраты труда машин, машино-дней	0,6	0,2	12,8
Прибыль от реализации, ден. ед.			d1 = 5 d2 = 8

Вариант 15.

Производственные ресурсы	Виды продукции	Объем ресурсов
А	В
Исходное сырье, кг
Затраты труда, чел.-дней	0,02	0,04	0,54
Затраты труда машин, машино-дней	0,06	0,02	0,74
Прибыль от реализации, ден. ед.			d1 = 1 d2 = 2

Вариант 16.

Производственные ресурсы	Виды продукции	Объем ресурсов
А	В
Исходное сырье, кг
Затраты труда, чел.-дней	0,02	0,03	1,32
Затраты труда машин, машино-дней	0,06	0,02	1,44
Прибыль от реализации, ден. ед.			d1 = 10 d2 = 5

Вариант 17.

Производственные ресурсы	Виды продукции	Объем ресурсов
А	В
Исходное сырье, кг
Затраты труда, чел.-дней	0,4	0,4	15,6
Затраты труда машин, машино-дней	1,1	0,2	15,9
Прибыль от реализации, ден. ед.			d1 = 2 d2 = 12

Вариант 18.

Производственные ресурсы	Виды продукции	Объем ресурсов
А	В
Исходное сырье, кг
Затраты труда, чел.-дней	0,3	0,6	26,1
Затраты труда машин, машино-дней	0,3	0,2	13,1
Прибыль от реализации, ден. ед.			d1 = 7 d2 = 6

 

Вариант 19.

Производственные ресурсы	Виды продукции	Объем ресурсов
А	В
Исходное сырье, кг
Затраты труда, чел.-дней	0,06	0,03	4,08
Затраты труда машин, машино-дней	0,02	0,05	4,2
Прибыль от реализации, ден. ед.			d1 = 12 d2 = 30

Вариант 20.

Производственные ресурсы	Виды продукции	Объем ресурсов
А	В
Исходное сырье, кг
Затраты труда, чел.-дней	0,3	0,4	36,4
Затраты труда машин, машино-дней	0,4
Прибыль от реализации, ден. ед.			d1 = 10 d2 = 20

Вариант 21.

Производственные ресурсы	Виды продукции	Объем ресурсов
А	В
Исходное сырье, кг
Затраты труда, чел.-дней	0,6	1,2	52,2
Затраты труда машин, машино-дней	1,2	0,8	52,4
Прибыль от реализации, ден. ед.			d1 = 11 d2 = 9

Вариант 22.

Производственные ресурсы	Виды продукции	Объем ресурсов
А	В
Исходное сырье, кг
Затраты труда, чел.-дней	0,4	0,2	12,4
Затраты труда машин, машино-дней	0,6	0,1
Прибыль от реализации, ден. ед.			d1 = 10 d2 = 5

Вариант 23.

Производственные ресурсы	Виды продукции	Объем ресурсов
А	В
Исходное сырье, кг
Затраты труда, чел.-дней	0,06	0,02	3,84
Затраты труда машин, машино-дней	0,06	0,02	2,76
Прибыль от реализации, ден. ед.			d1 = 5 d2 = 30

 

Вариант 24.

Производственные ресурсы	Виды продукции	Объем ресурсов
А	В
Исходное сырье, кг
Затраты труда, чел.-дней	0,09	1,1	82,5
Затраты труда машин, машино-дней	0,5	0,2	19,8
Прибыль от реализации, ден. ед.			d1 = 4 d2 = 25

Вариант 25.

Производственные ресурсы	Виды продукции	Объем ресурсов
А	В
Исходное сырье, кг
Затраты труда, чел.-дней	0,7	0,3	36,4
Затраты труда машин, машино-дней	0,7	0,1
Прибыль от реализации, ден. ед.			d1 = 15 d2 = 25

Вариант 26.

Производственные ресурсы	Виды продукции	Объем ресурсов
А	В
Исходное сырье, кг
Затраты труда, чел.-дней	0,5	0,4
Затраты труда машин, машино-дней	1,4	0,2
Прибыль от реализации, ден. ед.			d1 = 10 d2 = 20

Вариант 27.

Производственные ресурсы	Виды продукции	Объем ресурсов
А	В
Исходное сырье, кг	1,2	1,6	48,4
Затраты труда, чел.-дней	0,15	0,42	10,23
Затраты труда машин, машино-дней	0,26	0,18	7,82
Прибыль от реализации, ден. ед.			d1 = 4 d2 = 8

Вариант 28.

Производственные ресурсы	Виды продукции	Объем ресурсов
А	В
Исходное сырье, кг
Затраты труда, чел.-дней	1,6	0,9	72,9
Затраты труда машин, машино-дней	0,5	0,4	24,8
Прибыль от реализации, ден. ед.			d1 = 9 d2 = 10

 

Вариант 29.

Производственные ресурсы	Виды продукции	Объем ресурсов
А	В
Исходное сырье, кг
Затраты труда, чел.-дней	0,02	0,1	6,2
Затраты труда машин, машино-дней	0,03	0,04	2,8
Прибыль от реализации, ден. ед.			d1 = 3 d2 = 20

Вариант 30.

Производственные ресурсы	Виды продукции	Объем ресурсов
А	В
Исходное сырье, кг
Затраты труда, чел.-дней	0,6	0,3	13,8
Затраты труда машин, машино-дней	0,6	0,2	12,8
Прибыль от реализации, ден. ед.			d1 = 7 d2 = 5

 

ЗАКРЫТАЯ МОДЕЛЬ ТРАНСПОРТНОЙ (РАСПРЕДЕЛИТЕЛЬНОЙ) ЗАДАЧИ

 

Формализация распределительной задачи

Транспортной (распределительной) задачей называется задача определения оптимального плана перевозок груза из заданных пунктов отправления в заданные… Имеется m поставщиков А1, А2, … , Аm с запасами груза соответственно a1, a2,… b1, b2, …, bn. Стоимость перевозки единицы груза от i-го поставщика к j-му потребителю составляет сij. Необходимо…

Таблица 1

Потреби-тели Постав-щики	В1	В2	…	Вn	Запасы
А1	с11 х11	с12 х12	…	с1n х1n	a1
А2	с21 х21	с22 х22	…	с2n х2n	a2
…	…	…	…	…	…
Аm	сm1 хm1	сm2 хm2	…	сmn хmn	am
Потребности	b1	b2	…	bn	Σai = Σbj

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

Обозначим x_ij – количество единиц груза, запланированных к перевозке от i-го поставщика к j-му потребителю.

Поскольку от i-го поставщика к j-му потребителю запланировано перевезти х_ij единиц груза, стоимость данной перевозки составит с_ijх_ij. Стоимость всего плана выразится двойной суммой :

.

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

1) Все запасы должны быть вывезены:

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

2) Все потребности должны быть удовлетворены:

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

3) Обратные перевозки не имеют смысла:

x_ij ³ 0 (i = 1, 2,…, m; j = 1, 2,…, n).

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

 

Введем следующую терминологию.

Количество единиц груза, направляемого от i-го поставщика к j-му потребителю, называется перевозкойx_ij.

Совокупность значений X = {x_ij, i = 1,…, m, j = 1,…, n} называется планом перевозок.

Допустимый план X называется опорным, если в нем отличны от нуля не более чем r = m + n – 1 элементов, а остальные элементы равны нулю.

Опорный план называется оптимальным, если он минимизирует или максимизирует заданную целевую функцию.

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

Тарифом называется стоимость перевозки единицы груза от i-го поставщика к j-му потребителю.

План транспортной задачи, содержащий не менее m+n–1 ненулевых компонент, называют невырожденным.

Для построения первоначального опорного плана, содержащего не более m+n–1 ненулевых компонентов, можно использовать метод «северо-западного угла» и метод наилучшего элемента.

Методы построения опорного плана

Метод северо-западного угла

Если a1 > b1, то x11 = b1 и первый столбец закрывается для заполнения его клеток: x21 = … = xm1 = 0. Следующей заполняется клетка (1; 2). При этом x12 = min {a1 – b1; b2}.

Метод наилучшего элемента

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

Решение транспортной задачи методом потенциалов

Потенциалами называются числа uí и vj, удовлетворяющие следующим условиям оптимальности плана перевозок. 1) Для всех занятых клеток (xij > 0) должно выполняться равенство vj – ui = cij.

Алгоритм последовательного улучшения опорного

Плана перевозок

  1. Осуществляется выбор перспективной клетки с наибольшей по модулю… – перспективная клетка.

Типовой пример

Дана следующая содержательная постановка задачи.

 

С четырех складов необходимо организовать перевозку груза на три строительных участка. Общее количество груза на складах (в тоннах), потребности участков (в тоннах), а также стоимость перевозки одной тонны груза от каждого склада к каждому участку (в ден. ед.) представлены в таблице2.

Таблица 2

Склады	Участки	Наличие на складах
1-й	2-й	3-й
I-й	40	70	20
II-й	10	20	30
III-й	20	40	10
IV-й	30	20	50
Потребности участков

 

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

При решении использовать метод потенциалов.

Решение.

Составим математическую модель задачи.

Обозначим x_ij – количество груза, перевозимое из i-го склада на j-й строительный участок, i = 1, 2, 3, 4; j = 1, 2, 3 (таблица 3).

Таблица 3

Склады	Участки	Наличие на складах
1-й	2-й	3-й
I-й	x11 40	x12 70	x13 20
II-й	x21 10	x22 20	x23 30
III-й	x31 20	x32 40	x33 10
IV-й	x41 30	x42 20	x43 50
Потребности участков

Составим ограничивающие условия:

1. С каждого склада должен быть вывезен весь груз:

x₁₁ + x₁₂ + x₁₃ = 8000;

x₂₁ + x₂₂ + x₂₃ = 5000;

x₃₁ + x₃₂ + x₃₃ = 10000;

x₄₁ + x₄₂ + x₄₃ = 7000.

2. Потребности всех строительных участков должны быть удовлетворены:

x₁₁ + x₂₁ + x₃₁ + x₄₁ = 12000;

x₁₂ + x₂₂ + x₃₂ + x₄₂= 9000;

x₁₃ + x₂₃ + x₃₃ + x₄₃= 9000.

3. Обратные перевозки невозможны:

x_ij ³ 0, i = 1, 2, 3, 4; j = 1, 2, 3.

Общие транспортные расходы выразятся двойной суммой произведений тарифов на общее количество перевозимого груза:

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

Составим первоначальный опорный план методом наилучшего элемента.

В таблице определяем клетку с минимальной стоимостью. Таких клеток две: (2; 1) и (3; 3) (минимальная стоимость перевозки c₂₁ = c₃₃ = 10).

Построение первоначального плана выгоднее начать с заполнения клетки (3; 3), поскольку в нее можно вписать больший объем перевозок 9000 т, чем в клетку (2; 1), где максимально возможный объем перевозок составит 5000 т. Записываем x₃₃ = 9000 т (min {9000; 10000}). Потребности третьего участка полностью удовлетворены, поэтому прочеркиваем оставшиеся клетки третьего столбца. На третьем складе осталось 10000 – 9000 = 1000 т.

В таблице снова выбираем клетку с минимальной стоимостью – клетку (2; 1) и записываем величину x₂₁ = min {12000; 5000} = 5000. Возможности второго склада полностью исчерпаны, поэтому прочеркиваем вторую строку. Первому участку необходимо допоставить 12000 – 5000 = 7000 т.

В оставшейся таблице снова выбираем клетку с минимальной стоимостью, в которую можно вписать больший объем перевозок: (4; 2),

x₄₂ = min {9000; 7000} = 7000. Возможности четвертого склада исчерпаны – прочеркиваем клетку (4; 1). Второму участку необходимо допоставить 9000 – 7000 = 2000 т.

Наименьшую стоимость перевозки содержит клетка (3; 1). Поэтому

x₃₁ = min {7000; 1000} = 1000 т. Возможности третьего склада исчерпаны – прочеркиваем клетку (3; 2). Первому участку необходимо допоставить 7000 – 1000 = 6000 т. Далее заполняем клетку (1; 1): x₁₁ = min {6000; 8000} = 6000 т. На первом складе осталось 8000 – 6000 = 2000 т. И, наконец, в оставшуюся клетку (1; 2) вписываем величину x₁₂ = 2000.

Построение первоначального опорного плана показано в таблице 4.

 

Таблица 4

Склады	Участки	Наличие на складах
1-й	2-й	3-й
I-й	6000 40	2000 70	– 20
II-й	5000 10	– 20	– 30
III-й	1000 20	– 40	9000 10
IV-й	– 30	7000 20	– 50
Потребности участков

 

Число занятых клеток r = m + n – 1 = 4 + 3 – 1 = 6. Следовательно, полученный опорный план является невырожденным и транспортная задача имеет решение.

Для проверки плана на оптимальность вычислим потенциалы строк u_i и столбцов v_j.

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

Таблица 5

Участки Склады	1 – й	2 –й	3 –й	Наличие на складах
v1 = 40	v2 = 70	v3 = 30
I–й	u1 = 0	6000 40	2000 70	– 20
II-й	u2 = 30	5000 10	– 20	– 30
III-й	u3 = 20	1000 20	– 40	9000 10
IV-й	u4 = 50	– 30	7000 20	– 50
Потребности участков

 

Построим систему потенциалов, используя условие v_j – u_i = c_ij для каждой занятой клетки:

v₁ – u₁ = 40;

v₁ – u₂ = 10;

v₁ – u₃ = 20;

v₂ – u₁ = 70;

v₂ – u₄ = 20;

v₃ – u₃ = 10.

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

Учитывая, что u₁ = 0, найдем значение потенциала первого столбца:

v₁ = c₁₁ + u₁ = 40 + 0 = 40.

Аналогично определяем значение потенциала второго столбца:

v₂ = c₁₂ + u₁ = 70 + 0 = 70.

Используя найденное значение потенциала v₁ и известную величину c₂₁, определяем u₂:

u₂ = v₁ – c₂₁ = 40 – 10 = 30.

Таким же образом вычисляем значение потенциала третьей строки u₂:

u₃ = v₁ – c₃₁ = 40 – 20 = 20.

Потенциал третьего столбца v₃ определяем по известным значениям

u₃ = 20 и c₃₃ = 10:

v₃ = c₃₃ + u₃ = 10 + 20 = 30.

Потенциал четвертой строки u₄ найдем, используя значения v₂ = 70 и

c₄₂ = 20:

u₄ = v₂ – c₄₂ = 70 – 20 = 50.

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

Для проверки опорного плана на оптимальность вычислим оценки свободных клеток w_ij по формуле: w_ij = c_ij – (v_j – u_i).

w₁₃ = c₁₃ – (v₃ – u₁) = 20 – (30 – 0) = –10;

w₂₂ = c₂₂ – (v₂ – u₂) = 20 – (70 – 30) = –20;

w₂₃ = c₂₃ – (v₃ – u₂) = 30 – (30 – 30) = 30;

w₃₂ = c₃₂ – (v₂ – u₃) = 40 – (70 – 20) = –10;

w₄₁ = c₄₁ – (v₁ – u₄) = 30 – (40 – 50) = 40;

w₄₃ = c₄₃ – (v₃ – u₄) = 50 – (30 – 50) = 70.

Оценки w₁₃, w₂₂, w₃₂ оказались отрицательными. Следовательно, полученный опорный план не является оптимальным и может быть улучшен за счет перераспределения грузов из занятых клеток.

Определяем наибольшую по абсолютной величине отрицательную оценку:

min {w₁₃ = –10, w₂₂ = –20, w₃₂ = –10} = w₂₂.

Индексы такой оценки определяют перспективную клетку (2; 2)*, которую необходимо ввести в план.

Строим цикл, выбирая клетку (2; 2) в качестве исходной вершины. Двигаясь по этой строке до занятой клетки (2; 1), поворачиваем на 90° вверх и продолжаем двигаться вдоль первого столбца до занятой клетки (1; 1). Снова делаем поворот на 90° и переходим к клетке (1; 2). Затем, повернув на 90°, возвращаемся к исходной клетке (2; 2).

Таким образом, получили цикл (2; 2) * – (2; 1) – (1; 1) – (1; 2).

Присваиваем вершинам цикла чередующиеся знаки, начиная с перспективной клетки, которой присваиваем знак «+».

Среди клеток с отрицательными вершинами определяем величину α как минимальный объем груза:

α = min {2000; 5000} = 2000 т.

На эту величину производим перераспределение:

x₁₂ = 2000 – 2000 = 0;

x₂₂ = 0 + 2000 = 2000;

x₂₁ = 5000 – 2000 = 3000;

x₁₁ = 6000 + 2000 = 8000.

Получаем новый план перевозок.

Целевая функция для нового плана составит:

z = 40∙8000 + 10∙3000 + 20∙2000 + 20∙1000 + 10∙9000 + 20∙7000 = 640000 (ден. ед.).

Составляем следующую распределительную таблицу (таблица 6).

Таблица 6

Участки Склады	1 – й	2 –й	3 –й	Наличие на складах
v1 = 40	v2 = 50	v3 = 30
I–й	u1 = 0	8000 40	– 70	– 20
II-й	u2 = 30	3000 10	2000 20	– 30
III-й	u3 = 20	1000 20	– 40	9000 10
IV-й	u4 = 30	– 30	7000 20	– 50
Потребности участков

 

Вычисляем потенциалы строк и столбцов из системы уравнений для занятых клеток:

v₁ – u₁ = 40;

v₁ – u₂ = 10;

v₂ – u₂ = 20;

v₁ – u₃ = 20;

v₃ – u₃ = 10;

v₂ – u₄ = 20.

Полагая u₁ = 0, найдем значения потенциалов:

v₁ = 40 + u₁ = 40 + 0 = 40;

u₂ = v₁ – 10 = 40 – 10 = 30;

v₂ = 20 + u₂ = 20 + 30 = 50;

u₃ = v₁ – 20 = 40 – 20 = 20;

v₃ = 10 + u₃ = 10 + 20 = 30;

u₄ = v₂ – 20 = 50 – 20 = 30.

Для проверки опорного плана на оптимальность вычислим оценки свободных клеток полученной таблицы:

w₁₂ = c₁₂ – (v₂ – u₁) = 70 – (50 – 0) = 20;

w₁₃ = c₁₃ – (v₃ – u₁) = 20 – (40 – 0)= –20;

w₂₃ = c₂₃ – (v₃ – u₂) = 30 – (40 – 30) = 20;

w₃₂ = c₃₂ – (v₂ – u₃) = 40 – (50 – 20) = 10;

w₄₁ = c₄₁ – (v₁ – u₄) = 30 – (40 – 30) = 20;

w₄₃ = c₄₃ – (v₃ – u₄) = 50 – (40 – 30) = 40.

Оценка w₁₃ = –20 отрицательна. Следовательно, полученный опорный план не является оптимальным и может быть улучшен за счет перераспределения груза.

Клетка (1; 3)* – перспективная.

Строим цикл: (1; 3)* – (3; 3) – (3; 1) – (1; 1).

Присваиваем чередующиеся знаки «+» и «–», начиная с перспективной

клетки.

Находим величину перераспределения груза:

α = min {8000; 9000} = 8000 т.

Производим перераспределение груза в вершинах цикла:

x₁₁ = 8000 – 8000 = 0;

x₁₃ = 0 + 8000 = 8000;

x₃₃ = 9000 – 8000 = 1000;

x₃₁ = 1000 + 8000 = 9000.

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

z = 20∙8000 + 10∙3000 + 20∙2000 + 20∙9000 + 10∙1000 + 20∙7000 = 560000 (ден. ед.).

Составляем следующую распределительную таблицу (таблица 7):

 

Таблица 7

vj ui Участки Склады	1 – й	2 –й	3 –й	Наличие на складах
v1 = 30	v2 = 40	v3 = 20
I–й	u1 = 0	– 40	– 70	8000 20
II-й	u2 = 20	3000 10	2000 20	– 30
III-й	u3 = 0	9000 20	– 40	1000 10
IV-й	u4 = 20	– 30	7000 20	– 50
Потребности участков

 

Вычислим потенциалы строк и столбцов из системы уравнений для занятых клеток:

v₃ – u₁ = 20;

v₁ – u₂ = 10;

v₂ – u₂ = 20;

v₁ – u₃ = 20;

v₃ – u₃ = 10.

v₂ – u₄ = 20.

Полагая u₁ = 0, найдем значения потенциалов:

v₃ = 20 + u₁ = 20 + 0 = 20;

u₃ = v₃ – 10 = 20 – 10 = 10;

v₁ = 20 + u₃ = 20 + 10 = 30;

u₂ = v₁ – 10 = 30 – 10 = 20;

v₂ = 20 + u₂ = 20 + 20 = 40;

u₄ = v₂ – 20 = 40 – 20 = 20.

Вычислим оценки свободных клеток полученной таблицы:

w₁₁ = c₁₁ – (v₁ – u₁) = 40 – (30 – 0) = 10;

w₁₂ = c₁₂ – (v₂ – u₁) = 70 – (40 – 0) = 30;

w₂₃ = c₂₃ – (v₃ – u₂) = 30 – (20 – 20) = 30;

w₃₂ = c₃₂ – (v₂ – u₃) = 40 – (40 – 10) = 10;

w₄₁ = c₄₁ – (v₁ – u₄) = 30 – (30 – 20) = 20;

w₄₃ = c₄₃ – (v₃ – u₄) = 50 – (20 – 20) = 50.

Все оценки положительны. Следовательно, план перевозок является оптимальным.

.

Минимальные транспортные затраты для оптимального плана составляют z_min = 560000 ден. ед.

 

 

4.6. Индивидуальное задание № 4

 

Из складов лесоматериалов необходимо доставить лес на строительные площадки. Потребности строительных площадок (в м³), запасы леса на складах (в м³) и себестоимость перевозки 1 м³ леса (в ден. ед.) представлены в таблице.

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

Задачу решить методом потенциалов.

 

Вариант 1.

Склады	Строительные площадки	Запасы леса на складах
1-я	2-я	3-я	4-я	5-я
I
II
III
IV
Потребности строительных площадок

Вариант 2.

Склады	Строительные площадки	Запасы леса на складах
1-я	2-я	3-я	4-я
I	0,99	1,13	0,78	0,85
II	1,20	0,76	0,93	1,01
III	0,94	1,04	1,08	0,91
Потребности строительных площадок

Вариант 3.

Склады	Строительные площадки	Запасы леса на складах
1-я	2-я	3-я	4-я
I
II
III
Потребности строительных площадок

Вариант 4.

Склады	Строительные площадки	Запасы леса на складах
1-я	2-я	3-я	4-я
I	1,34	1,20	0,99	1,01
II	1,04	0,93	0,85	1,15
III	1,91	1,31	1,50	0,95
Потребности строительных площадок

Вариант 5.

Склады	Строительные площадки	Запасы леса на складах
1-я	2-я	3-я	4-я	5-я
I
II
III
IV
Потребности строительных площадок

 

Вариант 6.

Склады	Строительные площадки	Запасы леса на складах
1-я	2-я	3-я	4-я
I
II
III
IV
Потребности строительных площадок

Вариант 7.

Склады	Строительные площадки	Запасы леса на складах
1-я	2-я	3-я	4-я
I
II
III
Потребности строительных площадок

Вариант 8.

Склады	Строительные площадки	Запасы леса на складах
1-я	2-я	3-я	4-я	5-я
I
II
III
Потребности строительных площадок

Вариант 9.

Склады	Строительные площадки	Запасы леса на складах
1-я	2-я	3-я	4-я	5-я	6-я
I
II
III
IV
Потребности строительных площадок

Вариант 10.

Склады	Строительные площадки	Запасы леса на складах
1-я	2-я	3-я	4-я	5-я
I
II
III
IV
Потребности строительных площадок

Вариант 11.

Склады	Строительные площадки	Запасы леса на складах
1-я	2-я	3-я	4-я
I	1,10	0,98	0,86	1,03
II	0,79	0,91	1,20	1,10
III	1,14	1,30	0,78	0,91
Потребности строительных площадок

Вариант 12.

Склады	Строительные площадки	Запасы леса на складах
1-я	2-я	3-я	4-я	5-я	6-я
I
II
III
IV
Потребности строительных площадок

Вариант 13.

Склады	Строительные площадки	Запасы леса на складах
1-я	2-я	3-я	4-я	5-я
I
II
III
Потребности строительных площадок

Вариант 14.

Склады	Строительные площадки	Запасы леса на складах
1-я	2-я	3-я	4-я	5-я
I
II
III
Потребности строительных площадок

Вариант 15.

Склады	Строительные площадки	Запасы леса на складах
1-я	2-я	3-я	4-я	5-я
I
II
III
IV
Потребности строительных площадок

 

Вариант 16.

Склады	Строительные площадки	Запасы леса на складах
1-я	2-я	3-я	4-я
I
II
III
Потребности строительных площадок

Вариант 17.

Склады	Строительные площадки	Запасы леса на складах
1-я	2-я	3-я	4-я	5-я
I
II
III
IV
Потребности строительных площадок

Вариант 18.

Склады	Строительные площадки	Запасы леса на складах
1-я	2-я	3-я	4-я
I
II
III
IV
Потребности строительных площадок

Вариант 19.

Склады	Строительные площадки	Запасы леса на складах
1-я	2-я	3-я	4-я	5-я
I
II
III
IV
Потребности строительных площадок

Вариант 20.

Склады	Строительные площадки	Запасы леса на складах
1-я	2-я	3-я	4-я
I
II
III
Потребности строительных площадок

Вариант 21.

Склады	Строительные площадки	Запасы леса на складах
1-я	2-я	3-я	4-я
I	1,1	0,98	0,79	0,85
II	0,83	1,24	0,91	1,20
III	0,78	0,13	1,10	0,75
Потребности строительных площадок

Вариант 22.

Склады	Строительные площадки	Запасы леса на складах
1-я	2-я	3-я	4-я
I
II
III
IV
Потребности строительных площадок

Вариант 23.

Склады	Строительные площадки	Запасы леса на складах
1-я	2-я	3-я	4-я
I	0,71	0,69	0,83	0,91
II	0,88	0,90	0,71	0,69
III	0,65	0,79	0,90	0,81
Потребности строительных площадок

Вариант 24.

Склады	Строительные площадки	Запасы леса на складах
1-я	2-я	3-я	4-я
I
II
III
Потребности строительных площадок

Вариант 25.

Склады	Строительные площадки	Запасы леса на складах
1-я	2-я	3-я	4-я	5-я
I
II
III
Потребности строительных площадок

 

 

Вариант 26.

Склады	Строительные площадки	Запасы леса на складах
1-я	2-я	3-я
I	1,10	0,98	0,76
II	0,89	1,20	0,91
III	0,79	0,88	1,15
Потребности строительных площадок

Вариант 27.

Склады	Строительные площадки	Запасы леса на складах
1-я	2-я	3-я	4-я
I
II
III
IV
Потребности строительных площадок

Вариант 28.

Склады	Строительные площадки	Запасы леса на складах
1-я	2-я	3-я	4-я
I
II
III
Потребности строительных площадок

Вариант 29.

Склады	Строительные площадки	Запасы леса на складах
1-я	2-я	3-я	4-я	5-я
I
II
III
IV
Потребности строительных площадок

Вариант 30.

Склады	Строительные площадки	Запасы леса на складах
1-я	2-я	3-я	4-я
I
II
III
Потребности строительных площадок

 

ОТКРЫТАЯ МОДЕЛЬ ТРАНСПОРТНОЙ ЗАДАЧИ

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

Для открытой задачи возможны два случая: 1. Запасы превышают потребности: .

Типовой пример

Дана следующая содержательная постановка задачи.

 

Из трех песчаных карьеров необходимо вывезти песок на три строительных участка. Объем песка в карьерах (в тоннах), потребности строительных участков (в тоннах) и себестоимость перевозки одной тонны песка от каждого песчаного карьера к каждому строительному участку (в ден. ед.) представлены в таблице (таблица 1).

 

Таблица 1

Карьеры	Строительные участки	Объемы песка в карьерах
1-й	2-й	3-й
I	2	4	6
II	8	4	1
III	3	2	5
Потребности участков

 

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

Решение.

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

b₄ = 3500 – 2900 = 600 т.

Стоимость перевозки тонны песка от всех поставщиков к фиктивному потребителю полагаем равной 100. В таблице 2 построен первоначальный опорный план методом наилучшего элемента.

Таблица 2

Карьеры	Участки	Наличие на складах
1-й	2-й	3-й	Фиктивный
I	1200 2	600 4	-- 6	200 100
II	– 8	-- 4	600 1	400 100
III	– 3	500 2	-- 5	– 100
Потребности участков

 

Вычислим потенциалы строк и столбцов из системы уравнений для занятых клеток:

v₁ – u₁ = 2;

v₂ – u₁ = 4;

v₄ – u₁ = 100;

v₃ – u₂ = 1;

v₄ – u₂ = 100;

v₂ – u₃ = 2.

Полагая u₁ = 0, найдем потенциалы:

v₁ = 2;

v₂ = 4;

v₄ = 100;

u₂ = v₄ – 100 = 0;

v₃ = 1;

u₃ = 4 – 2 = 2.

Вычислим оценки свободных клеток полученной таблицы:

w₁₃ = 6 – (1 – 0) = 5;

w₂₁ = 8 – (2 – 0) = 6;

w₂₂ = 4 – (4 – 0) = 0;

w₃₁ = 3 – (2 – 3) = 2;

w₃₃ = 5 – (1 – 2) = 6;

w₃₄ = 100 – (100 – 2) = 2.

Так как среди оценок нет отрицательных, то первоначальный опорный план

является оптимальным.

Значение целевой функции z_min = 1200·2 + 600·4 + 600·1 + 500·2 = 6400 (ден.ед.).

 

5.3. Индивидуальное задание № 5

 

Необходимо перевезти гравий из карьеров на строительные площадки. Потребности строительных площадок в гравии (в тоннах), производственные выработки карьеров (в тоннах), а также себестоимость перевозки одной тонны гравия от каждого карьера к каждой строительной площадке (в ден. ед.) заданы в таблице.

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

 

Вариант 1.

Карьеры	Строительные участки	Объем гравия в карьерах
1-й	2-й	3-й	4-й
I
II
III
Потребности строительных участков

 

 

Вариант 2.

Карьеры	Строительные участки	Объем гравия в карьерах
1-й	2-й	3-й	4-й
I
II
III
Потребности строительных участков

Вариант 3.

Карьеры	Строительные участки	Объем гравия в карьерах
1-й	2-й	3-й	4-й
I
II
III
Потребности строительных участков

Вариант 4.

Карьеры	Строительные участки	Объем гравия в карьерах
1-й	2-й	3-й	4-й
I
II
III
Потребности строительных участков

Вариант 5.

Карьеры	Строительные участки	Объем гравия в карьерах
1-й	2-й	3-й	4-й
I
II
III
Потребности строительных участков

 

 

Вариант 6.

Карьеры	Строительные участки	Объем гравия в карьерах
1-й	2-й	3-й	4-й
I
II
III
Потребности строительных участков

Вариант 7.

Карьеры	Строительные участки	Объем гравия в карьерах
1-й	2-й	3-й	4-й
I
II
III
Потребности строительных участков

Вариант 8.

Карьеры	Строительные участки	Объем гравия в карьерах
1-й	2-й	3-й	4-й
I
II
III
Потребности строительных участков

Вариант 9.

Карьеры	Строительные участки	Объем гравия в карьерах
1-й	2-й	3-й	4-й
I
II
III
Потребности строительных участков

 

 

Вариант 10.

Карьеры	Строительные участки	Объем гравия в карьерах
1-й	2-й	3-й	4-й
I
II
III
Потребности строительных участков

Вариант 11.

Карьеры	Строительные участки	Объем гравия в карьерах
1-й	2-й	3-й	4-й	5-й
I
II
III
Потребности строительных участков

Вариант 12.

Карьеры	Строительные участки	Объем гравия в карьерах
1-й	2-й	3-й	4-й
I
II
III
Потребности строительных участков

Вариант 13.

Карьеры	Строительные участки	Объем гравия в карьерах
1-й	2-й	3-й	4-й
I
II
III
Потребности строительных участков

 

 

Вариант 14.

Карьеры	Строительные участки	Объем гравия в карьерах
1-й	2-й	3-й	4-й
I
II
III
Потребности строительных участков

Вариант 15.

Карьеры	Строительные участки	Объем гравия в карьерах
1-й	2-й	3-й	4-й
I
II
III
Потребности строительных участков

Вариант 16.

Карьеры	Строительные участки	Объем гравия в карьерах
1-й	2-й	3-й	4-й
I
II
III
Потребности строительных участков

Вариант 17.

Карьеры	Строительные участки	Объем гравия в карьерах
1-й	2-й	3-й	4-й
I
II
III
Потребности строительных участков

 

 

Вариант 18.

Карьеры	Строительные участки	Объем гравия в карьерах
1-й	2-й	3-й	4-й
I
II
III
Потребности строительных участков

Вариант 19.

Карьеры	Строительные участки	Объем гравия в карьерах
1-й	2-й	3-й	4-й
I
II
III
Потребности строительных участков

Вариант 20.

Карьеры	Строительные участки	Объем гравия в карьерах
1-й	2-й	3-й	4-й
I
II
III
Потребности строительных участков

Вариант 21.

Карьеры	Строительные участки	Объем гравия в карьерах
1-й	2-й	3-й	4-й
I
II
III
Потребности строительных участков

 

Вариант 22.

Карьеры	Строительные участки	Объем гравия в карьерах
1-й	2-й	3-й	4-й
I
II
III
Потребности строительных участков

Вариант 23.

Карьеры	Строительные участки	Объем гравия в карьерах
1-й	2-й	3-й	4-й
I
II
III
Потребности строительных участков

Вариант 24.

Карьеры	Строительные участки	Объем гравия в карьерах
1-й	2-й	3-й	4-й	5-й
I
II
III
Потребности строительных участков

Вариант 25.

Карьеры	Строительные участки	Объем гравия в карьерах
1-й	2-й	3-й	4-й
I
II
III
Потребности строительных участков

 

Вариант 26.

Карьеры	Строительные участки	Объем гравия в карьерах
1-й	2-й	3-й	4-й	5-й
I
II
III
Потребности строительных участков

Вариант 27.

Карьеры	Строительные участки	Объем гравия в карьерах
1-й	2-й	3-й	4-й
I
II
III
Потребности строительных участков

Вариант 28.

Карьеры	Строительные участки	Объем гравия в карьерах
1-й	2-й	3-й	4-й
I
II
III
Потребности строительных участков

Вариант 29.

Карьеры	Строительные участки	Объем гравия в карьерах
1-й	2-й	3-й	4-й
I
II
III
Потребности строительных участков

 

Вариант 30.

Карьеры	Строительные участки	Объем гравия в карьерах
В1	В2	В3	В4
А1
А2
А3
Потребности строительных участков

 

 

Литература

Основная:

1. Волкова В.Н., Денисов А.А. Основы теории систем и системного анализа. – СП-б.: изд-во СП-б ГТУ, 1997.

2. Губанов В.А., Захаров В.В., Коваленко А.Н. Введение в системный анализ. – Ленинград: Изд-во ЛГУ, 1988.

3. Лямец В.И., Тевяшев А.Д. Системный анализ. - Харьков: ХТУРЭ, 1998 – 252 с.

4. Перегудов Ф.И., Тарасенко Ф.П. Введение в системный анализ. – М.: Высшая школа, 1989.

5. Перегудов Ф.П., Тарасенко Ф.П. Основы системного анализа. – Томск: Изд-во НТЛ, 2001.

6. Спицнадель В. Н. Основы системного анализа. – Спб.: Изд. Дом «Бизнес-пресса», 2000. – 326 с.

 

Дополнительная:

1. Акулич И.Л. Математическое программирование в примерах и задачах. – М.: Высшая школа, 1986. – 319 с.

2. Кулян В.Р., Юнькова Е.А., Жильцов А.Б. Математическое программирование (с элементами информационных технологий). – К.: МАУП, 2003. – 124 с.

3. Нефедов Ю.М. Методы оптимизации. – Луганск: Изд-во ВНУ им. В. Даля, 2004. – 240 с.

4. Нефедов Ю.М. Сборник примеров и задач по математическому программированию. – Луганск: Изд-во ВУГУ, 1999. – 93 с.

5. Ногин В.Д., Протодьяконов И.О., Евлампиев И.И. Основы теории оптимизации. – М.: Высшая школа, 1986. – 384 с.

6. Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации. – М.: Наука, 1986. – 325 с.