27. Анализ решения задачи по симплекс – таблице, отвечающей критерию оптимальности.

Схема решения задачи симплексным методом(Это может быть и не то)

1) указывается способ вычисления первоначального допустимого решения задачи.

2) при помощи признака оптимальности проверяется не является ли это решение оптимальным.

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

Алгоритм перехода к симплекс-таблице № 2:

1) Неизвестные x 2 и x 4 меняют местами.

2) Разрешающий элемент a 24 заменяют обратной величиной.

3) Остальные элементы разрешающей строки делим на разрешающий элемент.

4) Элементы разрешающего столбца, кроме разрешающего

элемента, делят на разрешающий элемент и

меняют знаки.

5) Все остальные элементы симплекс–таблицы № 2 получают по правилу прямоугольника: Из произведения элементов диагонали, содержащей искомый элемент, вычитают произведение элементов противоположной диагонали и делят всё на элемент, противоположный искомому.

28. Транспортная задача. Постановка задачи.

Транспортная задача (Т.З.) одна из распространённых задач Л.П.

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

Всё это сокращает время продвижения товаров, уменьшает затраты предприятий связанные с

осуществлением процессов снабжения сырьём, материалами, топливом, оборудованием и т.д.

Под термином Т.З. понимается широкий круг задач не только транспортного характера.

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

– прикрепление потребителей ресурса к производителям;

– привязка пунктов отправления к пунктам назначения;

– взаимная привязка грузопотоков прямого и обратного направлений; – отдельные задачи оптимальной

загрузки промышленности оборудования;

– оптимальное распределение объёмов выпуска промышленной продукции между заводами- изготовителями.

Постановка задачи:

Однородный груз сосредоточен у m поставщиков в объемах а₁, а₂, …, а_m.

Данный груз необходимо доставить n потребителям в объемах, b₁, b₂, … , b_n.

Известен С_ij (i= 1, 2, … , m; j=1, 2 ,…, n) – стоимости перевозки единицы груза от каждого i-го поставщика каждому j-му потребителю.

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

Исходные данные транспортной задачи записываются в таблице

Переменными (неизвестным) транспортной задачи являются x_ij (i=1,2,…,m; j=1,2,…,n) – объемы перевозок от каждого i-го поставщика j-му потребителю. Эти переменные могут быть записаны в виде матрицы перевозок.

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

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

Целевая функция задачи Z(X) выражает требование обеспечить минимум суммарных затрат на перевозку всех грузов. Вторая группа из уравнений ограничений записанных в общем виде, выражает требование, что запасы всех m, поставщиков вывозятся полностью, а также полностью должны удовлетворятся запросы всех n потребителей. Последнее неравенство является условием неотрицательности всех переменных.

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

такая задача называется сбалансированной, а её модель закрытой. Если же это равенство не выполняется, то задача называется несбалансированной (с неправильным балансом), а её модель – открытой.

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

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

если целевая функция Z’ стремится к минимуму то в системе ограничении меняется знак: экономический смысл перемененных двойственной задачи:

U_i, V_j – называются потенциалами.

Определения:

1. Если задача открыта, то необходимо добавить фиктивного поставщика или потребителя с недостающим объемом поставки и нулевой стоимостью перевозки. Распределение поставки фиктивному потребителю (поставщику), идет в последнюю очередь.

2. Клетка в плане перевозок называется базисной (закрытой), если в нее ставится перевозка.

3. Количество базисных клеток определяется соотношением r=m+n-1. опорное решение не может иметь базисных клеток больше, чем r.

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

5. Если в задаче указана не только стоимость перевозки, но и стоимость производства товара, тогда необходимо сложить эти стоимости с учетом перевозки товара от i-го поставщика j-му потребителю. Кроме того, математическая модель составляется с учетом этой суммарной стоимости.