1.4 Уточнение границ изменения ресурсов и цен на пэвм

Алгоритм исследования границ изменения ресурсов.

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

2. В исходной симплекс – таблице подставляем нижние границы, а затем верхние границы в отдельности по каждому ресурсу из пункта 5.

3. Проверяем план выпуска продукции на соответствие полученному решению.

4. Если план выпуска той продукции, которую выпускаем, не соответствует полученному решению, то к нижним границам мы прибавляем (вычитаем) шаг, равный 0.001 (до тех пор, пока план не сойдется), а из верхних границ вычитаем (прибавляем) по шагу равному 0.001 (то тех пор, пока план не сойдется).

Алгоритм исследования границ изменения цен.

1. Вводим в Simplex Solver значения исходной таблицы. Проводим анализ чувствительности к изменению коэффициентов критерия.

2. В исходной симплекс – таблице подставляем нижние границы, а затем верхние границы цены в отдельности для каждой продукции из пункта 7.

3. Проверяем план выпуска продукции на соответствие полученному решению.

4. Если план выпуска той продукции, которую мы выпускаем, не соответствует полученному решению, то к нижним границам мы прибавляем (вычитаем) шаг равный, 0.001 (до тех пор, пока план не сойдется), а из верхних границ мы вычитаем (прибавляем) по шагу равному 0.001 (до тех пор, пока план будет равным).

По результатам исследования составим таблицу.

Таблица 1.9 – Исследование границ изменения ресурсов и цен

Параметры исследования	Аналитическое исследование	Компьютерный анализ	Уточнение границы изменения
	__________	__________	__________
	__________	__________	__________
	__________	__________	__________

2 Решение транспортной задачи методом потенциалов

2.1 Задание

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

2. Построить модель транспортной задачи как задачи линейного программирования в канонической форма записи, составить к ней двойственную задачу.

3. Найти начальное решение, проверить его на невырожденность.

4. Решить задачу методом потенциалов.

5. Решить задачу в среде Microsoft Exel, приложить отчет.

В каждом варианте задания приведена таблица, в клетках которой проставлены элементы матрицы стоимостей перевозок (m=4, n=5), справа от таблицы значения запасов груза на складах , внизу значения запасов .

2.2 Алгоритм метода потенциалов

1.Построить математическую модель линейного программирования для транспортной задачи и двойственную к ней .

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

3.Проверить решение на невырожденность.

– ранг матрицы

Из размерности ранга матрицы А следует, что число ненулевых компонент плана системы ограничений должно быть . В этом случае решение называется невырожденным, а если число ненулевых решений меньше ранга, то такое решение называется вырожденным (вводится значимый нуль в клетку с минимальным значением C_ij из оставшихся так, чтобы можно было найти потенциалы (U,V).

4.Проверка плана на оптимальность.

4.1. Вычислить потенциалы.

Потенциалы находят из решения системы: ,

где U_i, V_j – потенциалы, переменные двойственной задачи

C_ij – стоимость перевозки единицы груза

4.2. Вычислить оценки:

• если все оценки положительны, , то это признак единственного оптимального решения, переход п.6;

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

• если имеются оценки , то это признак того, что найденное решение неоптимально и минимальная из отрицательных оценок определяет разрешающий элемент, переход п.5

5. Построить новый план.

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

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

Error: Reference source not found

5.2.Помечаем вершины цикла знаками «+» и «−» поочередно, начиная с разрешающего элемента.

0. 5.3.Находим величину сдвига по циклу - минимальный из элементов цикла, помеченных знаком «−»:

, где - цикл

5.4.Строим новый план , добавляя или вычитая, в соответствии со знаками вершин цикла, величину к элементам цикла. И переходим на пункт 4.

6. Конец

7. Решить задачу в среде Microsoft Exсel, приложить отчет.