СКАЧАТЬ:  postroenie-pervonachalnogo-opornogo-plana1111111111.zip [221,39 Kb] (cкачиваний: 18)

Построение первоначального опорного плана

1. Метод северо-западного угла

Таблицу начинаем заполнять с левого верхнего угла. Дальше перемещаемся по строке вправо или по столбцу вниз. В клетку с координатами 1-1 необходимо занести меньшее из чисел

х₁₁=min(a₁,b₁)

Если a₁> b_1, то х₁₁=b₁, т.е записываем 120, первый столбец полностью закрыт.Затем перемещаемся по первой строке в соседнюю клетку с координатами 1-2, записываем меньшее из чисел, но уже разность (а₁-b₁,b₂) , т.е. 140-120=20<100, следовательно записываем 20, первая строка полностью закрывается. Переходим во вторую строку, в клетку с коэффициентами 2-2, записываем 70, т.к. 70<100 и вторая строка полностью закрывается. Переходим на третью строку и записываем в клетку с координатами 3-2   а₃,b₂-х₁₂х_22, т. е. 100-20-70=10, сравнивая 10<120, записываем в клетку с коэффициентами 3-2 число10 и второй столбец закрывается. Переходим  в следующую клетку с координатами 3-3, записываем в нее а₁- х₃₂,b₃ т. е. 120-10=110 и 110<150, то записываем в эту клетку 110 и третья строка закрывается. Переходим на четвертую строку, в оставшуюся пустую клетку  записываем b₃- х₃₃ =150-110=40

L=3450

2.Метод минимальной стоимости

Из всей таблицы выбираем наименьшую стоимость и в клетку, которая ей соответствует помещаем меньшее из чисел а или b, т.е. 40, 4-ая строка полностью закрывается. Из оставшейся части таблицы снова выбираем наименьшую стоимость, в нашем случае это клетка с коэффициентами 2-1, записываем 70, вторая строка полностью закрывается. Далее клетка с наименьшей стоимостью 1-2, записываем 100 и второй столбец полностью закрывается. Затем клетка с наименьшей стоимостью 1-1, в нее записываем b₁-x₂₁-x₄₁=120-70-40=10 и первый столбец полностью закрыт. Из оставшейся части наименьшая стоимость а₁-x₁₁-x₁₂=140-10-100=30 и записываем это число в клетку с коэффициентами  1-3, первая строка полностью закрывается. В последнюю не заполненную клетку записываем а₁=120

L=2440

3. Метод минимального элемента

В данном методе построения опорного решения начинают с клетки с наименьшей величиной стоимости и находим из всей таблицы min стоимость. Из нашей таблицы видно, что минимальную стоимость имеет клетка с коэффициентами 4-3, сравниваем

a₄<b_3, то х₄₃=a₄, т.е 40, четвертая строка полностью закрывается. Следующая клетка с коэффициентами 3-3, b₁-х₄₃=150-40=110, третий столбец полностью закрывается. Далее клетка с минимальной стоимостью, клетка с коэффициентами 3-2, а₃-х₃₃=120-110=10 сравниваем 10 и третья строка закрывается. Дальше клетка с наименьшей стоимостью 1-2, b₂-х₃₂=100-10=90, записываем 90 и второй столбец полностью закрывается. Из оставшейся части наименьшую стоимость имеет клетка с коэффициентами 2-1, записываем в эту клетку а₁-х₁₂=140-90=50 первая строка полностью закрывается, в последнюю незаполненную клетку с коэффициентами 2-1, записываем  а₂=70         

L=2750

Нахождение оптимального плана с помощью метода потенциалов.

После построения исходного опорного плана все переменные разбиты на 2 группы х_pq –свободные переменные, х_ke, базисные переменные.

L=

            Для  нахождения коэффициентов -при свободных переменных необходимо сопоставить каждому пункту отправления а_i некоторую величину U_i –потенциал пункта а_i. И каждому пункту назначения bj  потенциал пункта V_j-потенциал пункта bj_, свяжем эти величины равенством

U_k+V_l=C_kl

C_kl-стоимость перевозок 1тонны груза из пункта а в пункт b.

            Обозначим для свободных переменных сумму потенциалов через

=U_p+V_q

-косвенная стоимость.

            Тогда коэффициенты при свободных переменных определяется по формуле

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

Решение:

По методу Северо-западного угла.

Примем U₁=1, тогда из системы уравнений получим:

Найдем косвенную стоимость:

Коэффициенты  отрицательные, значит, переходим к следующему базису:

к  добавим 70, следовательно, из  вычтем, к добавим 70, из  вычтем.

Примем U₁=1, тогда из системы уравнений получим:

Найдем косвенную стоимость:

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

к  добавим 10, следовательно, из  вычтем, к добавим 10, из  вычтем

Примем U₁=1, тогда из системы уравнений получим:

Найдем косвенную стоимость:

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

к  добавим 10, следовательно, из  вычтем, к добавим 10, из  вычтем

Примем U₁=1, тогда из системы уравнений получим:

Найдем косвенную стоимость:

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

к  добавим 30, следовательно, из  вычтем, к добавим 30, из  вычтем

Примем U₁=1, тогда из системы уравнений получим:

Найдем косвенную стоимость:

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

к  добавим 10, следовательно, из  вычтем, к добавим 10, из  вычтем

Примем U₁=1, тогда из системы уравнений получим:

Найдем косвенную стоимость:

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

к  добавим 100, следовательно, из  вычтем, к  добавим 100, из  вычтем

Примем U₁=1, тогда из системы уравнений получим:

Найдем косвенную стоимость:

L=2290

Все коэффициенты положительны, следовательно минимум найден. С применением метода северо-западного угла оптимальный ответ найден в 7 шагов.

По методу минимального элемента.

Примем U₁=1, тогда решив систему, получим:

Найдем косвенную стоимость:

Коэффициенты  отрицательные, значит, переходим к следующему базису:

к  добавим 10, следовательно, из  вычтем, к добавим 10, из  вычтем.

Примем U₁=1, тогда решив систему, получим:

Найдем косвенную стоимость:

Коэффициент  отрицательные, значит, переходим к следующему базису:

к  добавим 10, следовательно, из  вычтем, к добавим 10, из  вычтем.

Примем U₁=1, тогда решив систему, получим:

Найдем косвенную стоимость:

Коэффициент  отрицательные, значит, переходим к следующему базису:

к  добавим 30, следовательно, из  вычтем, к добавим 30, из  вычтем.

Примем U₁=1, тогда решив систему, получим:

Найдем косвенную стоимость:

Коэффициенты  отрицательные, значит, переходим к следующему базису:

к  добавим 10, следовательно, из  вычтем, к добавим 10, из  вычтем.

Примем U₁=1, тогда решив систему, получим:

Найдем косвенную стоимость:

Коэффициент  отрицательные, значит, переходим к следующему базису:

к  добавим 100, следовательно, из  вычтем, к добавим 100, из  вычтем.

Примем U₁=1, тогда решив систему, получим:

Найдем косвенную стоимость:

L=2290

Все коэффициенты положительны, следовательно минимум найден. С применением метода минимального элемента оптимальный ответ найден в 6 шагов.

Контрольная работа

по дисциплине

Структура и математическое обеспечение системы управления