МИНИСТЕРСТВО СВЯЗИ И ИНФОРМАТИЗАЦИИ РЕСПУБЛИКИ БЕЛАРУСЬ

Учреждение образования

«ВЫСШИЙ ГОСУДАРСТВЕННЫЙ КОЛЛЕДЖ СВЯЗИ»

Кафедра математики и физики

Математическое программирование

Руководство по решению задач

для студентов

всех специальностей

В 2 частях

Часть 2

Минск

2014

УДК 811.1

ББК 81.2 М.

М

Рекомендовано к изданию

кафедрой математики и физики

30 Мая 2013, протокол № 10

Составитель

Е. М. Колодная, старший преподаватель

кафедры математики и физики

Рецензент

Л. Л. Гладков, зав. кафедрой математики и физики,

доктор физ.-мат. наук

М	Математическое программирование : руководство по решению задач для студентов всех специальностей. В двух частях, часть 2 / сост. Е. М. Колодная. – Мн. : УО ВГКС, 2013. – 96 с. Предназначено для студентов и преподавателей колледжа. УДК 811.1 ББК 81.2 М.

© Учреждение образования «Высший государственный колледж связи», 2014

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

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

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

Задачи 43

ТЕМА 3 ЗАДАЧА О НАЗНАЧЕНИЯХ 51

3.1 Математическая модель задачи о назначениях 51

3.2 Решение задачи о назначениях 53

Задачи 65

ТЕМА 4 ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ 71

4.1 Задача оптимального распределения ресурсов 73

Задачи 78

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

Задачи 102

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

ТЕМА 2 ТРАНСПОРТНАЯ ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ (ТЗ)

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

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

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

Для наглядности, условие транспортной задачи можно представить таблицей, которую будем называть распределительной. Распределительную таблицу называют иногда табличной илиматричной моделью ТЗ (таблица 2.1).

Таблица 2.1

Поставщики	Потребители							Запас, единиц
					...
					...
					...
...	...		...		...	...		...
					...
Потребность ,единиц					...

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

Введем переменные – объемы перевозок от-го поставщика-му потребителю.

Матрицу будем называтьматрицей перевозок.

Цель ТЗ – минимизировать суммарные затраты на перевозку всего груза, следовательно, целевая функция будет иметь вид:

(2.1)

Составим систему ограничений (2.2) в случае, когда , которая будет определять ОДР данной задачи.

(2.2)

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

Будем называть план перевозок

допустимым, если он удовлетворяет системе ограничений (2.2).

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