Контрольная работа по Методам оптимизации решений Вариант №4

08.02.17 в 11:24

1. Сущность симплекс-метода.

Симплекс-метод — алгоритм решения оптимизационной задачи линейного программирования путём перебора вершин выпуклого многогранника в многомерном пространстве.

2. Исследовать функцию f(x), найти отрезок, на котором локализован один минимум. Выполнить три итерации для уточнения точки минимума методом «золотого» сечения.

2. x³+cos(x))²

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

Обозначим суммарный запас груза у всех поставщиков символом «a» , а суммарную потребность в грузе у всех потребителей – символом «b».

Тогда эта задача будет называться закрытой, так как а=b (21+36+60=117).

Составляем опорный план перевозок методом минимального элемента.

Считаем кол-во базисных клеток по формуле :  m+n-1= 3+3-1=5.

Кол-во базисных клеток в таблице = 5.

Следовательно, план перевозок – невырожденный.

Далее вычисляю потенциалы для плана перевозки.

Предположим, что U₁ = 0.

Тогда:   u₁ + v₁ = 2; 0 + v₁ = 2; v₁ = 2;
u₁ + v₂ = 3; 0 + v₂ = 3; v₂ = 3;
u₂ + v₂ = 3; 3 + u₂ = 3; u₂ = 0;
u₂ + v₃ = 8; 0 + v₃ = 8; v₃ = 8;
u₃ + v₃ = 2; 8 + u₃ = 2; u₃ = -6.

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_j > c_ij
(1;3): 0 + 8 > 3; ∆₁₃ = 0 + 8 — 3 = 5

Получаем новый план:

Проверим оптимальность опорного плана:    u₁ + v₁ = 2; 0 + v₁ = 2; v₁ = 2;
u₁ + v₃ = 3; 0 + v₃ = 3; v₃ = 3;
u₂ + v₃ = 8; 3 + u₂ = 8; u₂ = 5;
u₂ + v₂ = 3; 5 + v₂ = 3; v₂ = -2;
u₃ + v₃ = 2; 3 + u₃ = 2; u₃ = -1.

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_j > c_ij
(2;1): 5 + 2 > 3; ∆₂₁ = 5 + 2 — 3 = 4.

Получаем новый опорный план:

4. Решить по алгоритму Литтла задачу коммивояжера с матрицей.

Решение:

Возьмем в качестве произвольного маршрута:
X₀ = (1,2);(2,3);(3,4);(4,1).

5. Найти методом потенциалов оптимальный путь от пункта 1 к пункту 11.

Решение: