Содержание

Стр.

Глава 1. Линейное программирование 3

1.1. Математическая модель задачи линейного программирования 3

Задачи 7

1.2. Формы записи задач линейного программирования 11

Задачи 16

1.3. Геометрическая интерпретация и графический метод решения задач линейного программирования с двумя переменными 17

Задачи 26

1.4. Графический метод решения задач линейного программирования с n переменными 30

Задачи 35

1.5. Симплексный метод решения задач линейного программирования 36

Задачи 58

1.6. Двойственные задачи линейного программирования 59

Задачи 66

Глава 2. Транспортная задача линейного программирования (тз) 68

2.1. Математическая модель транспортной задачи 68

2.2. Решение транспортной задачи 72

Задачи 94

Глава 3. Динамическое программирование 98

3.1. Задача оптимального распределения ресурсов 99

Задачи 103

3.2. Задача об оптимальной стратегии замены оборудования 105

Задачи 116

Список использованной литературы 118

Глава 1. Линейное программирование

1.1. Математическая модель задачи линейного программирования

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

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

Для составления математической модели необходимо:

1. выбрать переменные задачи;

2. составить систему ограничений;

3. задать целевую функцию.

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

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

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

Экстремальным значением называют максимальное или минимальное значение.

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

(1.1)

и удовлетворяют системе ограничений

(1.2)

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

Допустимым решением (планом) ЗЛП называется вектор , удовлетворяющий системе ограничений задачи.

Множество допустимых решений задачи образует область допустимых решений (ОДР).

Допустимое решение (план), доставляющий целевой функции экстремальное значение, называется оптимальным решением (оптимальным планом). Его будем обозначать .

Экстремальное значение целевой функции .

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

Составим математические модели некоторых задач линейного программирования (примеры 1.1 – 1.3).

Пример 1.1

Имеются стержни, длиной 5 м. Их необходимо разрезать на заготовки 2-х видов: заготовки А – длиной 1,5 м и заготовки В – длиной 0,8 м для производства 20 изделий. На каждое изделие требуется две длинных заготовки (А) и три коротких (В). Определить число стержней, которое необходимо разрезать каждым из возможных способов, чтобы изготовить нужное число изделий и минимизировать отходы.

Решение

Прежде всего, перебрав все возможные способы, построим карту раскроя одного стержня:

Способ	Количество заготовок А (по 1,5 м)	Количество заготовок В (по 0,8 м)	Отходы, м
I	3		0,5
II	2	2	0,4
III	1	4	0,3
IV		6	0,2

Для изготовления 20 изделий потребуется заготовок А: 202 = 40 шт. и заготовок В: 203 = 60 шт.

1) Введем переменные. Обозначим за – количество стержней, которые будут разрезаныI способом, – II способом, – III способом, –IV способом.

2. Целевая функция Z – отходы. Ее будем минимизировать. Найдем отходы, полученные при разрезании стержней:

–отходы, полученные при разрезании стержнейI способом,

так как 5 – 3·1,5 = 0,5;

–отходы, полученные при разрезании стержней II способом,

так как 5 – 2·1,5 – 2·0,8 = 0,4;

–отходы, полученные при разрезании стержней III способом,

так как 5 – 1·1,5 – 4·0,8 = 0,3;

–отходы, полученные при разрезании стержней IV способом,

так как 5 – 6·0,8 = 0,2.

Тогда .

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

а) Ограничение на заготовки А.

При разрезании стержнейI способом получим заготовок А,

стержней II способом – заготовок А, стержней III способом – заготовок А, при разрезании стержней IV способом заготовок А не образуется. Таким образом, всего получим заготовок А, что по условию задачи должно быть не менее 40, то есть.

б) Аналогично получим ограничение на заготовки В:

.

в) Составим ограничения на экономический смысл переменных. Так как количество стержней может быть только неотрицательным числом, то и– целые.

Итак, математическая модель данной задачи имеет вид:

;

Пример 1.2

Предприятие за 10 часов должно произвести 31 единицу продукции вида П₁ и 36 единиц продукции вида П₂. Для производства продукции каждого вида может быть использовано оборудование А₁ или А₂.

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

5, 3,4,6,

8, 7,4,2.

Решение

Для наглядности составим таблицу:

	Продукция П1	Продукция П2	Запас времени, ч
Оборудование А1	ед./ч усл. ден. ед./ч	ед./ч усл. ден. ед./ч	10
Оборудование А2	ед./ч усл. ден. ед./ч	ед./ч усл. ден. ед./ч	10
План производства, ед.	31	36

1) Обозначим за – время работы оборудования А_i по выпуску продукции П_j, .

2) Целевая функция будет представлять собой затраты на выпуск продукции, которые необходимо минимизировать. Так как затраты по выпуску продукции П_j на оборудование А_i составляют , то целевая функция будет иметь вид:

, т. е. .

3. Составим систему ограничений.

а) Ограничение на выпуск продукции П₁.

На оборудовании А₁ будет произведено единиц продукции П₁.

На оборудовании А₂ будет произведено единиц продукции П₁.

Таким образом всего продукции П₁ будет произведено , что по условию должно быть равно 31, то есть получим ограничение

, или .

б) Аналогично получим ограничение по выпуску продукции П₂:

, или .

в) Ограничение на время работы оборудования А₁.

Время работы оборудования А₁ по выпуску обоих видов продукции не превышает плановый период 10 ч, следовательно, ограничение будет иметь вид: .

г) Аналогично получим ограничение на время работы оборудования А₂: .

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

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

;

Пример 1.3

Предприятие может выпускать продукцию двух видов: П₁ и П₂. При этом используется три вида ресурсов: время работы оборудования, сырье и электроэнергия. Нормы расхода, запасы ресурсов и прибыль от реализации единицы продукции представлены в таблице:

Ресурсы	Нормы расхода на единицу продукции		Запас ресурса
	П1	П2
Время работы оборудования, ч Сырье, кг Электроэнергия, кВтч.	2 1 2	3 1 1	30 12 20
Прибыль от единицы продукции, руб.	5	4

Найти оптимальный план выпуска продукции.

Решение

Введем переменные:

, – объем выпускаемой продукции П₁ и П₂ соответственно, единиц.

Z – прибыль от реализации всей выпущенной продукции.

Математическая модель данной задачи будет иметь вид:

;

Методы решения задач линейного программирования будут рассмотрены ниже.

Задачи

1.1.1

Необходимо за 24 часа изготовить максимальное количество изделий, общая себестоимость которых не должна превышать 2000 руб., используя при этом два станка. Производительность первого станка составляет 5 изделий в час, второго – 6 изделий в час. Себестоимость одного изделия, изготовленного на первом станке, составляет 9 руб., на втором станке – 10 руб. Составить математическую модель выпуска продукции на указанных станках.

1.1.2

Цех может выпускать 2 вида продукции, производство которых характеризуется следующими данными:

Продукция	Время на производство изделия, ч	Количество металла на изделие, кг	Прибыль от реализации изделия, руб.
I вид II вид	2 5	1 3	30 80

В планируемом месяце имеется 100 часов рабочего времени и 60 кг металла. Продукции I вида должно бать выпущено не менее 25 изделий. Составить математическую модель задачи выпуска продукции с максимальной прибылью от реализации.

1.1.3

Завод должен переслать 1000 деталей в ящиках двух типов. Ящик I типа вмещает 70 деталей, ящик II типа – 40 деталей. Стоимость пересылки одного ящика I типа составляет 30 руб., II типа – 20 руб. Для пересылки можно использовать не более 12 ящиков I типа. Составить математическую модель задачи пересылки всех деталей с наименьшими затратами

1.1.4

Имеются путевки в дома отдыха 3-х видов: на 7, 12 и 20 дней. Стоимость их 100 руб., 150 руб. и 250 руб. соответственно. Организация планирует закупить 21 путевку и потратить не более 3000 руб. Составить математическую модель задачи определения нужного числа путевок каждого вида, чтобы общее число дней отдыха по всем путевкам оказалось наибольшим.

1.1.5

Для рекламирования своей продукции фирма может использовать радио, телевиденье и общественный транспорт. Стоимость одной минуты рекламы на радио составляет 3 усл. ден. ед., а на телевиденье – 50 усл. ден. ед., в общественном транспорте – 2 усл. ден. ед. Объемы продаж увеличиваются от рекламы на радио, телевиденье и в общественном транспорте в соотношении 2:30:1. Фирма может использовать в месяц не более 10 минут эфирного времени на телевиденье и не более 100 минут на радио. На всю рекламу фирма запланировала потратить в месяц не более 900 усл. ден. ед. Составить математическую модель задачи эффективного вложения в рекламу денежных средств.

1.1.6

Нужно перевести по железной дороге 20 больших и 150 малых контейнеров, используя при этом минимальное количество вагонов. Вес малого контейнера составляет 2 тонны, а большого – 5 тонн. Грузоподъемность вагона – 60 тонн, недогрузка вагонов не допускается. Составить математическую модель задачи перевозки всех контейнеров.

1.1.7

Из пункта S в пункт T необходимо перевести 250 ед. оборудования типа I, 120 – типа II, 340 – типа III на автомобилях вида А, В, С и D. Количество оборудования одновременно вмещаемого на определенный автомобиль и затраты на одну поездку каждого автомобиля приведены в таблице:

Тип оборудования	Количество оборудования вмещаемого на автомобиль
	А	В	С	D
I II III	0 4 2	2 0 6	1 2 3	4 1 0
Затраты, руб.	8	10	6	7

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

1.1.8

Цех может выпускать 3 вида продукции, производство которых характеризуется следующими данными:

Продукция	Время на производство ед. продукции, ч	Количество металла на ед. продукции, кг	Прибыль от реализации ед. продукции, руб.
I вид II вид III вид	4 3 1	5 2 3	330 210 120

В планируемом месяце имеется 500 часов рабочего времени и 700 кг металла. Составить математическую модель задачи выпуска продукции с максимальной прибылью от реализации.

1.1.9

Предприятие за 8 часов должно выпустить 25 единиц продукции вида П₁ и 35 единиц продукции вида П₂. Для производства продукции каждого вида может быть использовано оборудование А₁ или А₂.

Производительность оборудования А₁ по выпуску продукции П₁ составляет 4 ед./ч, а по выпуску продукции П₂ – 5 ед./ч., стоимость 1 часа работы оборудования А₁ составляет 15 руб. Производительность оборудования А₂ по выпуску продукции П₁ составляет 3 ед./ч, а по выпуску продукции П₂ – 2 ед./ч., стоимость 1 часа работы оборудования А₂ составляет 7 руб. Составить математическую модель задачи выпуска запланированной продукции с минимальной себестоимостью.

1.1.10

В плановом году строительные организации города переходят к сооружению домов типов Д1, Д2, Д3 и Д4. Данные о количестве квартир разного типа в каждом из указанных типов домов, их плановая себестоимость приведены в таблице:

Тип квартиры	Тип дома
	Д1	Д2	Д3	Д4
Однокомнатная Двухкомнатная Трехкомнатная Четырехкомнатная	10 40 60 20	18 20 90 10	20 20 10 –	15 60 – 5
Плановая себестоимость, ден. ед.	8300	7900	3600	4500

Годовой план ввода жилой площади составляет соответственно 1000, 1300, 1500 и 300 квартир указанных типов. Составить математическую модель задачи выполнения плана ввода квартир (а возможно, и его перевыполнения) с минимальной себестоимостью.

1.1.11

Необходимо за 8 часов изготовить 200 изделий, используя при этом три станка. Производительность первого станка составляет 10 изделий в час, второго – 12 изделий в час, третьего – 9 изделий в час. Себестоимость одного изделия, изготовленного на первом станке, составляет 3 руб., на втором станке – 2,8 руб., на третьем станке – 2,5 руб. Составить математическую модель задачи выпуска продукции на указанных станках с минимальной себестоимостью.

1.1.12

На производство поступило 100 стержней длиной 1м, которые необходимо разрезать на заготовки А длиной 0,3м и заготовки В длиной 0,2м. Для изготовления одного изделия требуется 1 заготовка А и 3 заготовки В. Составить математическую модель задачи раскроя стержней для изготовления максимального количества изделий.