Задачи транспортного типа

Пусть имеется m пунктов отправления от А1…Аm, на которых сосредоточены однородные товары или грузы в количестве а11…аm и n пунктов назначения В1….Вn, потребности которых в данном товаре равны b1..bn. Стоимость перевозки единицы груза из пункта Аi в пункт Bj составляет cij единицы – это стоимость- тариф. Требуется составить план перевоза, позволяющий вывезти весь товар из пунктов отправления и удовлетворить все потребности в пункте назначения, причем план должен иметь минимальную стоимость. Условие задачи записывается в виде матрицы планирования.

Математическая модель данной задачи имеет вид: ∑∑сij xij-> min

∑xij=ai ∑xij=bj i=1..m; j=1..n. Ограничения означают что весь груз должен быть вывезен из пункта отправления и все потребности в грузах должны быть удовлетворены. Решение транспортной задачи состоит из 2 этапов: определение первоначального плана; Улучшение опорного плана и построение оптимального плана. Методом определения первоначального плана является метод северо-западного угла или метод минимального элемента.

После определения первоначального опорного плана осуществляется определение его оптимального плана, методом потенциалов.

132 Методы решения задач одномерной оптимизации.

Дана некоторая функция f(x) от одной переменной x, надо определить такое значение x*, при котором функция f(x) принимает экстремальное значение. Под ним обычно понимают минимальное или максимальное значения. В общем случае функция может иметь одну или несколько экстремальных точек.

Методы одномерной оптимизации можно разделить на:

· методы исключения интервалов;

· методы точечного оценивания (полиномиальной аппроксимации);

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

1) Методы ориентированы на нахождение точки оптимума внутри заданного интервала и основаны на свойстве унимодальности функции.

Правила исключения интервалов.

Пусть унимодальна на интервале и достигает минимума в точке . Рассмотрим точки и такие, что если , то точка принадлежит интервалу , а интервал исключается.