Решение задач линейного программирования

 

Z(x)=2500+2000+3000+500+500=8500

Для каждого  поставщика и потребителя находим  потенциал. Для этого составлем  систему уравнений U_i+V_i=C_ij для каждой заполненной решением клетки таблицы:U₁=0

U₁+V₃ => V₃=5

U₁+V₅ => V₅=0

U₁+V₆ => V₆=4

U₂+V₄ => V₄=4

U₂+V₆ => U₂=-1

U₃+V₁ => V₁=3

U₃+V₃ => U₃=-2

U₄+V₂ => V₂=1 

U₄+V₅ => U₄=0

Для всех не заполненных решением клеток таблицы  вычисляем оценку ∆_ij=U_i+V_j-C_ij .

∆₁₁=U₁+V₁-C₁₁=0+3-3=0≤0

∆₁₂=U₁+V₂-C₁₂=0+1-2=-1≤0

∆₁₄=U₁+V₄-C₁₄=0+4-4=0≤0

∆₂₁=U₂+V₁-C₂₁=-1+3-4=-2≤0

∆₂₂=U₂+V₂-C₂₂=-1+1-3=-3≤0

∆₂₃=U₂+V₃-C₂₃=-1+5-5=-1≤0

∆₂₅=U₂+V₅-C₂₅=-1+0-0=-1≤0

∆₃₂=U₃+V₂-C₃₂=-2+1-1=-2≤0

∆₃₄=U₃+V₄-C₃₄=-2+4-2=0≤0

∆₃₅=U₃+V₅-C₃₅=-2+0-0=-2≤0

∆₃₆=U₃+V₆-C₃₆=-2+4-2=0≤0

∆₄₁=U₄+V₁-C₄₁=0+3-4=-1≤0

∆₄₃=U₄+V₃-C₄₃=0+5-6=-1≤0

∆₄₄=U₄+V₄-C₄₄=0+4-3=1≥0

∆₄₆=U₄+V₆-C₄₆=M≤0

Так как ∆₄₄<0, то решение не оптимальное и его можно улучшить

min {500;500;1000}= 500

 

Z(x)=2500+3000+1000+1500=8000

Для каждого  поставщика и потребителя находим  потенциал. Для этого составлем  систему уравнений U_i+V_i=C_ij для каждой заполненной решением клетки таблицы:U₁=0

U₁+V₃=5  =>V₃=5

U₁+V₅=0  =>V₅=0

U₁+V₆=4  =>V₆=4    

U₂+V₆=3  =>U₂=-1

U₃+V₁=1 =>V₁=3

U₃+V₃=3 =>U₃=-2

U₄+V₂=1 =>V₂=1

U₄+V₄=3 =>V₄=3

U₄+V₅=0 =>U₄=0

Для всех не заполненных  решением клеток таблицы вычисляем  оценку ∆_ij=U_i+V_j-C_ij

∆₁₁=U₁+V₁=0+3-3=0 ≤0

∆₁₂=U₁+V₂=0+1-2=-1 ≤0

∆₁₄=U₁+V₄=0+3-4=-1 ≤0

∆₂₁=U₂+V₁=-1+3-4=-2 ≤0

∆₂₂=U₂+V₂=-1+1-3=-3 ≤0

∆₂₃=U₂+V₃=-1+5-5=-1 ≤0

∆₂₄=U₂+V₄=-1+9-3=-1 ≤0

∆₂₅=U₂+V₅=-1+0-0=-1 ≤0

∆₃₂=U₃+V₂=-2+1-1=-2 ≤0

∆₃₄=U₃+V₄=-2+3-2=-1 ≤0

∆₃₅=U₃+V₅=-2+0-0=-2 ≤0

∆₃₆=U₃+V₆=-2+4-2=0 ≤0

∆₄₁=U₄+V₁=0+3-4=-1 ≤0

∆₄₃=U₄+V₃=0+5-6=-1 ≤0 

В итоге получим  таблицу с учетом сделанных выше ограничений:

 
Целевая функция:

Z(x)=500+500+500+5000+3000+1500=10500

Ответ: min Z(Х)= 10500 при Х =  

8. Вывод

 

     Минимальные затраты в размере 10500 денежных единиц достигаются если обеспечить доставку видео- и аудиокассет:

1) со  склада №1 в магазин №3 в  количестве 500 тыс.шт.;

2) со склада №2 в магазин №3 в количестве 500 тыс.шт. и в магазин №4 в количестве 1000 тыс.шт.;

3) со склада №3 в магазин №1 500 тыс.шт.;

4) со склада №4 в магазины №2 и №4 в размере 500 тыс.шт. 
 
 

 

Заключение 

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

     Во  время решения задачи на составление  плана производства станков линейного программирования симплексным методом, я выбирал переменные x₁,x₂,x₃ так как в задаче сказано о том, что в плане производства использовались станки трёх видов, причем данные переменные должны быть больше нуля. После этого я составлял систему ограничений. Следующим шагом я находил целевую функцию задачи, так как цель задачи составление плана обеспечивающий максимальную прибыль , то целевая функция должна стремится к максимальной прибыли. Следующий мой шаг заключался в приведении задачи к каноническому виду. После приведения задачи к каноническому виду, я строил начальное опорное решение методом Гаусса. Только после этого задачу можно начать решать симплексным методом. Для этого я составлял первую симплексную таблицу, после её составления я проверял решение на оптимальность. Так как ∆₅ получилось меньше нуля, то решение не оптимальное, следовательно, его можно улучшить. Для этого я находил новое опорное решение с помощью «правила прямоугольника», определял ключевой столбец и ключевую строку. После этого рассчитывал новые элементы таблицы, затем заполнял таблицу получив элементами и после этого проверял решение на оптимальность, и так как все ∆_k были больше нуля, то решение оптимальное, следовательно, наибольшее значение Z(Х) = 72, при Х = (9; 3; 0).

     Во  время же решения транспортной задачи с ограничениями на пропускную способность, я опирался на условие задачи и  на её дополнительные условия. После  этого я составлял план перевозок  и проверял баланс задачи. В ходе этой проверки я выяснил, что необходимо ввести фиктивного потребителя, после этого я составлял таблицу перевозки товара. Следующим моим шагом было, выполнение дополнительных условий задачи, входе этого мне пришлось немного изменить таблицу перевозки товара. После этого я составил математическую модель транспортной задачи. После этого я задавал целевую функцию задачи, при условии того, что целью задачи является перевозка необходимой продукции с минимальными затратами. Проверял решение на оптимальность, то есть ∆_(ij ) должно было быть меньше нуля, но так как данное условие не выполнялось, то я строил цикл для клетки, в которой имеется наибольшее положительное число и в ее ставил знак плюс и добавлял его к заполненным клеткам. После этого снова задавал целевую функцию и проверял решение на оптимальность если данное условие не выполнялось, то вновь строил цикл, и так до тех пор пока ∆_k не стало меньше или равно нулю. Когда же это произошло, я возвращал таблицу в исходный вид и записывал ответ. 
 
 

 

Литература 

1. Вентцель Е.С. «Исследование операций». - М.:Наука, 2000 г. 
2. Кремер Н.Ш. «Исследование операций в экономике». - М.: ЮНИТИ, 2003 г.
3. Ермаков В.И. «Общий курс высшей математики для экономистов». – М.: Инфра-М, 2005 г.
4. Замков О.О., А.В. Толстопятенко, Ю.Н. Черемных «Математические методы в экономике» . - «Дело и Сервис», 2000 г.
5. Солодовников А. С., Бабайцев В. А., Браилов А. В. «Математика в экономике». – М.: Финансы и статистика, 2000г.
6. Кремер Н.Ш., Путко Б.А., Тришин И.М. «Высшая математика для экономических специальностей»- «Высшее образование»; «Юрайт- Издат», 2009 г.