С помощью .

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

1. институт прав и свобод человека и (конституционного статуса личности);
2. институт государственного (территориального) устройства;
3. институт (систему) государственных органов;
4. государственную символику;
5. механизм защиты конституции.

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

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

1. Форма конституции в узком (формально-правовом) аспекте – основной закон.
2. Форма конституции в широком (материально-правовом) аспекте – вся нормативная структура, составляющая конституционный строй страны (все источники норм конституционного права).

Функции конституции РФ

В науке конституционного права различаются следующие функции конституции :

• учредительная;
• организаторская;
• внешнеполитическая;
• идеологическая;
• юридическая.

Учредительная функция

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

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

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

Нахождение оптимального плана транспортной задачи

Построенный одним из методов исходный опорный план можно довести до оптимального путем последовательного улучшения.

Существуют несколько таких методов: распределительный, метод потенциалов, венгерский метод и др. Рассмотрим метод потенциалов.

Метод потенциалов

Основой вычислительного процесса при улучшении опорного плана является определение критерия оптимальности:

где - расчетные затраты или косвенные тарифы, связанные с доставкойодной единицы груза из i -го пункта отправления в j -й пункт назначения, определяемые для тех клеток опорного плана, ресурсы в которые не распределены (для незаполненных клеток); c ij - затраты (истинные тарифы), связанные с доставкой одной единицей груза из i -го пункта отправления в j -й пункт назначения.

Т е о р е м а 4.1. Если для всех свободных клеток таблицы перевозок значение критерия оптимальности ≤0, то этот план перевозок является оптимальным.

Если для всех свободных клеток таблицы перевозок значение критерия оптимальности <0, то этот оптимальный план перевозок является единственным.

Если для некоторых свободных клеток значение критерия оптимальности = 0, то этот оптимальный план перевозок не является единственным.

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

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

Каждому поставщику A i ,где i = 1,2,...,т , ставится в соответствие некоторое число U i ,где i = 1, 2, ., т, которое называется потенциалом А-гопоставщика или i -й строки.

Каждому потребителю B j ,где j = 1,2,…,п , ставится в соответствие некоторое число V j ,которое называется потенциалом B j -го потребителя или j-го столбца.

Для каждой заполненной клетки, т.е. для каждой базисной переменной, строитсясоотношениеU i + V j = c ij Получают систему с числом уравнений, равным количеству базисных переменных (количеству заполненных клеток).Из этой системы определяют неизвестные потенциалы строк U i и столбцов V j .

Поскольку число неизвестных п+ т превышает на единицу число уравнений т+ п-1, одно из неизвестных можно положить равным произвольному числу, например, U 1 = 0 и найти значения остальных неизвестных. Значения потенциалов записываются в ту же матрицу планирования перевозок.

Для каждой незаполненной клетки, т. е. для каждой небазисной переменной, рассчитываются косвенные тарифы по формуле

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

То исходный план является оптимальным.

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

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

Цикл строится следующим образом. Вычеркиваются все строки и столбцы, содержащие ровно одну заполненную клетку. При этом считается, что выбранная клетка без поставки является заполненной. Все оставшиеся после вычеркивания клетки составляют цикл и лежат в его углах. Они соединяются ломаной линией.

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

В каждую клетку цикла, начиная с незаполненной, поочередно вписываем знаки «+» и «-». Так как у цикла четное количество вершин, то знаки будут чередоваться по кругу.

В клетках с отрицательными знаками выбирается минимальная величина поставки и обозначается А .В те вершины, которые имеют знак «+» прибавляется еще поставка А , а в вершинах со знаком «-» поставки уменьшают на величину А . При этом суммы поставок по строкам a i и по столбцам bjне изменятся.

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

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

Значения переменных, включенных в цикл, после пересчета переносятся в новую таблицу. Все остальные переменные записываются в новую таблицу без изменений.

Полученный новый базисный план проверяется на оптимальность.

Такое улучшение плана можно проводить до тех пор, пока все критерии для незаполненных клеток окажутся <0. Затем вычисляется оптимальная стоимость перевозок.

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

Алгоритм нахождения оптимального плана перевозок в транспортной задаче.

Оптимальный план перевозок находится по следующей схеме.

Строится исходный опорный план. Если он оказывается вырожденным, то вводятся условно занятые клетки с нулевыми поставками, дополняя число занятых клеток до m + n- 1.

Вычисляется значение целевой функции Z .

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

Выполняется пересчет поставок по циклу, загружается клетка, для которой не выполняется критерий оптимальности. Строится новый опорный план с числом занятых клеток, равным m + n -1.

Выполняется переход к пункту 3.

Следует иметь в виду, что при решении транспортной задачи возможны случаи вырождения, которые встречаются, если при построении плана перевозок число заполненных клеток окажется меньше, чем m + n- 1. В этом случае следует в свободные клетки ввести недостающее количество поставок, считая их нулевыми, но заполненными. Желательно вводить эти поставки в клетки с наименьшими тарифами. Однако если при выполнении дальнейших расчетов встречаются затруднения, например, происходит зацикливание, надо поменять заполненную нулем клетку.

Порядок выполнения работы

решить транспортную задачу в соответствии с предложенным вариантом с использованием ТП Excel ;

найти исходный опорный план методом северо-западного угла для вариантов с нечетным номером и методом наименьшей стоимости для вариантов с четным номером;

найти оптимальный план транспортной задачи методом потенциалов.

Пример выполнения работы

Некоторый однородный продукт, сосредоточенный у трех поставщиковА 1 , А 2 , A 3 в количестве а 1 , а 2 , а 3 тонн соответственно, необходимо доставить потребителям B 1 , B 2 , B 3 , B 4 , B 5 в количестве b 1 , b 2 , b 3 , b 4 , b 5 тонн.

Последовательность решения:

подготовить таблицы и заполнить их исходными данными: Стоимостиперевозки тонны продукта (D ), Ресурсы (а ) и Потребности (b );

с помощью функции СУММ найти суммы ресурсов (ячейка D 12) и потребностей (G 14);

подготовить таблицу оптимальных перевозок. Диапазон G 09:G 21 заполнить начальными значениями - нулями;

с помощью функции СУММ найти суммы перевозок по потребителям (C 22:G 22) и поставщиками (Н 19:Н 21);

в ячейку G 16 ввести выражение стоимости оптимального плана перевозок;

запустить инструментальное средство Поиск решения (меню Сервис/Поиск Решения) и ввести необходимые параметры: адрес целевой ячейки, изменяемые ячейки и ограничения (рис. 4.2).

Требования к отчету

Отчет должен содержать:

название лабораторной работы;

цель лабораторной работы;

результат решения в ТП Excel;

исходный опорный план, найденный методом северо-западного угла или методом наименьшей стоимости;

последовательность шагов нахождения оптимального плана методомпотенциала.

Варианты 1-8.Некоторый однородный продукт, сосредоточенный у трех поставщиков А 1 , А 2 , А 3 в количестве а 1 , а 2 , а 3 тонн соответственно, необходимо доставить потребителям В 1 , В 2 , В 3 , В 4 , В 5 в количестве b 1 , b 2 , b 3 , b 4 , b 5 тонн. Стоимость C ij перевозки тонны груза от i- го поставщика j -му потребителю задана матрицей D . Составить план перевозок, имеющий минимальную стоимость и позволяющий вывести все грузы и полностью удовлетворить потребности.

Варианты 9-16.Пусть на предприятии имеется т видов станков, максимальное время работы которых соответственно равно а, где i = 1,2, ..., т часов. Каждый из станков может выполнять п видов операций. Суммарное время выполнения каждой операции соответственно b j , j = 1, 2, п. Известна производительность (C j)i -го станка при выполнении j -й операции. Определить, сколько времени и на какой операции нужно использовать
каждый из станков, чтобы разработать максимальное количество деталей.

Для решения этой задачи линейную функцию умножить на -1, т.е. считать в таблице все значения C j отрицательными.

Приведем сходные данные для вариантов

a t			bj

a t			bj

a t			bj

a t			bj

a t			bj

a t			bj

a t			bj

a t			bj

a t			bj

a t			bj

a t	bj

a t	bj

a t	bj

a t	bj

a t	bj

a t			bj

a t			bj

a t	bj

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

1. Как формулируется транспортная задача?

2. Каков общий вид матрицы планирования перевозок?

3. Что называется планом транспортной задачи?

4. Какие существуют способы отыскания исходного опорного плана?

5. Охарактеризуйте метод северо-западного угла.

6. Охарактеризуйте метод наименьшей стоимости.

7. Какие существуют способы улучшения исходного опорного плана для транспортной задачи?

РАБОТА №5. НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

Цель работы - знакомство с простейшей задачей нелинейного программирования (нахождение оптимального значения функции одной переменной) и одним из методов ее решения - методом золотого сечения. Приобретение навыков решения оптимальных задач встроенными средствами системы MathCAD .

Программное обеспечение: интегрированная математическая системаMathCAD .

Теоретическое введение

Разработаны численные методы решения задач минимизации нелинейной функции как при ограничениях, так и без ограничений. Задачи и методы целесообразно изучать по схеме от простого к сложному. Сначала излагаются методы минимизации функции одной переменной. Далее рассматриваются методы для решения задач без ограничений с целевой функцией нескольких переменных. Наиболее сложными являются задачи оптимизации с ограничениями.

Универсального метода, с помощью которого можно было бы успешно решать разнообразные задачи оптимизации с ограничениями, не существует. Поэтому для решения каждого конкретного класса задач используют «свои» численные методы.

Классический метод минимизации функций одной переменной.Рассмотрим задачу нахождения минимума функции f(x) на отрезке [a; b ]. Классический метод подробно излагается в курсе математического анализа. Основным недостатком классического метода является узкая область его применения.

Если значения целевой функции определены из наблюдений или в результате проведения экспериментов, то получить аналитическое выражение для производной трудно. Но даже если f" (х ) найдена, то отыскание корней уравнения f" (х )=0 может составить сложную вычислительную задачу. Поэтому разработаны методы минимизации, которые не требуют числового значения производных и в которых объем вычисления значений целевой функции является наименьшим.

Унимодальные функции. Выделим класс функций, обладающих важным свойством.

Функция f(x)называется унимодальнойна отрезке [a; b ],если онаимеет на этом отрезке единственнуюточку глобального минимума x min
и слева от этой точки является строгоубывающей, а справа - строго возрастающей.

Другими словами, функция f(x) унимодальная, если точка x min существует и является единственной. Нарис. 5.1 представлен пример графикаунимодальной функции.

Имеет место следующее свойство унимодальной функции. Рассмотрим
две произвольные точки x 1 , x 2 є[a; b ] и a<x 1 <x 2

Если f(x 1) x 2) , то x min <x 2 (рис. 5.2, а), если же f (x 1) >f(x 2), то тогда
x min >x i (рис. 8.2, б).

Метод золотого сечения. Будем искать точку глобального минимума унимодальной функции f(x) на отрезке так, чтобы количество вычислений значений f (x) для заданной точности было наименьшим.

Рассмотрим на исходном отрезке точку x 1 и вычислимf(x) .Зная значение f (x ) только в одной точке, невозможно сузить область поиска точки x min . Поэтому выбираем вторую точку x 2 так, чтобы a<x 1 <x 2 f (x 2).

Возможен один из двух случаев:

f (x 1) x 2), согласно свойству унимодальной функции область поиска сужается до [a ; x 2 ];

f (x 1) >f (x 2), тогда область поиска сужается до [x 1 ; b ].

Где же лучше всего на исходном отрезке брать точки х 1 и х 2 ?

Так как первоначально ничего неизвестно о положении точки x min , то оба указанных выше случая равно возможны. Отсюда ясно, что точки х 1 и х 2 должны быть расположены симметрично относительно середины отрезка [a ; b ].

Чтобы найти «золотую середину», рассмотрим для простотыотрезок (рис. 5.3).

Чтобы точкаВ была «выгодной» как на первом этапе, так и на следующем, она должна делить отрезок ADв таком же отношении, как и АС, т.е.АВ/AD = BC/AC. При этом в силу симметрии аналогичным свойствам будетобладать и точка С.

В терминах координаты х пропорция примет вид

Это уравнение имеет корень меньше 1 и равный .

О точке, которая расположена на расстоянии % длины от одногоиз концов отрезка, говорят, что она выполняет «золотое сечение» данного отрезка. Очевидно, каждый отрезок имеет две такие точки, расположенные симметрично относительно середины.

Итак, точки x 1 и х 2 должны осуществлять «золотое сечение» исходного отрезка [a ; b ].

Вычисляем координаты точек, осуществляющих «золотое сечение» исходного отрезка,
, z 0 =a 0 +b 0 - y 0 и определяем значения f (y 0) иf (z 0).

Сравниваем значения f(y k - 1) и f(z k - 1), (к>1).

Если f(y k - 1) - 1 и вычисляем координату точки (слева от имеющейся) y k = a k + b k -z k и значениеf (y k).

Если f(y k - 1) >f(z k - 1), то полагаем a k =a k - 1 , b k =z k - 1 , z k =y k - 1 и вычисляем координату точки (справа от имеющейся) z k = a k + b k - y k и значение f(z k).

В любом из двух случаев вычисляется длина (k +1)-го отрезка: ∆ k - 1 =b k - y k или∆ k - 1 = z k -a k

Работа выполняется до тех пор, пока ∆ k - 1 0 - заданная точность вычислений.

Выбираем наименьшее из чисел f(y k) и f(z k)- приближенный минимум. А точка, которая ему соответствует, дает приближение к x min .

Порядок выполнения работы

Решить задачу оптимизации в системе MathCAD по алгоритму:

задать начальные условия задачи оптимизации;

построить график функции f (x );

оформить вычислительный блок Given с привлечением функции maximize или minimize ;

получить значения f (х ) опт и х опт.

Проанализировать полученный результат.

Обратите внимание! Для поиска значений переменных x 1 ,x 2 ,…,x n ,при которых функция f (x 1 ,x 2 ,...,x n) имеет максимальное или минимальное значение используются функцииmaximizef (x 1 , x 2 ,..., x n) и minimizef(x 1 , x 2 , ., x n). Обе эти функции реализованы достаточно универсальным алгоритмами оптимизации. Эти функции должны использоватьсяв составе вычислительного блока, открываемого директивой Given , и возвращают векторнеизвестных, при котором заданная функция имеет максимальное или минимальное значение. Внутри блока могут быть различные ограничительные условия в виде равенств илинеравенств. Число условий ограничено только памятью ПК. Перед блоком решения нужнозадать начальные значения искомых переменных.

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

Пример выполнения лабораторной работы

Из круглой заготовки изготавливается пожарное ведро по простой технологии: вырезается сектор, затем полученная таким образом выкройка сворачивается в конус, а шов сваривается.

Длина дуги выкройки становится длиной окружности в основании конуса ,

где R– радиус заготовки; – значение угла вырезки; r – радиус основания конуса.

Высота конуса h , радиус его основания rи радиус заготовки Rсвязаны теоремой Пифагора.

Пусть радиус заготовки равен одному метру: R = 1. Длина окружностиоснования конуса , высота конуса , объемконуса .

Математическая формулировка задачи имеет следующий вид (рис. 5.4).Требуется рассчитать значение угла вырезки а, при котором объем V () будет максимальным, угол задаетсяв радианной мере.

При решении задачи воспользуемся встроенной функциейинтегрированной математической системы MathCADmaximize (f ,var l, var2,...), возвращающей значения переменных varl, varl, ..., которыедоставляют функцииf максимальное значение.

Решение задачи с использованием панели программирования приведено на рис.5.5.

Требования к отчету

Отчет должен содержать:

копию документа, созданного в MathCAD ;

поясняющие записи из теории по теме лабораторной работы.

Варианты индивидуальных заданий

Вариант 1. f (x ) = 72x + 6х 2 - 8x 3 -x 4 наотрезке . Точку х*

Вариант 2. Вычислить максимальное значение функции f (x ) = 2х - x 2- e X на отрезке. Точку х* определить с точностью до 0,05.

Вариант 3. Вычислить максимальное значение функции f (х) = 2 sinx – tgx на отрезке. Точку х* определить с точностью до 0,05.

Вариант 4. f (х ) = 1 - 32х + 4х 2 + х 4 наотрезке . Точку х*

Вариант 5. Вычислить минимальное значение функции f (х ) = 1 + 4х + 2х 2 + х 4 на отрезке [-1; 0]. Точку х* определить с точностью до 0,01.

Вариант 6. Вычислить максимальное значение функции f (х ) = 2 + 5х -

10х 2 + 5х 3 - x 5 на отрезке [-3; -2]. Точку х* определить с точностью до 0,01.

Вариант 7. Вычислить максимальное значение функции f (х ) = 3 + 120х - 4х 2 - х 4 наотрезке . Точку х* определить с точностью до 0,01.

Вариант 8. Вычислить максимальное значение функции f (х ) = х- 1х 2 + 2х 3 - 1х 7 наотрезке . Точку х* определить с точностью до 0,01.

Вариант 9. Вычислить максимальное значение функции f (х ) = 5х + х 2 - 1х 4 на отрезке . Точку х* определить с точностью до 0,01.

Вариант 10. Вычислить максимальное значение функции f (х ) = 1 + х- 2х 2 + 4х 4 наотрезке . Точку х* определить с точностью до 0,01.

Вариант 11. Вычислить минимальное значение функции f (х ) = 2х +х-
- 5x 3 + 2x 4 на отрезке [-1; 0,5]. Точку х* определить с точностью до 0,01.

Вариант 12. Вычислить минимальное значение функции f (х ) = 2х + (х + 1)4на отрезке [-3; -1]. Точку х* определить с точностью до 0,01.

Вариант 13. Вычислить минимальное значение функции f (х ) = 2х + х- 5х на отрезке [-1; -0,5]. Точку х* определить с точностью до 0,01.

Вариант 14. Вычислить максимальное значение функцииf (х ) = х- 2х + 5х на отрезке . Точку х* определить с точностью до 0,01.

Вариант 15. Вычислить максимальное значение функции f (х ) = 1 - 6х - 3х 2 - х 6 наотрезке [-1; 0]. Точку х* определить с точностью до 0,01.

Вариант 16. Вычислить максимальное значение функции f (х) = 80х - 30х 2 - наотрезке . Точку х* определить с точностью до 0,01.

Вариант 17. Вычислить максимальное значение функции f (х ) = 1 + 2х + - наотрезке . Точку х* определить с точностью до 0,01.

Вариант 18. Вычислить минимальное значение функцииf (x ) = x 2 + x (lnx -1) наотрезке . Точку х* определить с точностью до 0,01.

Вариант 19. Вычислить максимальное значение функции f (x ) = x 3 - e x - 2x на отрезке [-2; 1]. Точку х* определить с точностью до 0,01.

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

1. В чем состоит классический метод оптимизации функции одной переменной?

2. Какие функции называются унимодальными?

3. В чем состоит суть метода золотого сечения?

4. Какая точка выполняет золотое сечение отрезка ?

РАБОТА №6. ПЛАНИРОВАНИЕ РАБОЧЕЙ СИЛЫ

Число рабочих, необходимых для выполнения какого-либо проекта, регулируется путем их найма и увольнения. Поскольку как наем, так и увольнение рабочих связано с дополнительными затратами, необходимо определить, как должна регулироваться численность рабочих в период реализации проекта.

Предположим, что проект будет выполняться в течение n недель и минимальная потребность в рабочей силе на протяжении i -й недели составит b i рабочих. При идеальных условиях хотелось бы на протяжении i -й недели иметь в точности b i рабочих. Однако в зависимости от стоимостных показателей может быть более выгодным отклонение численности рабочей силы как в одну, так и в другую сторону от минимальных потребностей. Если x i -й недели, то возможны затраты двух видов:

C 1 (x i – b i) – затраты, связанные с необходимостью содержать избыток x i – b i рабочей силы

C 2 (x i – x i -1) – затраты, связанные с необходимостью дополнительного найма x i – x i -1 рабочих.

Элементы модели динамического программирования определяются следующим образом.

Этап i представляется порядковым номером недели i , i = 1,2,..., n .

Вариантами решения на i -м этапе являются значения x i – количество работающих на протяжении i -й недели.

Состоянием на i -м этапе является x i -1 – количество работающих на протяжении (i – 1)-й недели (этапа).

Рекуррентное уравнение динамического программирования представляется в виде

,i = 1, 2, …, n ,

где f n +1(x n) º 0

Вычисления начинаются с этапа n при х n = b n и заканчиваются на этапе 1.

Пример 1 . Для реализации проекта строительный подрядчик определил минимальные потребности в рабочей силе на ближайшие пять недель следующим образом: 5, 7, 8, 4 и 6 рабочих соответственно. Содержание избытка рабочей силы обходится подрядчику в 300 долларов за одного рабочего в неделю, а наем рабочей силы на протяжении одной недели обходится в 400 долларов (независимо от количества принимаемых на работу человек) плюс 200 долларов за обучение одного нового рабочего в неделю.Необходимо определить, каким образом должна регулироваться численность рабочих в период реализации проекта. Задачу решить методом динамического программирования.

Решение. Выражая затраты в сотнях долларов, имеем:

b 1 =5, b 2 =7, b 3 =8, b 4 =4, b 5 =6,

C 1 (x i -b i)=3(x i -b i), x i >b i , i =1, 2, 3, 4, 5,

C 2 (x i -x i -1)=4+2(x i -x i -1), x i >x i -1, i =1, 2, 3, 4, 5.

Решение задачи начинаем с последнего (5-го этапа). По условию на этом этапе должно работать 6 работников. На предыдущем этапе в штате могло быть 4 (необходимый минимум), 5 или 6 работников (с учетом численности на 5-ом этапе).

Этап 5. (b 5 =6)

На третьем этапе должно работать максимальное число (8) работников. Поэтому в таблице 6.2х 3 = 8.

Этап 3. (b 3 =8)

x 2	С 1 (х 3 -8)+С 2 (х 3 -х 2)+ f 4 (x 3)	Опт.решение
х 3 = 8	f 3 (x 2)	x 3 *
	3(0)+4+2(1)+6=12
	3(0)+0+6=6

На втором этапе в штате может быть 7 исполнителей (необходимый минимум) или 8 исполнителей (с учетом потребностей следующего этапа). Поэтому в таблице 6.3х 2 = 7, 8.

Этап 2. (b 2 =7)

x 1	С 1 (х 2 -7)+С 2 (х 2 -х 1)+ f 3 (x 2)	Опт.решение
х 2 = 7	х 2 = 8	f 2 (x 1)	x 2 *
	3(0)+4+2(2)+12=20	3(1)+4+2(3)+6=19
	3(0)+4+2(1)+12=18	3(1)+4+2(2)+6=17
	3(0)+0+12=12	3(1)+4+2(1)+6=15
	3(0)+0+12=12	3(1)+0+6=9

На первом этапе, соответствующем началу выполнения проекта, в штат может быть зачислено от 5 до 8 исполнителей.

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

Лекция №3.

Вопросы для самостоятельной подготовки (по учебнику).

1. Медиатор. Виды медиаторов. Свойства медиаторов.

2. Электрические и тормозные синапсы. Особенности передачи сигнала.

3. Пути фармакологической регуляции синаптической передачи возбуждения.

Решение КТЗ методом потенциалов .

Метод потенциалов является модификацией метода последовательного улучшения плана в ЗЛП. Решение задачи включает в себя следующие этапы:

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

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

3. Переход в случае необходимости к лучшему опорному плану.

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

		v 1	…	v j	…	v n
	А i B j	B 1	…	B j	…	B n	a i
u 1	A 1	C 11		C 1j		C 1n	a 1
…	…					…	…
u i	A i	C i1		C ij		C in	a i
…	…					…	…
u m	A m	C m1		C mj		C mn	a m
	b j	b 1	…	b j	…	b n

Затем необходимо построить начальный опорный план.

Всего существует три метода отыскания начального ОП:

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

2) Метод минимального элемента,

3) Метод Фогеля.

Рассмотрим 2 первых метода.

Построение нач. ОП начинается с левой верхней клетки, которая заполняется элементом . Для этого между пунктами А 1 и В 1 назначается максимально возможный объем перевозки, определяемый как . При этом возможны три случая:

а) . При этом , а все остальные перевозки из пункта производства А 1 . Это означает, что из пункта А 1 вывозится вся произведенная продукция в пункт потребления В 1 , поэтому объем перевозок из А 1 другие пункты потребления равен 0 (нули в таблицу не записываются). Т.К. Из А 1 больше вывозить нечего, то первая строка таблицы вычеркивается, а потребность пункта В 1 уменьшается на величину , т.е. .

б) . При этом , а . Ресурс в А 1 уменьшается на величину , т.е. , а столбец В 1 вычеркивается, т.к. потребность пункта В 1 полностью удовлетворена.

в) . Тогда . В этом случае вычеркивается либо строка, либо столбец (но не оба сразу!). В этом случае опорный план будет являться вырожденным, и чтобы найти нулевые базисные переменные либо строка, либо столбец в таблице остаются. Если вычеркивается строка, то считаем, что в пункте потребления В 1 остается потребность, равная 0, которая в дальнейшем д.б. удовлетворена. Если же вычеркиваем столбец, то считаем, что в пункте производства А 1 остался запас, равный 0, который в дальнейшем д.б. вывезен.

В таблицу заносятся нулевые базисные переменные, но небазисные нули не заносятся, чтобы не спутать их с нулевыми базисными переменными.

Пусть теперь назначен, и один ряд таблицы (строка или столбец) вычеркнуты (закрыты). В оставшейся части таблицы вновь берем левую верхнюю клетку и в ней назначаем максимально возможный объем перевозки с учетом ранее назначенных. В результате закрывается еще один ряд. После назначения в (n+m-1) клетках объемов перевозок получится некоторый опорный план перевозок. В заполненных клетках будут записаны базисные переменные, а переменные в незаполненных клетках будут соответствовать небазисным, которые равны 0 и не записываются, чтобы не спутать с базисными нулями вырожденного опорного плана.

МЕТОД СЕВЕРО-ЗАПАДНОГО УГЛА

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

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

Во избежание ошибок после построения начального опорного решения необходимо проверить, что число занятых клеток равно m+n-1 и векторы условий, соответствующие этим клеткам, линейно независимы.

Необходимо иметь в виду, что метод северо-западного угла не учитывает стоимость перевозок, поэтому, опорное решение, построенное по данному методу, может быть далеким от оптимального.

Составить опорное решение методом северо-западного угла транспортной задачи, в которой 5 поставщиков и 5 потребителей. данные записаны в таблице 6

Таблица 6

Распределяем запасы первого поставщика. Так как его запасы меньше запросов первого потребителя, то в клетку (1,1) записываем перевозку и исключаем из рассмотрения первого поставщика. Определяем оставшиеся неудовлетворенными запросы первого потребителя.

Распределяем запасы второго поставщика. Так как его запасы, меньше запросов первого потребителя, то записываем в клетку (2,1) перевозку и исключаем из рассмотрения второго поставщика. Определяем оставшиеся неудовлетворенными запросы первого потребителя.

Распределяем запасы третьего поставщика. Так как его запасы больше запросов первого потребителя, то записываем в клетку (3,1) перевозку и исключаем из рассмотрения первого потребителя. Определяем оставшиеся неудовлетворенными запросы третьего поставщика.

Распределяем запасы третьего поставщика. Так как его запасы меньше запросов второго потребителя, то в клетку (3,2) записываем перевозку и исключаем из рассмотрения третьего поставщика. Определяем оставшиеся неудовлетворенными запросы второго потребителя.

Распределяем запасы четвертого поставщика. Так как его запасы больше запросов второго потребителя, то записываем в клетку (4,2) перевозку и исключаем из рассмотрения второго потребителя. Определяем оставшиеся неудовлетворенными запросы четвертого поставщика.

Распределяем запасы четвертого поставщика. Так как его запасы меньше запросов третьего потребителя, то в клетку (4,3) записываем перевозку и исключаем из рассмотрения четвертого поставщика. Определяем оставшиеся неудовлетворенными запросы третьего потребителя.

Распределяем запасы пятого поставщика. Так как его запасы больше запросов третьего потребителя, то в клетку (5,3) записываем перевозку и исключаем из рассмотрения третьего потребителя. Определяем оставшиеся неудовлетворенными запасы пятого поставщика.

Распределяем запасы пятого поставщика. Так как его запасы больше запросов четвертого потребителя, то в клетку (5,4) записываем перевозку и исключаем из рассмотрения четвертого потребителя. Определяем оставшиеся неудовлетворенными запасы пятого поставщика.

Распределяем запасы пятого поставщика. Так как его запасы равны запросам пятого потребителя, то в клетку (5,5) записываем перевозку и исключаем из рассмотрения пятого поставщика и пятого потребителя.

Ввиду того, что задача с правильным балансом, запасы всех поставщиков исчерпаны и запросы всех потребителей удовлетворены.

Результаты построения опорного решения приведены в таблице 7.

БЛОК-СХЕМА (АЛГОРИТМ РЕШЕНИЯ)

Западного

Постановка задачи

Четыре предприятия экономического района для производства продукции используют однородное сырье, спрос на которое составляет b j (у.е.).

Объем предложения сырья от трех поставщиков составляет, соответственно, a i (у.е.). Известны отпускные цены поставщиков р i (д.е./у.е.) и тарифы перевозок с ij (д.е./у.е.) от каждого поставщика А i к каждому предприятию В j . Требуется найти планы перевозок сырья предприятиям, при которых будут минимальными денежные затраты:

1)только на закупку сырья;

2)только на транспортировку сырья;

3)на закупку и транспортировку сырья.

Найти оценки логистического подхода для решения задачи закупки сырья предприятием.

Исходные данные

4 вариант.

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

Имеются три поставщика А i и четыре потребителя B j . Предложения поставщиков (а i), спросы потребителей (b j), а также затраты на перевозку единицы груза (с ij) от пункта А i к пункту B j заданы матрицей С (д.е./ед).

Найти первое опорное решение транспортной задачи методом северо-западного угла. Решение: Проверяем условие сбалансированности (закрытости) задачи

Т.к. то вводим дополнительный столбец (потребитель) с потребностью b 5 =70 - 48 = 22 (ед.).

Составляем транспортную таблицу:

Таблица 2

Поставщики	Потребители
B 1		B 3		B 5
A 1
A 2
A 3

Начинаем заполнение таблицы с левой верхней клетки: записываем максимально возможное значение x 11 =min(30;12)=12. Спрос потребителя В 1 удовлетворен и первый столбец исключаем из рассмотрения. Запасы первого поставщика равны 30-12 = 18.

В таблице находим новый северо-западный угол - клетку А 1 В 2 и записываем х 12 =min(18;10)=10.

В запасе поставщика А 1 осталось 8.

Находим следующий северо-западный угол х 13 =min(8;15)=8. Таким образом запас первого поставщика исчерпан - исключаем из рассмотрения первую строку.

В оставшейся таблице находим «северо-западный угол » и т.д. В результате получаем распределение поставок (см. табл.2). На каждом шаге (кроме последнего) из рассмотрения выпадали либо строка, либо столбец, а на последнем - и строка и столбец.

Поэтому число заполненных клеток (шагов) на единицу меньше суммы чисел строк и столбцов, т.е. план является невырожденным.

Найдем оптимальное решение транспортной задачи, выбрав первый опорный план методом минимального элемента.

Решение: Минимальный тариф c 33 =2; x 33 =min(22;15) =15.

Третий столбец вычеркиваем (обнуляем). Минимальный тариф для оставшихся клеток с 22 =4, х 22 =min(18;10) =10. Второй столбец вычеркиваем.

Для оставшихся клеток минимальный тариф с 34 =4, х 34 =min(22 - 15; 11) =7. Третью строку вычеркиваем.

Для оставшихся клеток минимальный тариф с 24 =5, х 24 =min(18-10;11-7) = 4.

Четвертый столбец вычеркиваем. Из оставшихся клеток основной таблицы минимальный тариф с 11 =6, х 11 =min(30;12) = 12. Первый столбец вычеркиваем.

Аналогично заполняем фиктивный столбец х 15 = 18, х 25 =4. Получаем первый опорный план. Количество загруженных клеток равно 3+5-1=7, т.е. выполняется необходимое условие невырожденности плана.

Таблица 3

Поставщики	Потребители
B 1		B 3		B 5
A 1
A 2
A 3
V j

Стоимость перевозки по этому плану составит:

L 1 =6*12 + 0*18 + 4*10 + 5*4 + 0*4 + 2*15 + 4*7 = 190 (д.е.). Число загруженных клеток равно m+n-1=3 + 5- 1 = 7, т.е. необходимое условие невырожденности плана выполняется. Последовательно, из уравнений, составленных для загруженных клеток, определяем потенциалы поставщиков и потребителей:

U 3 =0; V 1 =C 31 - U 3 = 5- 0 = 5; U 2 = C 21 - V 1 = 11 - 5 = 6;

V 2 = C 22 - U 2 = 4-6 = -2; V 3 = C 23 - U 2 = 8 - 6 = 2;

U 3 = C 33 - V 3 = 2 - 2 = 0; V 4 = C 34 - U 3 = 4 - 0 = 4;

V 5 = C 25 - U 2 = 0 - 6 = -6

Составим разности для свободных клеток:

12 = U 1 + V 2 - C 12 = 0 - 2 - 8 = -10

13 = U 1 + V 3 - C 13 = 0 + 2 - 13 = -11

14 = U 1 + V 4 - C 14 = 0 + 4 - 15 = -11

21 = U 2 + V 1 - C 21 = 6 + 5 - 11 = 0

23 = U 2 + V 3 - C 23 = 6 + 2 - 8 = 0

31 = U 3 + V 1 - C 31 = 0 + 5 - 5 = 0

32 = U 3 + V 2 - C 32 = 0 - 2 - 9 = -11

35 = U 3 + V 5 - C 35 = 0 - 6 - 0 = -6

Так как все разности то полученный план оптимален.

Минимальные затраты составят 190 (д.е.)