2.5.3. Классификация задач

Возможны три типа задач:

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

2.Вероятностные задачи (задачи с риском). Задачи, возникающие в ситуациях, когда руководитель полагает, что могут быть получены различные результаты, вероятности достижения которых известны или могут быть оценены.

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

Контрольные вопросы

1. Когда целесообразно проводить эксперимент при исследовании системы?

2. Что представляет собой операционная модель?

3. В какой форме чаще всего выражается целевая функция?

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

5. Перечислите составные части операционного проекта

6. Какие классы операционных задач выделяют в ИСО?

7. Какие условия должны быть учтены в каждой операционной задаче?

8. Назовите две категории целей в операционных задачах.

9. Перечислите три типа операционных задач

Лекция 3 транспортная задача линейного программирования

План

3.1. Формулировка задачи

3.2. Нахождение опорного решения методом «северо-западного угла»

3.3. Нахождение опорного решения методом «минимального элемента»

3.1. Формулировка задачи

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

(3.1)

Содержательная формулировка транспортной задачи выглядит следующим образом:

Пусть в пунктах А₁, А₂,..., А_m производится некоторый однородный продукт, причём, объём производства этого продукта в пункте A_i‚ составляет а_i единиц, i = 1,. . .,m.

Произведённый в пунктах производства продукт требуется доставить в пункты потребления В₁, В₂, ..., В_n, причём объём потребления в пункте В_j составляет b_j единиц продукта.

Предполагается, что транспортировка готовой продукции возможна из любого пункта производства в любой пункт потребления и транспортные издержки, приходящиеся на перевозку единицы продукта из пункта А_i в пункт В_j, составляют a_i денежных единиц, i =1,...,m.

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

Формальная постановка «транспортной задачи».

Пусть x_ij - количество продукта, перевозимого из пункта А_i в пункт В_j. Требуется определить совокупность из mn величин х_ij, удовлетворяющих условиям:

(3.2)

и обращающих в минимум линейную форму:

(3.3.)

Для решения «транспортной задачи» воспользуемся симплекс–методом, («симплекс» - в переводе означает «простой», то есть несложный).

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

Рис. 3.1. Общий вид распределительной матрицы

На рис 3.1. с_ij - это единичная стоимость, т.е. стоимость перевозки единицы груза от i-го поставщика j-му потребителю.

Все преобразования симплекс-метода мы также будем проводить непосредственно в табличной матрице. Каждое очередное преобразование (итерация, что в переводе означает «шаг») будет продуцировать новый план перевозок, с уменьшенным значением целевой функции. Преобразования-итерации заканчиваются достижением оптимума. Для этого используются два метода: распределительный метод и метод потенциалов.

Каждый из названных методов приводит к оптимальному решению.

Каждый из алгоритмов по названным двум методам начинается с построения опорного решения, оно является исходным, с которого начинаем реализацию алгоритма. Нахождение опорного решение строится образом, что в нём число заполненных клеток должно равняться рангу системы r:

r = p+ q – 1 (3.4)

Для нахождения опорного решения имеются два метода: метод северо-западного угла и метод минимального элемента.

При этом формулируются и следующие ограничения:

- значения переменных х_ij должны быть больше или равны нулю, поскольку отрицательными объёмы перевозок быть не могут;

- остаётся в силе приведенное определение ранга системы.

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

(3.5)

где: n - общее число переменных x;

r – ранг системы.

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

Обычно такие базисные нули фигурируют в угловых клетках цикла, и без их использования невозможно организовать целенаправленного циклического преобразования.

В целом методика решения данной задачи осуществляется в следующей последовательности:

1. Находим одним из двух методов исходное опорное решение системы,

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

3. Останавливаем процесс при достижении Z_min .