Выполнения заданий. Теоретические вопросы

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

Теоретические вопросы

ТЕМА 5. ИССЛЕДОВАНИЕ ОПЕРАЦИЙ

1. Сформулируйте постановку следующих экономико-математических моделей: задача о ресурсах, задача и диете, транспортная задача.

2. Запишите стандартную форму записи задачи линейного программирования.

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

4. Какие переменные называются базисными в задаче линейного программирования?

6. Что такое допустимое и оптимальное решение задачи линейного программирования?

7. Сформулируйте основную идею симплекс-метода.

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

9. Как составить опорный план транспортной задачи?

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

Пример 1.. Пусть бригада имеет: 300 кг металла, 100 м² стекла, 160 чел. / час. рабочего времени. Надо изготовить: изделия А и В. Прибыль от реализации изделий: А — 10 у.е., В — 12 у.е. Для изготовления изделия А расходуется: 4 кг металла, 2 м² стекла и 2 чел./час. рабочего времени. Для изготовления изделия В расходуется: 5 кг металла, 1 м² стекла и 3 чел./час. рабочего времени. Требуется спланировать выпуск продукции так, чтобы прибыль была максимальной. Решить задачу симплекс-методом.

Решение. Математическая постановка задачи.

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

Прибыль от реализации всей продукции составит

Это типичная задача линейного программирования (). Вид данной задачи не канонический, поскольку условия имеют вид неравенств, а не уравнений. Сведем ее к каноническому виду, добавив дополнительные переменные по числу ограничений - неравенств:

(1)

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

Перепишем систему (1) в более удобном виде, выразив дополнительные переменные

(2)

Чтобы свести данную задачу к задаче минимизации целевой функции, функцию нужно взять со знаком минус:

Запишем условие задачи в виде таблицы

(3)

Так как все , то в качестве начального опорного решения можно взять следующее решение:

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

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

Наименьшей является величина 53,3, которая соответствует переменной . Определим новое опорное решение из системы (2):

Значение целевой функции

Это решение уже лучше.

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

(4)

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

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

Наименьшей является величина 35, которая соответствует переменной . Определим новое опорное решение:

Значение целевой функции

Это решение еще лучше предыдущего.

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

(5)

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

Ответ: Для получение максимума прибыли в 710 у.е. необходимо изготовить 35 изделий А и 30 изделий В. При этом все ресурсы стекла и рабочего времени будут использованы полностью, а металла останется 10 кг.

Пример 2. Найти опорное решение задачи методом северо-западного угла.

На три базы А₁, А₂, А₃ поступил однородный груз в количествах, приведенных в таблице 3. Требуется перевезти этот груз в пять пунктов назначения В₁, В₂, B₃, В₄, В₅, данные приведены в таблице 1. Составить опорный план методом северо-западного угла, и найти такой план закрепления потребителей и поставщиков, чтобы общие затраты на перевозки были минимальны (метод потенциалов).

Таблица 1

Пункт отправления	Пункты назначения	Запасы
Потребности

Стоимость перевозок единицы груза с каждого из пунктов отправления в соответствующие пункты назначения известны. Найти план перевозок методом северо-западного угла.

Решение. Здесь число пунктов отправления m=3, а число пунктов назначения n=5. Заполнение таблицы начинаем с верхней левой клетки (1,1), т.е. попытаемся удовлетворить потребности первого пункта назначения за счет запасов первого пункта отправления. Так как запасы пункта А₁ больше, чем потребности пункта В₁, то полагаем , записываем это значение в клетке (1,1) и временно исключаем из рассмотрения столбец В₁, считая при этом запасы А₁=80. Рассматриваем далее первые из оставшихся пунктов отправления А₁ и назначения В₂. Запасы пункта А₁ больше потребностей пункта В₂. Положим , запишем это значение в клетку (1,2) и временно исключим из рассмотрения столбец В₂. В пункте А₁ осталось 10 единиц груза. Снова рассмотрим первые из оставшихся пунктов отправления А₁ и пунктов назначения В₃. Потребности В₃ больше оставшихся запасов пункта А₁. Положим и исключим из рассмотрения строку А₁. Значение записываем в клетку (1,3) и считаем потребности пункта В₃ равными 110 единиц.

Переходим к заполнению клетки (2,3) и т.д. Через шесть шагов остается один пункт отправления А₃ с запасом груза 100 единиц и один пункт назначения В₅ с потребностью 100 единиц. Имеется одна клетка (3,5), которую и заполняем . В результате получили опорный план

Пункт отправления	Пункты назначения	Запасы
Потребности

Клетки таблицы, в которых стоят ненулевые переменные, являются базисными, их число равно 7. Остальные клетки - свободные (пустые), в них стоят нулевые переменные, их число равно . Условия для опорного плана выполнены.

Согласно данному плану перевозок, общая стоимость перевозок всего груза составляет

F =2•60+ 3•70 + 4•10 + 1•110 + 4•70 + 7•60 + 2•100 = 1380

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

.

Запишем оценки для пустых клеток и проследим выполнение неравенства :

Так как , то составим цикл для клетки (3,3).

Пункт отправления	Пункты назначения	Запасы
			10
			- 110	+ 70
			+	- 60
Потребности

Цена цикла составляет . Составим потенциальный план, перемещая по циклу 60 единиц.

Пункт отправления	Пункты назначения	Запасы
Потребности

Согласно новому плану перевозок, общая стоимость перевозок всего груза составляет

F =2•60+ 3•70 + 4•10 + 1•50 + 4•130 + 3•60 + 2•100 = 1320

Проверим оптимален ли полученный план.

.

Запишем оценки для пустых клеток и проследим выполнение неравенства :

Так как , то составим цикл для клетки (1,4).

Пункт отправления	Пункты назначения	Запасы
			- 10	+
			+50	- 130
Потребности

Пункт отправления	Пункты назначения	Запасы
Потребности

Согласно новому плану перевозок, общая стоимость перевозок всего груза составляет

F =2•60+ 3•70 + 2•10 + 1•60 + 4•120 + 3•60 + 2•100 = 1270

Проверим оптимален ли полученный план.

.

Запишем оценки для пустых клеток и проследим выполнение неравенства :

Так как , то составим цикл для клетки (2,2).

Пункт отправления	Пункты назначения	Запасы
		- 70		+ 10
		+		- 120
Потребности

Пункт отправления	Пункты назначения	Запасы
Потребности

Согласно новому плану перевозок, общая стоимость перевозок всего груза составляет

F =2•60+ 2•80 + 4•70 + 1•60 + 4•50 + 3•60 + 2•100 = 1200

Проверим оптимален ли полученный план.

.

Запишем оценки для пустых клеток и проследим выполнение неравенства :

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

ИНДИВИДУАЛЬНЫЕ ЗАДАНИЯ

Дата добавления: 2015-07-02