Задачи для самостоятельного решения.

1. Для изготовления деталей двух видов имеется 100 кг металла. На изготовление одного вида деталей расходуется 2кг металла, а на изготовление детали второго вида - 4кг. Составить план производства, обеспечивающий получение наибольшей прибыли, если изделие первого вида дает прибыль 3 ден.ед., а изделие второго вида – 2 ден. ед. Причем изделий первого вида требуется изготовить не более 40, а изделий второго вида – не более 20.

2. Решить следующую сырьевую задачу:

	Продукт 1	Продукт 2	Продукт 3	Запасы
Сырье 1	-	2	-	10
Сырье 2	-	5	3	30
Сырье 3	1	1	1	8
прибыль	1	2	2

Третье сырье израсходовать полностью.

3.Решить следующую задачу ЛП:

Транспортная задача.

Постановка транспортной задачи

Однородный груз, имеющийся в m пунктах отправления (производства) А1, А2, ...Аm соответственно в количествах а1, а2, ...аm единиц, требуется доставить в каждый из n пунктов назначения (потребления) В1, В2, ..., Вn соответственно в количествах b1, b2 ..., bn единиц. Стоимость перевозки (тариф) единицы продукции из Аi в Вj известна для всех маршрутов AiBj и cij (i=1,m; j=1,n). Требуется составить такой план перевозок, при котором весь груз из пунктов отправления вывозится и запросы всех пунктов потребления удовлетворяются (закрытая модель), т. е.

а суммарные транспортные расходы минимальны.

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

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

Допустимый план называтся опорным , если в нем отличны от нуля не более m+n-1 базисных перевозок, а остальные перевозки равны 0.

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

Методы решения транспортных задач

Составляется таблица, в ячейки которой заносят количество перевозимого груза из Аi в Bj груза Xij>=0, а в маленькие клетки - соответствующие тарифы Cij:

Затем решение задачи разбивается на два этапа:

1. Определение опорного плана

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

Для определения начального опорного плана используется метод наименьшего элемента. Сущность способа в том, что на каждом шаге заполняется та клетка оставшейся части таблицы, которая имеет наименьший тариф; в случае наличия нескольких таких равных тарифов заполняется любая из них, причем максимально возможным числом: либо полностью выносится груз из Аi, либо полностью удовлетворяется потребность Вj. Процедура продолжается до тех пор, пока на каком-то шаге не исчерпаются запасы аi и не удовлетворятся все потребности bj. В заключении проверяют, что найденные компоненты плана Хij удовлетворяют горизонтальным и вертикальным уравнениям.

Для нахождения оптимального плана перевозок последовательно используют метод потенциалов. Соотношения (*) определяют систему из m+n-1 линейных уравнений с m+n известными, имеющую бесчисленное множество решений; для её определённости одному неизвестному придают любое число (обычно альфа равное 0), тогда все остальные неизвестные определяются однозначно.